Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 18, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Andreas Razen
For a planar point set we consider the graph of crossing-free straight-line perfect matchings where two perfect matchings are adjacent if their union is crossing-free. In 2005 Houle et al. showed that this graph is connected and gave an upper bound of $n-2$ for its diameter, $n$ being the number of given points. Recently, this upper bound was improved to $O(log n)$ by Aichholzer et al.
We prove a lower bound of $\Omega( log n / log log n )$ for the diameter of this graph. So far only constant lower bounds were known.
Automatic MiSe System Software Version 1.4803M | admin login