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

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.