On the Size of Some Trees Embedded in ${\mathbb R}^d$

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 : We show that, for an Euclidean minimal k-insertion tree (EMITk), if the weight w of an edge e is its Euclidean length to the power of α, the sum on all edges of EMITk of their weights w(e) is O(n * k−α/d) in the worst case, where d is the dimension, for d ≥ 2 and 0 < α < d. We also analyze the expected size of EMITk and some stars, when points are evenly distributed inside the unit ball, for any α > 0.
Type de document :
Article dans une revue
Operations Research Letters, Elsevier, 2011, 39, pp.44-48. 〈10.1016/j.orl.2010.10.005〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00991081
Contributeur : Olivier Devillers <>
Soumis le : mercredi 14 mai 2014 - 16:36:15
Dernière modification le : samedi 27 janvier 2018 - 01:32:19

Identifiants

Collections

Citation

Pedro Machado Manhães de Castro, Olivier Devillers. On the Size of Some Trees Embedded in ${\mathbb R}^d$. Operations Research Letters, Elsevier, 2011, 39, pp.44-48. 〈10.1016/j.orl.2010.10.005〉. 〈hal-00991081〉

Partager

Métriques

Consultations de la notice

247