On Simple Polygonalizations with Optimal Area
Fekete, Sandor P.
(2000)
On Simple Polygonalizations with Optimal Area.
Published in:
Discrete & computational geometry : an international journal of mathematics and computer science. Vol. 23 (1).
pp. 73110.
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 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. Finally, we turn to higher dimensions, where we prove that for 1<= k <=d, 2<=d, it is NPhard determine the smallest possible total 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
 Preprinted Version
Download (803kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Article 

Citations:  10 (Google Scholar)  3 (Web of Science) 
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:  zpr97256a 

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/256001 