Problem 16: Simple Polygonalizations

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

[MO01]

Categories

polygons; point sets

Entry Revision History

J. O'Rourke, 2 Aug. 2001; 1 Jan. 2003.

Bibliography

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.