How many simple polygons on *n* points can there be?

More formally,

What is the number of simple polygonizations of a set of points,
maximized over all sets of *n* points?

The goal would be to give asymptotic bounds on this number, call it
*P*(*n*), in terms of *n*.
One trivial bound is that *P*(*n*) is at most *n*!,
because every polygonization induces an order on the *n* points.
But one would expect that most orders induce crossings, and so
*P*(*n*) is much smaller.

Indeed, it turns out that the asymptotics of *P*(*n*) is
*b*^{n} for some constant *b*. What remains open is
the exact base *b* of the exponentiation.
Here is a brief history of upper and lower bounds on *b*;
please let me know if I missed any.

Year | Bound on Base | Reference |
---|---|---|

1979 | 2.27 | [Akl 1979] |

1980 | 2.15 | [Newborn and Moser 1980] |

1987 | 3.26846179 | [Hayward 1987] |

1998 | 3.60501960 | [García and Tejel 1998] |

1995 | 4.642 | [García, Noy, and Tejel 1995] |

These lower bounds are generally based on counting a subset of polygonizations of a particular arrangement of points.

Year | Bound on Base | Reference |
---|---|---|

1982 | 10^{13} | [Ajtai, Chvátal, Newborn, and Szemerédi 1982] |

1989 | 1,384,000 | [Smith 1989; García, Noy, and Tejel 1995] |

1997 | 53,000 | [Pach and Tóth 1997; Ajtai et al. 1982] |

1998 | 38,837 | [Seidel 1998; García, Noy, and Tejel 1995] |

1997 | 2,226 | [Denny and Sohler 1997; García, Noy, and Tejel 1995] |

1999 | 1,888 | [Denny and Sohler 1997; Dumitrescu 1999] |

1999 | 936 | [Denny and Sohler 1997; Alt, Fuchs, and Kriegel 1999] |

2003 | 199 | [Santos and Seidel 2003; Alt, Fuchs, and Kriegel 1999] |

2005 | 87 | [Sharir and Welzl 2005] |

2009 | 70 | [Buchin, Knauer, Kriegel, Schulz, Seidel 2007; Sharir and Sheffer 2009] |

2011 | 56 | [Sharir, Sheffer, Welzl 2011] |

Several of these upper-bound papers are not directly about the polygonization
problem, but rather are about one of two other problems that have been shown to
be related in the sense that a bound on the related problem induces a bound on
the polygonization problem. Specifically, those results marked with an [Ajtai
et al. 1982] reference are based on lower bounds on the crossing number of a
graph, whose relation is shown in [Ajtai et al. 1982]. Another approach
[Sharir and Welzl 2005] uses a bound on the number of crossing-free matchings.
Finally, the results marked with a
[García, Noy, and Tejel 1995], [Dumitrescu 1999],
[Alt, Fuchs, and Kriegel 1999], or [Sharir and Sheffer 2009] reference
are based on upper bounds on the number of triangulations of *n* points.

The first bound along these lines says that, if there are at most
*c*^{n} triangulations, then there are at most
(8 *c*)^{n} polygonizations
[García, Noy, and Tejel 1995].
This bound was later improved to
(6.75 *c*)^{n} [Dumitrescu 1999].
Eppstein (personal communication, July 2002) points out that
an upper bound of (4 *c*)^{n} is straightforward,
because there are only 2^{2n} ways to color the 2*n*
triangles as inside or outside the polygon.
The bound of (3.3636 *c*)^{n}
follows from an upper bound of 3.3636^{n}
on the number of noncrossing cycles in a planar graph (triangulation)
[Alt, Fuchs, and Kriegel 1999].
This bound on the number of noncrossing cycles was improved to
30^{n/4} ≈ 2.3404^{n}
[Buchin, Knauer, Kriegel, Schulz, and Seidel 2007],
implying an upper bound of (2.3404 *c*)^{n} on the
polygonization problem, which is the basis for the current best upper bound.
At the time this paper was written, however, the best upper bound value on
*c* was 59 [Alt, Fuchs, and Kriegel 1999], so the resulting upper bound
of 138^{n} was worth than the already known bound of
87^{n} obtained by different techniques [Sharir and Welzl 2005].

The bounds on the number of triangulations are of interest in their own right,
with applications in mesh encoding and graphics.
The current best bound is 30^{n}
[Sharir and Sheffer 2009].
Combined with [Buchin, Knauer, Kriegel, Schulz, and Seidel 2007],
we obtain the current best bound on the polygonization problem:
70.2104^{n}.

The latest upper bound, by Sharir, Sheffer, and Welzl [2011], uses support weighted counting and a weighted Kasteleyn method.

**Monotone Polygons**: every vertical line intersects the boundary of the polygon at most twice. Here nearly tight bounds are known [Meijer and Rappaport 1990]. If the points have distinct*x*coordinates, the base of the exponent is between 1.618033989 and 2; and in general the base is between 2.058171027 and 2.236067977.**Starshaped Polygons**: every vertex of the polygon can be seen from a common point interior to the polygon, without obstruction by polygon edges. Nothing is known directly about this class. If the set of possible common interior points forms a positive-area*kernel*, then there are only polynomially many such polygons; specifically, there is an upper bound of*O*(*n*^{4}) [Deneen and Shute 1988]. This bound is claimed optimal in [Deneen and Shute 1988].

