Show simple item record

Presentation

dc.creatorAichholzer, Oswines
dc.creatorReinhardt, Klauses
dc.date.accessioned2017-03-01T08:30:30Z
dc.date.available2017-03-01T08:30:30Z
dc.date.issued2004
dc.identifier.citationAichholzer, O. y Reinhardt, K. (2004). A quadratic distance bound on sliding between crossing-free spanning trees. En 20th European Workshop on Computational Geometry, Sevilla.
dc.identifier.urihttp://hdl.handle.net/11441/54977
dc.description.abstractLet 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.es
dc.formatapplication/pdfes
dc.language.isoenges
dc.relation.ispartof20th European Workshop on Computational Geometry (2004).
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectCrossing-free spanning treees
dc.subjectLocal transformationes
dc.subjectEdge slidees
dc.titleA quadratic distance bound on sliding between crossing-free spanning treeses
dc.typeinfo:eu-repo/semantics/conferenceObjectes
dc.type.versioninfo:eu-repo/semantics/submittedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.relation.projectID1/2003
idus.format.extent4 p.es
dc.eventtitle20th European Workshop on Computational Geometryes
dc.eventinstitutionSevillaes

FilesSizeFormatViewDescription
A quadratic distance bound on ...125.3KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional