A Semiring On Convex Polygons and Zero-Sum Cycle Problems
Report ID: TR-053-86Author: Iwano, Kazuo / Steiglitz, Kenneth
Date: 1986-09-00
Pages: 47
Download Formats: |PDF|
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.