| DATE: | Wednesday, March 24th 2004. |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnel 320 |
| TITLE: | A quadratic distance bound on sliding between crossing-free spanning trees |
| SPEAKER: | Klaus Reinhardt, University of Tuebingen |
Let $S$ be a set of $n$ points in the plane in general position and
let ${\cal T}_S$ be the set of all crossing-free spanning trees of
$S$. We show that it is possible to transform any two trees in
${\cal
T}_S$ into each other by $O(n^2)$ local and constant-size edge slide
operations. Previously Avis and Fukuda have shown that the
corresponding tree graph is connected but no polynomial upper bound
for this task was known; in [AichholzerAurenhammerHurtado] a bound
of $O(n^2 \log n)$ operations was conjectured.
Joint work with Oswin Aichholzer, University of Graz