Generating random simple polygons

Definitions and mathematical statement

Let $S=\{p_1,\ldots,p_n\}\subset\mathbb R^2$ be in general position (no three points collinear). A polygonization of $S$ is a cyclic ordering of all its points whose straight edges form a simple closed polygon. Identify cyclic shifts and reversal, and write $N(S)$ for the number of resulting undirected polygonizations.

The sampling question asks for a randomized algorithm which outputs each polygonization with probability exactly $1/N(S)$ and whose expected running time is polynomial in the input size. For a bit-complexity formulation, the point coordinates are rational and their binary lengths are included in that size. Exact uniformity is stronger than a distribution which is merely close to uniform. A separate question is the computational complexity of evaluating the integer $N(S)$ exactly.

The extremal part asks for the maximum of $N(S)$ over all $n$-point sets, including its asymptotic growth. Corresponding extremal counting questions replace polygonizations by triangulations of $\operatorname{conv}(S)$ using every point, or by noncrossing straight-line Hamiltonian paths or spanning trees on $S$. These are distinct families; their edge sets are counted once, without extra choices of a starting vertex or orientation.

Short English statement

Can all simple polygons through a given point set be counted or sampled uniformly in polynomial time? How large can these families, and related families of noncrossing graphs, become?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3800019 (AMR-037-0019), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erickson - Open Problems in Computational Geometry, Generating random simple polygons. Original source indexed by AMR-037-0019. https://jeffe.cs.illinois.edu/open/.
• S3 Jeff Erickson, Generating random simple polygons. https://jeffe.cs.illinois.edu/open/randompoly.html.