McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

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

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at