2021/11/14 by Demaine, Erik D., Fekete, Sándor P., Keldenich, Phillip +2 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.07304
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 of n points in the plane. Both problems are known to be NP-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 from n = 10 all the way to n = 1, 000, 000.