A Semiring On Convex Polygons and Zero-Sum Cycle Problems

Abstract:

We show that two natural operations on the set of convex polygons form a closed semiring; the two operations are vector summation and convex hull of the union. We then investigate various properties of these operations: for example, the operation of vector summation takes O(m log m) time where m is the number of edges involved in the operation, while the decomposition of a given convex polygon into two convex polygons (in a sense, the inverse of vector summation) is NP-complete. 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. We show that this algorithm runs 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. We also investigate the undirected zero-sum cycle problem and the zero-sum simple cycle problem.