Counting simple polygonalizations of a point set
A simple polygonalization of a finite point set $P$ in the plane is a simple polygon whose vertex set is exactly $P$, that is, a non-crossing Hamiltonian cycle on $P$ with straight edges.
Marx and Miltzow built a framework of dynamic programming over planar separators that, in $n^{(11+o(1))\sqrt n}$ time, counts the non-crossing straight-line graphs of a prescribed kind on $n$ points; for Hamiltonian cycles this counts simple polygonalizations in $n^{O(\sqrt n)}$ time. Some special cases were known before, for instance monotone polygonalizations, counted by Zhu, Sundaram, Snoeyink and Mitchell. The question is closely tied to drawing a simple polygonalization of $P$ uniformly at random, for which Auer and Held implemented heuristics.
Problem. Is there an algorithm that, given $n$ points in the plane, counts their simple polygonalizations in time polynomial in $n$?
Source: Origin uncertain; Problem 16 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- counting non-crossing Hamiltonian cycles, simple polygonalization, The Open Problems Project
References
@inproceedings{marxmiltzow2016,
author = {Marx, D{\'a}niel and Miltzow, Tillmann},
title = {Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
series = {LIPIcs},
volume = {51},
year = {2016},
pages = {52:1--52:16},
doi = {10.4230/LIPIcs.SoCG.2016.52},
}
@article{zhusundaramsnoeyinkmitchell1996,
author = {Zhu, Chong and Sundaram, Gopalakrishnan and Snoeyink, Jack and Mitchell, Joseph S. B.},
title = {Generating random polygons with given vertices},
journal = {Comput. Geom. Theory Appl.},
volume = {6},
year = {1996},
pages = {277--290},
}
@inproceedings{auerheld1996,
author = {Auer, Thomas and Held, Martin},
title = {Heuristics for the generation of random polygons},
booktitle = {Proc. 8th Canad. Conf. Comput. Geom.},
year = {1996},
pages = {38--43},
url = {https://www.cccg.ca/proceedings/1996/cccg1996_0007.pdf},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01073, "Counting simple polygonalizations of a point set", clopen.solutions.