Area optimization of simple polygons
Fekete, Sandor P.
(1997)
Area optimization of simple polygons.
Technical Report
, 45 p.
Abstract
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 NPcomplete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NPcompleteness 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 NPcomplete to decide whether there is a simple polygon of at least (2/3+eps)(AR(conv(P)). We also sketch an NPhardness proof for the problem of finding a minimumlink 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 NPhard to minimize the volume of the kdimensional faces of a ddimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980.
Download: 
Postscript
Download (911kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  8 (Google Scholar)  
Uncontrolled Keywords:  approximation area complexity geometric optimization grid point Pick's theorem point separation polyhedra simple polygon traveling salesman problem 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr97256 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:46 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/256 