**Next:** Problem 17: Visibility Graph Recognition

**Previous:** Problem 15: Output-sensitive Convex Hull in \R^d

- Statement
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.- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

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

- Appearances
- Categories
polygons; point sets

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; 1 Jan. 2003.

- [AH96]
Thomas Auer and Martin Held. Heuristics for the generation of random polygons. In

*Proc. 8th Canad. Conf. Comput. Geom.*, pages 38–43, 1996.- [CHUZ01]
Jurek Czyzowicz, Ferran Hurtado, Jorge Urrutia, and Najib Zaguia. On polygons enclosing point sets.

*Geombinatorics*, XI:21–28, 2001.- [HMO+09]
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.- [MO01]
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.- [ZSSM96]
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.