Skip to Main content Skip to Navigation

On the Size of Some Trees Embedded in Rd

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : This paper extends the result of Steele [6,5] on the worst-case length of the Euclidean minimum spanning tree EMST and the Euclidean minimum insertion tree EMIT of a set of n points S contained in Rd. More precisely, we show that, if the weight w of an edge e is its Euclidean length to the power of α, the following quantities Σ_{e ∈ EMST} w(e) and Σ_{e ∈ EMIT} w(e) are both worst-case O(n^{1-α/d}), where d is the dimension and α, 0 < α < d, is the weight. Also, we analyze and compare the value of Σ_{e ∈ T} w(e) for some trees T embedded in Rd which are of interest in (but not limited to) the point location problem [2].
Document type :
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Monday, January 18, 2010 - 4:58:48 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Thursday, October 18, 2012 - 12:40:56 PM


Files produced by the author(s)


  • HAL Id : inria-00448335, version 1



Pedro Machado Manhães de Castro, Olivier Devillers. On the Size of Some Trees Embedded in Rd. [Research Report] RR-7179, INRIA. 2010. ⟨inria-00448335⟩



Record views


Files downloads