On the Optimal Bisection of a Polygon
Elias Koutsoupias, Christos H. Papadimitriou, Martha Sideri
ORSA Journal on Computing · 1992 · Volume 4 · Issue 4
Abstract
We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any ratio. In contrast, we give a dynamic programming algorithm which finds a subdivision into two parts with total perimeter at most that of the optimum bisection, such that the two parts have areas within ε of each other; the time is polynomial in the number of sides of the polygon, and 1/ε. When the polygon is convex, or if the parts are required to be connected, then the exact problem can be solved in quadratic time. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
analysis of algorithms: a dynamic programming approximation algorithm for a geometric problem, computational complexity: NR-complete problem
Enable JavaScript for citation tools and additional paper interactions.