Strong Minkowski Decomposition is NP-Complete

Kazuo IWANO

Summary :

This paper shows that the strong Minkowski decomposition problem is NP-complete. Given two convex polygons α and β, the Minkowski sum α+β is a convex polygon defined by {(a_x+b_x, a_y+b_y|(a_x+a_y)α, (b_xb_y)β}. The Minkowski decomposition problem is for a given convex polygon γ to find two non-trivial convex polygons α and β whose Minkowski sum is γ. Silverman and Stein gave a linear-time algorithm for this problem. The strong Minkowski decomposition problem is to decompose a given convex polygon into two convex polygons in such a way that any pair of edges of two polygons are not in parallel. It is well known that the Minkowski sum of two convex polygons can be computed in linear time with respect to the number of edges involved. The NP-completeness result of the strong Minkowski decomposition problem shows interesting contrast to the following two results: One is that its inverse operation, the Minkowski sum operation, can be computed in linear-time; Another result, recently obtained by Mount and Silverman, is that the strong Minkowski operation for a convex polyhedron in R³ is also linear-time computable.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.4 pp.653-656
• Publication Date: 1991/04/25
• Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)

Authors

Kazuo IWANO

Keyword