On simple polygonalizations with optimal area
SP Fekete - Discrete & Computational Geometry, 2000 - Springer
Discrete & Computational Geometry, 2000•Springer
We discuss the problem of finding a simple polygonalization for a given set of vertices P that
has optimal area. We show that these problems are very closely related to problems of
optimizing the number of points from a set Q in a simple polygon with vertex set P and prove
that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a
given vertex set, resulting in a proof of NP-completeness for the corresponding area
optimization problems. This answers a generalization of a question stated by Suri in 1989 …
has optimal area. We show that these problems are very closely related to problems of
optimizing the number of points from a set Q in a simple polygon with vertex set P and prove
that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a
given vertex set, resulting in a proof of NP-completeness for the corresponding area
optimization problems. This answers a generalization of a question stated by Suri in 1989 …
Abstract
We discuss the problem of finding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon with vertex set P and prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. This answers a generalization of a question stated by Suri in 1989. Finally, we turn to higher dimensions, where we prove that, for 1 k d , 2 d , it is NP-hard to determine the smallest possible total volume of the k -dimensional faces of a d -dimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980.
Springer