Sequences of spanning trees for L-infinity Delaunay triangulations

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/127570

Title:	Sequences of spanning trees for L-infinity Delaunay triangulations
Author:	Bose, Prosenjit; Cano Vila, María del Pilar; Silveira, Rodrigo Ignacio
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. CGA -Computational Geometry and Applications
Abstract:	We extend a known result about L2-Delaunay triangulations to L∞-Delaunay. Let TS be the set of all non-crossing spanning trees of a planar n-point set S. We prove that for each element T of TS, there exists a length-decreasing sequence of trees T0, . . . , Tk in the L∞-metric such that T0 = T, Tk = MST(S) and Ti does not cross Ti−1 for all i = 1, . . . , k, where MST(S) denotes the minimum spanning tree of S in the L∞ metric. We also give an Ω(log n) lower bound for the length of the sequence
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional -Computational geometry -Geometry -- Data processing -Trigonometry -Geometria computacional -Geometria -- Informàtica -Trigonometria -Triangulació
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Published version Conference Object
Share: