Simple Polygonizations
In November 2000, I ran into the following question. I was sure that it had
been explored before, but I had trouble finding information on it, so I created
this webpage.
How many simple polygons on n points can there be?
A simple polygon is a closed chain of straight line segments
that does not cross itself.
More formally,
What is the number of simple polygonizations of a set of points,
maximized over all sets of n points?
A simple polygonization of a set of points is a simple polygon whose
vertices are precisely that set of points. Simple polygonizations are also
called simple polygonalizations, spanning cycles, Hamiltonian polygons,
planar tours, or planar traveling salesman (TSP) tours.
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
bn 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]
Table 1: Approximate Lower Bounds.
|
These lower bounds are generally based on counting a subset of polygonizations
of a particular arrangement of points.
| Year | Bound on Base | Reference
|
|---|
| 1982 | 1013 | [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]
Table 2: Approximate Upper Bounds.
|
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
cn 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 22n ways to color the 2n
triangles as inside or outside the polygon.
The bound of (3.3636 c)n
follows from an upper bound of 3.3636n
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
30n/4 ≈ 2.3404n
[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 138n was worth than the already known bound of
87n 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 30n
[Sharir and Sheffer 2009].
Combined with [Buchin, Knauer, Kriegel, Schulz, and Seidel 2007],
we obtain the current best bound on the polygonization problem:
70.2104n.
The latest upper bound, by Sharir, Sheffer, and Welzl [2011],
uses support weighted counting and a weighted Kasteleyn method.
Related Problems
Classes of Polygons.
Instead of counting the number of simple polygonizations, researchers have
considered the number of certain types of simple polygonizations:
- 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(n4)
[Deneen and Shute 1988]. This bound is claimed optimal in
[Deneen and Shute 1988].
Other Subgraphs.
Another avenue of research is to look at certain types of noncrossing subgraphs
of an embedded complete graph, such as spanning trees and matchings,
or even a general subgraph of the complete graph.
See [Dumitrescu 1999] and [Sharir and Welzl 2005] for related results.
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].
Acknowledgments
Thanks to David Eppstein for pointing out
the
reference to
[Alt, Fuchs, and Kriegel 1999], which for several years led to the best
upper bounds.
Thanks to Michael Hoffmann for pointing out [Santos and Seidel 2003]
which was also a part of the best upper bound for a time.
Thanks to Piotr Rudnicki for pointing out an error in the paragraph
on decision problems (need to assume noncollinearity).
References
- [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
Kn”, 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
Kn”, 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 Kn”, 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.
