Area-Optimal Simple Polygonalizations: The CG Challenge 2019
Abstract
We give an overview of theoretical and practical aspects of finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set ofnpoints in the plane. Both problems are known to beNP-hard and were the subject of the 2019 Computational Geometry Challenge, which presented the quest of finding good solutions to more than 200 instances, ranging fromn= 10 all the way ton= 1, 000, 000.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 04, 2022
- Source ID
- 10.1145/3504000
Entities
People
- Dominik Krupke
- Erik D. Demaine
- Joseph S. B. Mitchell
- Phillip Keldenich
- Sándor P. Fekete
Organizations
- Defense Advanced Research Projects Agency
- Massachusetts Institute of Technology
- National Science Foundation
- Sandia National Laboratories
- Stony Brook University
- TU Braunschweig