HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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