Area-Optimal Simple Polygonalizations: The CG Challenge 2019

Erik D. Demaine; Sándor P. Fekete; Phillip Keldenich; Dominik Krupke; Joseph S.B. Mitchell

doi:10.1145/3504000

Area-Optimal Simple Polygonalizations: The CG Challenge 2019

Erik D. Demaine
, Sándor P. Fekete
, Phillip Keldenich
, Dominik Krupke
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

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 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.

Original language	English
Article number	2.4
Journal	ACM Journal of Experimental Algorithmics
Volume	27
Issue number	2
DOIs	https://doi.org/10.1145/3504000
State	Published - Mar 4 2022

Keywords

Computational geometry
algorithm engineering
area optimization
exact algorithms
geometric optimization
polygonization

Access to Document

10.1145/3504000

Cite this

@article{06ed148edda24c3c918fcd3ea4b3bccb,

title = "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 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.",

keywords = "Computational geometry, algorithm engineering, area optimization, exact algorithms, geometric optimization, polygonization",

author = "Demaine, \{Erik D.\} and Fekete, \{S{\'a}ndor P.\} and Phillip Keldenich and Dominik Krupke and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} 2022 Copyright held by the owner/author(s).",

year = "2022",

month = mar,

day = "4",

doi = "10.1145/3504000",

language = "English",

volume = "27",

journal = "ACM Journal of Experimental Algorithmics",

issn = "1084-6654",

publisher = "Association for Computing Machinery",

number = "2",

}

TY - JOUR

T1 - Area-Optimal Simple Polygonalizations

T2 - The CG Challenge 2019

AU - Demaine, Erik D.

AU - Fekete, Sándor P.

AU - Keldenich, Phillip

AU - Krupke, Dominik

AU - Mitchell, Joseph S.B.

PY - 2022/3/4

Y1 - 2022/3/4

N2 - 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.

AB - 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.

KW - Computational geometry

KW - algorithm engineering

KW - area optimization

KW - exact algorithms

KW - geometric optimization

KW - polygonization

UR - https://www.scopus.com/pages/publications/85150173799

U2 - 10.1145/3504000

DO - 10.1145/3504000

M3 - Article

SN - 1084-6654

VL - 27

JO - ACM Journal of Experimental Algorithmics

JF - ACM Journal of Experimental Algorithmics

IS - 2

M1 - 2.4

ER -

Area-Optimal Simple Polygonalizations: The CG Challenge 2019

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this