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

Appearances

[MO01]

Categories

polygons; point sets

Entry Revision History

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

Bibliography

AH96

T. Auer and Martin Held.
Heuristics for the generation of random polygons.
In Proc. 8th Canad. Conf. Comput. Geom., pages 38-43, 1996.

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

C. Zhu, G. Sundaram, Jack Snoeyink, and Joseph S. B. Mitchell.
Generating random polygons with given vertices.
Comput. Geom. Theory Appl., 6:277-290, 1996.