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 cs.mcgill.ca.

www.cs.mcgill.ca/~beezer/Seminars/