Area optimization of simple polygons
Sándor P. Fekete, William R. Pulleyblank · 1993
We discuss problems of optimizing the area of a simple polygon for a given set of vertices P and 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. We 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. We show that we can find a polygon of more than half the area AR(conv(P)) of the convex hull conv(P) of P, and demonstrate that it is NP-complete to decide whether there is a simple polygon of at least (3/2 + ε)AR(conv(P)). Finally, we prove that for 1 ≤ k ≤ d, 2 ≤ d, it is NP-hard to minimize the volume of the k-dimensional faces of a d-dimensional simple non-degenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980.