Counting Simple Polygonizations of Planar Point Sets.
Emo Welzl · Canadian Conference on Computational Geometry · 2011
Given a finite planar point set, we consider all possible spanning cycles whose straight line realizations are crossingfree – such cycles are also called simple polygonizations – and we are interested in the number of such simple polygonizations a set of N points can have. While the minumum number over all point configurations is easy to obtain – this is 1 for points in convex position –, the maximum seems to be more involved. M. Newborn and W.O.J. Moser were the first to ask the question around 1980 and they gave first evidence that this number has to be significantly less than the overall number (N − 1)!/2 of all spanning cycles. In 2000 A. Garcia, M. Noy and J. Tejel describe points sets that have as many as Ω(4.65 ) simple polygonizations, no improvement on this end has been reported since then. Despite of several improvements on the upper bound over the years, the currently best upper bound of O(54.6 ) (recent joint work with A. Sheffer and M. Sharir) leaves obviously a big gap to be closed. We report on the history of the problem and show how it connects to counting triangulations and crossingfree perfect matchings, and how Kasteleyn’s algebraic method for counting perfect matchings in planar graphs enters the picture. Basicially nothing is known for related algorithmic questions (determining the number of simple polygonizations for a given point set, enumerating all simple polygonizations).