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.
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.
Thomas Auer and Martin Held. Heuristics for the generation of random polygons. In Proc. 8th Canad. Conf. Comput. Geom., pages 38–43, 1996.
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.
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.