For n = 4 points, there is a maximum of 3 simple polygonizations.

Simple Polygonizations

by Erik Demaine

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

Last updated January 3, 2012 by Erik Demaine.