On simple polygonalizations with optimal area (Q1961852)

The author studies the problem of finding a simple polygonalization for a given set of vertices P in the Euclidean plane that has optimal area. He shows that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon or a maximum weight polygon for a given vertex set. The analysis of this relation produces a proof of NP-completeness for the corresponding area optimization problems. Problems in higher dimensions are also considered: he proves that for fixed dimensions \(k\) and \(d\), finding a simple \(d\)-dimensional polyhedron with a given set of vertices that has minimal volume of its \(k\)-dimensional faces is NP-hard.