Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/305

[2] https://www.cs.princeton.edu/research/techreps/author/349

[3] ftp://ftp.cs.princeton.edu/techreports/1986/053.pdf