This Friday there will be a talk by Emo Welzl. It will be in the Boardroom at 11am as usual.
Abstract: Given a finite planar point set, we consider all possible spanning
cycles whose straight line realizations are crossing-free – 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.65N ) 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.6N ) (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 crossing-free perfect matchings, and how
Kasteleyn’s algebraic method for counting perfect matchings in planar
graphs enters the picture. Basicially nothing is known for related algo-
rithmic questions (determining the number of simple polygonizations
for a given point set, enumerating all simple polygonizations).