Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 22, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Andreas Razen
For a planar point set we consider the graph of crossing-free straight-line spanning trees where two spanning trees are adjacent if their union is crossing-free. Recently, it was shown that an upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudo-triangulations of the underlying point set.
We prove a lower bound of $\Omega( log(n) / log(log(n)) )$ for the diameter of the graph of spanning trees on a planar set of $n$ points. This almost matches the known upper bound of $O( log(n) )$. If we measure the diameter in terms of the number of convex layers $k$ of the point set, our lower bound construction is tight, i.e. the diameter is in $\Omega( log(k) )$ which matches the known upper bound of $O( log(k) )$. So far only constant lower bounds were known.
Joint work with Kevin Buchin, Takeaki Uno and Uli Wagner.
Automatic MiSe System Software Version 1.4803M | admin login