A Semiring on Convex Polygons and Zero-Sum Cycle Problems

Authors:
  • KIKazuo Iwano
    Kazuo Iwano
  • KSKenneth Steiglitz
    Kenneth Steiglitz
Publisher website
Google Scholar
Abstract
Two natural operations on the set of convex polygons are shown to form a closed semiring; the two operations are vector summation and convex hull of the union. Various properties of these operations are investigated. Kleene’s algorithm applied to this closed semiring solves the problem of determining whether a directed graph with two-dimensional labels has a zero-sum cycle or not. This algorithm is shown to run in polynomial time in the special cases of graphs with one-dimensional labels, BTTSP (Backedged Two-Terminal Series-Parallel) graphs, and graphs with bounded labels. The undirected zero-sum cycle problem and the zero-sum simple cycle problem are also investigated.

This publication has 13 references indexed in Scilit: