On Simple Polygonalizations with Optimal Area |
| |
Authors: | S P Fekete |
| |
Institution: | (1) Department of Mathematics, TU Berlin, Str. des 17. Juni 136, D-10623 Berlin, Germany, DE |
| |
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.
Received June 26, 1997, and in revised form February 13, 1999, and May 19, 1999. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|