Next: Problem 17: Visibility Graph Recognition
Previous: Problem 15: Output-sensitive Convex Hull in \R^d
Can the number of simple polygonalizations of a set of n points in the plane be computed in polynomial time? A simple polygonalization is a simple polygon whose vertices are the points.
Uncertain, pending investigation.
Open.
Marx and Miltzow [MM16] give a planar-separator-based dynamic programming framework that, for any family of non-crossing straight-line graphs on an n-point set, counts those graphs in time n^{(11 + o(1))\sqrt{n}}. Since simple polygonalizations are exactly non-crossing Hamilton cycles, this framework yields an n^{O(\sqrt n)} algorithm for counting them, improving on Alvarez and Seidel’s [AS13] O(n^2 2^n) bound for counting triangulations.
Certain special cases are known (e.g., for computing the number of monotone simple polygonalizations [ZSSM96]), but the general problem remains open. The problem is closely related to that of generating a “random” instance of a simple polygon on a given set of vertices, with each instance being generated with probability 1/k, where k is the total number of simple polygonalizations. Heuristic methods are known and implemented [AH96].
See [CHUZ01] and [HMO+09] for related topics and references to relevant papers.
polygons; point sets
J. O’Rourke, 2 Aug. 2001; 1 Jan. 2003; J. Mallen, 18 June 2025.
Thomas Auer and Martin Held. Heuristics for the generation of random polygons. In Proc. 8th Canad. Conf. Comput. Geom., pages 38–43, 1996.
Victor Alvarez and Raimund Seidel. A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, SoCG ’13, pages 1–8, New York, NY, USA, 2013. Association for Computing Machinery.
Jurek Czyzowicz, Ferran Hurtado, Jorge Urrutia, and Najib Zaguia. On polygons enclosing point sets. Geombinatorics, XI:21–28, 2001.
Ferran Hurtado, C. Merino, D. Oliveros, T. Sakai, Jorge Urrutia, and I. Ventura. On polygons enclosing point sets II. Graphs Combinatorics, 25(3):327–329, 2009.
Dániel Marx and Tillmann Miltzow. Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1–52:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.
Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink, and Joseph S. B. Mitchell. Generating random polygons with given vertices. Comput. Geom. Theory Appl., 6:277–290, 1996.