On simple polygonalizations with optimal area
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.
- Computing area-optimal simple polygonizations
- Triangle-Based Heuristics for Area Optimal Polygonizations
- Area-optimal simple polygonalizations: the CG challenge 2019
- scientific article; zbMATH DE number 1445288
- On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
- Minimizing the stabbing number of matchings, trees, and triangulations
- On polygons enclosing point sets. II
- A note on lower bounds for the maximum area and maximum perimeter k-gon problems
- \(\alpha\)-concave hull, a generalization of convex hull
- Volume maximization and orthoconvex approximation of orthogons
- On separating points by lines
- On the effectiveness of the genetic paradigm for polygonization
- Optimal area polygonization problems: exact solutions through geometric duality
- Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
- On polygons excluding point sets
- scientific article; zbMATH DE number 988752 (Why is no real title available?)
- Spiral serpentine polygonization of a planar point set
- Greedy and local search heuristics to build area-optimal polygons
- Area optimal polygonization using simulated annealing
- Area-optimal simple polygonalizations: the CG challenge 2019
- Computing area-optimal simple polygonizations
- Triangle-Based Heuristics for Area Optimal Polygonizations
- A bound on a convexity measure for point sets
- An empirical study on randomized optimal area polygonization of planar point sets
- Edge sparsification for geometric tour problems
- Non-crossing Hamiltonian paths and cycles in output-polynomial time
- Optimal area polygonisation problems: mixed integer linear programming models
This page was built for publication: On simple polygonalizations with optimal area
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961852)
