D. Attali and J. Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on a surface, Proc. 7th ACM Symposium on Solid Modeling and Applications, 2002.

F. Aurenhammer and R. Klein, Voronoi diagrams, Handbook of Computational Geometry, pp.201-290, 2000.

A. Aurenhammer, Power Diagrams: Properties, Algorithms and Applications, SIAM Journal on Computing, vol.16, issue.1, pp.78-96, 1987.
DOI : 10.1137/0216006

A. Jean-daniel-boissonnat, O. Cérézo, J. Devillers, M. Duquesne, and . Yvinec, An algorithm for constructing the convex hull of a set of spheres in dimension d, Computational Geometry, vol.6, issue.2, pp.123-130, 1996.
DOI : 10.1016/0925-7721(95)00024-0

J. Erickson, New Lower Bounds for Convex Hull Problems in Odd Dimensions, SIAM Journal on Computing, vol.28, issue.4, pp.1198-1214, 1999.
DOI : 10.1137/S0097539797315410

[. Nielsen and M. Yvinec, An Output-Sensitive Convex Hull Algorithm for Planar Objects, International Journal of Computational Geometry & Applications, vol.08, issue.01, pp.39-66, 1998.
DOI : 10.1142/S0218195998000047
URL : https://hal.archives-ouvertes.fr/inria-00074107

[. Okabe, B. Boots, K. ¯. Sugihara, and S. Will, Spatial tessellations: concepts and applications of Vorono? ? diagrams Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology, 1999.

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 -38330 Montbonnot-St, 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