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].
Type de document :
Rapport
[Research Report] RR-7179, INRIA. 2010
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00448335
Contributeur : Pedro Machado Manhaes de Castro <>
Soumis le : lundi 18 janvier 2010 - 16:58:48
Dernière modification le : samedi 27 janvier 2018 - 01:31:02
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 12:40:56

Fichier

RR-7179.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

338

Téléchargements de fichiers

114