next up previous
Next: Problem 17: Visibility Graph Up: The Open Problems Project Previous: Problem 15: Output-sensitive Convex

Problem 16: Simple Polygonalizations

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.
Partial and Related Results
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
Entry Revision History
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.

The Open Problems Project - December 04, 2015