Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 07, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Manuel Wettstein
Let P be a set of n points in the plane, let M(P) be the set of crossing-free perfect matchings with vertex set P and edges embedded as straight line segments, and let pm(P) = |M(P)|. We present a counting algorithm which computes the number pm(P) in time O*(2^n), and we show how this algorithm can be modified such that the set M(P) is enumerated using polynomial time per enumerated object. Moreover, we briefly mention that the presented ideas can be generalized into an abstract framework, which gives rise to counting algorithms for many other types of geometric graphs, e.g. the set of all crossing-free geometric graphs, convex partitions, convex subdivisions, crossing-free spanning trees and crossing-free spanning cycles.
Automatic MiSe System Software Version 1.4803M | admin login