How quickly can we generate a random simple polygon with a given set of vertices?More formally, for any setPof points in the plane, letSP(P)be the set of simple polygons wihose vertex set isP.Given a setNo polynomialtime algorithm is known.P, how quickly can we choose an element ofSP(P)uniformly at random?There are several fast algorithms to generate polygons from other useful (nonuniform) probability distributions. Many of these implemented in the RPG software package by Thomas Auer and Martin Held.

Auer and Held's paper also describes efficient algorithms to generate

starshapedpolygons uniformly at random in O(n^{4}) time. Chong Zhu and his coauthors describe an lineartime algorithm to uniformly generatemonotonepolygons. Both papers consider a Markov chain heuristic for genreating simple polygons that starts with an arbitrary simple polygon an performs random "2OPT moves" -- delete a pair of edges and reconnect the two resulting pieces the only other possible way, but backtrack if you get something nonsimple. Unfortunately, this heuristic leads to a nonuniform distibution of polygons in the limit.

- Thomas Auer and Martin Held. RPG: Heuristics for the generation of random polygons. Extended abstract in Proc. 8th Canad. Conf. Comput. Geometry, pp. 38-44, 1996.
- Joe O'Rourke and M. Virmani. Generating random polygons. Technical Report 11, Dept. Comput. Sci., Smith College, 1991.
- 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.
A more or less equivalent question is

How quickly can we count all simple polygons with a given set of vertices?Of course, there is an easy exponential time algorithm -- try all (n-1)!/2 possibilities -- but no polynomialtime algorithm is known. It is also not known whether the problem is #Phard. Hiedi Burgiel and Michelle Raymond have written an applet to count simplengons.When

Pis in convex position,SP(P)contains only the convex hull ofP, but if the points are in nonconvex position,SP(P)could be exponentially large. Letsp(n)denote the maximum size ofSP(P)over allnpoint setsP.How big isAuer and Held prove an O(sp(n)? For alln, whichnpoint sets define the largest number of simple polygons?n^{4}) upper bound on the number of starshaped polygons with a given set ofnvertices. The following simple construction of Chirstian Sohler implies a matching lower bound: putn-2 points on the unit parabolay=x^{2}, half on either side of thex-axis, and then add two points far below and to either side of the parabola.The corresponding questions about other simple geometric objects such as triangulations, simple polygonal paths, and simple spanning trees are also open. Perhaps triangulations have received the most study -- Raimund Seidel proved a lower bound of 2

^{3n-Omega(log n)}, and Markus Denny and Christian Sohler proved an upper bound of 2^{8.2n+O(log n)}. The problems of counting (and therefore uniformly generating) spanning trees ofgraphsare wellstudied, but as far as I know, none of those results apply to simple spanning trees of points in the plane. It's not clear to me whether the added restriction makes the problem easier or harder.The following question may be related.

Given two sets of points in the plane, how quickly can we compute a pair of disjoint simple polygons/paths, or report that no such pair exists?As far as I know, this problem has never been studied. I suspect it is NPhard. John Hershberger and I recently developed an algorithm that finds a pair of disjoint simple spanning trees in O(nlogn) time, or a short proof that no such trees exist.

Obviously we can generalize the problem to higher dimensions.

Given a set of points in 3space, how quickly can we generate a random simple polyhedron? A random tetrahedralization? A random unknotted polygon?Jock Snoeyink has asked the following question:How many triangulated surfaces (say, homoeomorphic to a disk) canSpecifically, can it be more thannpoints in 3space determine?n!, or is it always less?Given two sets of points in 3space, how quickly can we determine whether they are the vertices of two unlinked polygons?

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 09 Apr 1999