On simple polygonalizations with optimal area

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 verte x set, resulting in a proof of NP-completeness for the corresponding area o ptimization 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 less than or equal to k less than or equal to d, 2 less than or equal to d, it is NP-hard to determine the smallest possible total volume of the k-dimensional faces of a d-dimensional simple nondegenerate polyhedron wit h a given vertex set, answering a generalization of a question stated by O' Rourke in 1980.