On simple polygonalizations with optimal area
type: Item
instance of: scholarly article
title: On simple polygonalizations with optimal area
zbMATH Open document ID: 0948.68128
DOI: 10.1007/PL00009492
author: Yanyan Li
published in: Discrete \& Computational Geometry
publication date: 2000-11-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 52C05
Mathematics Subject Classification ID: 58C07
zbMATH DE Number: 1394716
zbMATH Keywords: polygonalization
zbMATH Keywords: NP-completeness
zbMATH Keywords: optimization
zbMATH Keywords: area
zbMATH Keywords: volume
zbMATH Keywords: graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1394716