Ponencia
A quadratic distance bound on sliding between crossing-free spanning trees
Autor/es | Aichholzer, Oswin
Reinhardt, Klaus |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-01 |
Publicado en |
|
Resumen | Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide ... Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide operations. No polynomial upper bound for this task has been known, but in O.Aichholzer, F.Aurenhammer, F.Hurtado Sequences of spanning trees and a fixed tree theorem. Computational Geometry: Theory and Applications, 21(1-2):3-20, 2002. a bound of O(n2 log n) operations was conjectured. |
Identificador del proyecto | 1/2003 |
Cita | Aichholzer, O. y Reinhardt, K. (2004). A quadratic distance bound on sliding between crossing-free spanning trees. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A quadratic distance bound on ... | 125.3Kb | [PDF] | Ver/ | |