you're reading...

Counting Simple Polygonizations of Planar Point Sets

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



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 64 other followers

%d bloggers like this: