Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00448335
Contributor : Pedro Machado Manhaes de Castro <>
Submitted on : Monday, January 18, 2010 - 4:58:48 PM
Last modification on : Saturday, January 27, 2018 - 1:31:02 AM
Document(s) archivé(s) le : Thursday, October 18, 2012 - 12:40:56 PM

File

RR-7179.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00448335, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

442

Files downloads

152