**Decision Problems.**
Given a set of points in the plane,
it is trivial to decide whether it has a simple polygonization:
the answer is yes unless all the points happen to be collinear.
On the other hand, given a set of points in the plane,
deciding whether there is an orthogonal polygonization
(all edges must be horizontal or vertical) is NP-complete if
180-degree angles are allowed [Rappaport 1986] and solvable in
*O*(*n* log *n*) time otherwise [O'Rourke 1988].
In the latter case, any polygonization is unique [O'Rourke 1988].

**Optimization Problems.**
Given a set of points in the plane, finding the simple polygonization with
either minimum area or maximum area is NP-complete [Fekete 2000].

- [Ajtai, Chvátal, Newborn, and Szemerédi 1982]
- M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi,
“Crossing-free subgraphs”, in
*Theory and Practice of Combinatorics*, volume 12 of Annals of Discrete Mathematics and volume 60 of North-Holland Mathematics Studies, 1982, pages 9–12. - [Akl 1979]
- Selim G. Akl, “A lower bound on the maximum number of crossing-free
Hamiltonian cycles in a rectilinear drawing of
*K*_{n}”,*Ars Combinatoria*, volume 7, 1979, pages 7–18. - [Alt, Fuchs, and Kriegel 1999]
- Helmut Alt, Ulrich Fuchs, and Klaus Kriegel,
“On the number of simple cycles in planar graphs”,
*Combinatorics, Probability & Computing*, volume 8, number 5, September 1999, pages 397–405. - [Buchin, Knauer, Kriegel, Schulz, and Siedel 2007]
- Kevin Buchin, Christian Knauer, Klaus Kriegel, André Schulz,
Raimund Seidel,
“On the number of cycles in planar graphs”,
in
*Proceedings of the 13th International Computing and Combinatorics Conference*, 2007, pages 97–107. - [Deneen and Shute 1988]
- Linda Deneen and Gary Shute, “Polygonizations of point sets in the
plane”,
*Discrete & Computational Geometry*, volume 3, number 1, 1988, pages 77–87. - [Denny and Sohler 1997]
- M. Denny and C. Sohler,
“Encoding a triangulation as a permutation of its point set”,
*Proceedings of the 9th Canadian Conference on Computational Geometry*, 1997, pages 39–43. - [Dumitrescu 1999]
- Adrian Dumitrescu, “On two lower bound constructions”,
*Proceedings of the 11th Canadian Conference on Computational Geometry*, Vancouver, 1999.`http://www.cs.ubc.ca/conferences/CCCG/elec_proc/c10.ps.gz`

- [Fekete 2000]
- S. P. Fekete, “On simple polygonalizations with optimal area,”
*Discrete & Computational Geometry*, volume 23, number 1, 2000, pages 73–110. - [García, Noy, and Tejel 1995]
- A. García, M. Noy, and A. Tejel,
“Lower bounds on the number of crossing-free subgraphs of
*K*_{n}”,*Proceedings of the 7th Canadian Conference on Computational Geoemtry*, 1995, pages 97–102. - [García and Tejel 1998]
- A. García and J. Tejel, “A lower bound for the number of
polygonizations of N points in the plane”,
*Ars Combinatoria*, volume 49, 1998, pages 3–19. - [Hayward 1987]
- Ryan B. Hayward, “A lower bound for the optimal crossing-free Hamiltonian
cycle problem”,
*Discrete & Computational Geometry*, volume 2, number 4, 1987, pages 327–343. - [Newborn and Moser 1980]
- Monroe Newborn and W. O. J. Moser, “Optimal crossing-free Hamiltonian
circuit drawings of
*K*_{n}”,*Journal of Combinatorial Theory, Series B*, volume 29, 1980, pages 13–26. - [O'Rourke 1988]
- Joseph O'Rourke, “Uniqueness of orthogonal connect-the-dots”,
in
*Computational Morphology*, North-Holland, 1988, pages 97–104. - [Pach and Tóth 1997]
- János Pach and Géza Tóth,
“Graphs drawn with few crossings per edge”,
*Combinatorica*, volume 17, number 3, 1997, pages 427–439. - [Rappaport 1986]
- David Rappaport, “On the complexity of computing orthogonal polygons from a set of points”, Technical Report SOCS-86.9, McGill University, Montréal, 1986.
- [Santos and Seidel 2003]
- Francisco Santos and Raimund Seidel,
“A better upper
bound on the number of triangulations of a planar point set”,
*Journal of Combinatorial Theory, Series A*, volume 102, number 1, 2003, pages 186–193. - [Seidel 1998]
- Raimund Seidel, “On the number of triangulations of planar point sets”,
*Combinatorica*, volume 18, number 2, 1998, pages 297–299. - [Sharir and Sheffer 2009]
- Micha Sharir and Adam Sheffer, “Counting triangulations of planar point sets”, arXiv:0911.3352. First version November 2009, revision January 2010.
- [Sharir, Sheffer, and Welzl 2011]
- Micha Sharir, Adam Sheffer, and Emo Welzl.
“Counting plane graphs:
perfect matchings, spanning cycles, and Kasteleyn's technique”,
arXiv:1109.5596, September 2011.
[Originally announced during an invited talk by Emo Welzl at
*23rd Canadian Conference on Computational Geometry*, Toronto, Canada, August 2011.] - [Sharir and Welzl 2005]
- Micha Sharir and Emo Welzl, “On the number of crossing-free matchings, cycles, and partitions”, Manuscript, July 2005.
- [Smith 1989]
- W. D. Smith, “Studies in Computational Geometry motivated by mesh generation”, Ph.D. Thesis, Princeton University, 1989.