]. S. Références, M. Arya, and . Smid, Efficient construction of a bounded-degree spanner with low weight, Algorithmica, vol.17, issue.1, pp.33-54, 1997.

F. Baccelli and B. Blaszczyszyn, Spatial Modeling of Wireless Communications, a stochastic geometry approach

O. Beaumont, A. Kermarrec, L. Marchal, and É. Rivière, VoroNet: A scalable object network based on Voronoi tessellations, 2007 IEEE International Parallel and Distributed Processing Symposium, 2007.
DOI : 10.1109/IPDPS.2007.370210
URL : https://hal.archives-ouvertes.fr/inria-00358953

C. Mirela-ben-chen, C. Gotsman, and . Wormser, Distributed computation of virtual coordinates, Proceedings of the 23rd ACM Symposium on Computational Geometry, pp.210-219, 2007.

J. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, vol.20, issue.1, pp.51-71, 1992.
DOI : 10.1007/BF02293035
URL : https://hal.archives-ouvertes.fr/inria-00075274

T. Hubert, A. Chan, B. M. Gupta, S. Maggs, and . Zhou, On hierarchical routing in doubling metrics, Proc. 16th ACM-SIAM symp. on Discrete algorithms, pp.762-771, 2005.

B. Chazelle and L. J. Guibas, Fractional cascading: I. A data structuring technique, Algorithmica, vol.3, issue.2, pp.133-162, 1986.
DOI : 10.1007/BF01840440

L. P. Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry , SCG '86, pp.205-219, 1989.
DOI : 10.1145/10515.10534

O. Devillers, THE DELAUNAY HIERARCHY, International Journal of Foundations of Computer Science, vol.13, issue.02, pp.163-180, 2002.
DOI : 10.1142/S0129054102001035
URL : https://hal.archives-ouvertes.fr/inria-00166711

O. Devillers, S. Pion, and M. Teillaud, WALKING IN A TRIANGULATION, International Journal of Foundations of Computer Science, vol.13, issue.02, pp.181-199, 2002.
DOI : 10.1142/S0129054102001047
URL : https://hal.archives-ouvertes.fr/inria-00344519

J. Galtier, Tournament mac with constant size congestion window for wlan, Research Report, vol.6396, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00195965

J. A. Hartigan and M. A. Wong, Algorithm AS 136: A K-Means Clustering Algorithm, Applied Statistics, vol.28, issue.1, pp.100-108, 1979.
DOI : 10.2307/2346830

J. M. Keil and C. A. Gutwin, Classes of graphs which approximate the complete euclidean graph, Discrete & Computational Geometry, vol.11, issue.1
DOI : 10.1007/BF02187821

D. G. Kirkpatrick, Optimal Search in Planar Subdivisions, SIAM Journal on Computing, vol.12, issue.1, pp.28-35, 1983.
DOI : 10.1137/0212002

J. Kleinberg, The small-world phenomenon, Proceedings of the thirty-second annual ACM symposium on Theory of computing , STOC '00, pp.163-170, 2000.
DOI : 10.1145/335305.335325

E. Kranakis, H. Singh, and J. Urrutia, Compass routing on geometric networks, Proc. 11 th Canadian Conference on Computational Geometry, 1999.

F. Kuhn, R. Wattenhofer, and A. Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing , MobiHoc '03, pp.267-278, 2003.
DOI : 10.1145/778415.778447

J. Liebeherr, M. Nahas, and S. W. Si, Application-layer multicasting with Delaunay triangulation overlays, IEEE Global Telecommunications Conference, pp.1651-1655, 2001.
DOI : 10.1109/JSAC.2002.803067

S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, vol.28, issue.2, pp.129-137, 1982.
DOI : 10.1109/TIT.1982.1056489

N. Megiddo and K. J. Supowit, On the Complexity of Some Common Geometric Location Problems, SIAM Journal on Computing, vol.13, issue.1
DOI : 10.1137/0213014

G. Narasimhan and M. Smid, Geometric spanner networks, 2007.
DOI : 10.1017/CBO9780511546884

E. Ng and H. Zhang, Predicting Internet network distance with coordinates-based approaches, Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, 2002.
DOI : 10.1109/INFCOM.2002.1019258

B. Palop and D. Rio, Algorithmic problems on proximity and location under metric constraints, 2003.

F. P. Preparata, PLANAR POINT LOCATION REVISITED, International Journal of Foundations of Computer Science, vol.01, issue.01, pp.71-86, 1990.
DOI : 10.1142/S0129054190000072

J. Sabin and R. Gray, Global convergence and empirical consistency of the generalized Lloyd algorithm, IEEE Transactions on Information Theory, vol.32, issue.2, pp.148-155, 1986.
DOI : 10.1109/TIT.1986.1057168

M. Sharir, A near-linear algorithm for the planar 2-center problem, Proc. 12th Annu. ACM Sympos, pp.106-112, 1996.

G. Varghese, Network Algorithmics, 2005.
DOI : 10.1201/9781584888215-c28

F. Zhao and L. J. Guibas, Wireless Sensor Networks. An Information Processing Approach, 2004.
URL : https://hal.archives-ouvertes.fr/hal-01263160

I. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399