Area optimization of simple polygons

Fekete, Sandor P. (1997) Area optimization of simple polygons.
Technical Report , 45 p.


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. This answers a generalization of a question stated by Suri in 1989. We give evidence that it is unlikely that the minimization problem can be approximated. For the maximiation problem, we show that we can find in optimal time O(n log n) a polygon of more than half the area AR(conv(P)) of the convex hull conv(P) of P, yielding a fast 1/2 approximation method for the problem. We demonstrate that it is NP-complete to decide whether there is a simple polygon of at least (2/3+eps)(AR(conv(P)). We also sketch an NP-hardness proof for the problem of finding a minimum-link searating polygon for two finite point sets in the plane. Finally, we turn to higher dimensions, where we prove that for 0<k<d+1, 1<d, it is NP-hard to minimize the 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.

Download: [img] Postscript
Download (911kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-256
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46