A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor, A linear-time algorithm for computing the voronoi diagram of a convex polygon, Discrete & Computational Geometry, vol.9, issue.6, pp.591-604, 1989.
DOI : 10.1007/BF02187749

D. Attali and J. Boissonnat, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth conference on Computational geometry , SCG '03, 2001.
DOI : 10.1145/777792.777823

C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, vol.22, issue.4, 1993.
DOI : 10.1145/235815.235821

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

J. Boissonnat and M. Teillaud, The hierarchical representation of objects: the Delaunay tree, Proceedings of the second annual symposium on Computational geometry , SCG '86, pp.260-268, 1986.
DOI : 10.1145/10515.10543

J. Boissonnat and M. Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, vol.112, issue.2, pp.339-354, 1993.
DOI : 10.1016/0304-3975(93)90024-N
URL : https://hal.archives-ouvertes.fr/inria-00075419

P. Bose and L. Devroye, Intersections with random geometric objects, Computational Geometry, vol.10, issue.3, 1995.
DOI : 10.1016/S0925-7721(98)00004-2
URL : http://doi.org/10.1016/s0925-7721(98)00004-2

L. P. Chew, Building Voronoi diagrams for convex polygons in linear expected time, Dept. Math. Comput. Sci, 1986.

L. P. Chew, Constrained Delaunay triangulations, Proceedings of the third annual symposium on Computational geometry , SCG '87, pp.215-222, 1987.
DOI : 10.1145/41958.41981
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.8264

O. Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry , SCG '98, 1997.
DOI : 10.1145/276884.276896
URL : https://hal.archives-ouvertes.fr/hal-01179446

O. Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry , SCG '98, pp.106-115, 1998.
DOI : 10.1145/276884.276896
URL : https://hal.archives-ouvertes.fr/hal-01179446

O. Devillers, On deletion in Delaunay triangulation, Proc. 15th Annu. ACM Sympos, pp.181-188, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00073239

O. Devillers, S. Meiser, and M. Teillaud, Fully dynamic delaunay triangulation in logarithmic expected time per operation, Computational Geometry, vol.2, issue.2, pp.55-80, 1992.
DOI : 10.1016/0925-7721(92)90025-N
URL : https://hal.archives-ouvertes.fr/hal-01180164

O. Devillers, S. Pion, and M. Teillaud, Walking in a triangulation
URL : https://hal.archives-ouvertes.fr/inria-00344519

O. Devillers, P. Franco, and . Preparata, A Probabilistic Analysis of the Power of Arithmetic Filters, Discrete & Computational Geometry, vol.20, issue.4, pp.523-547, 1998.
DOI : 10.1007/PL00009400
URL : https://hal.archives-ouvertes.fr/inria-00073727

O. Devillers, P. Franco, and . Preparata, Further results on arithmetic filters for geometric predicates, Computational Geometry, vol.13, issue.2, pp.141-148, 1999.
DOI : 10.1016/S0925-7721(99)00011-5
URL : https://hal.archives-ouvertes.fr/inria-00073157

L. Devroye, E. Peter-mücke, and B. Zhu, A Note on Point Location in Delaunay Triangulations of Random Points, Algorithmica, vol.22, issue.4, pp.477-482, 1998.
DOI : 10.1007/PL00009234

R. A. Dwyer, Higher-dimensional voronoi diagrams in linear expected time, Discrete & Computational Geometry, vol.43, issue.3, pp.343-367, 1991.
DOI : 10.1007/BF02574694

J. Erickson, Nice point sets can have nasty Delaunay triangulations, Proc. 17th Annu. ACM Sympos, pp.96-105, 2001.
DOI : 10.1007/s00454-003-2927-4
URL : http://arxiv.org/abs/cs/0103017

L. J. Guibas, D. E. Knuth, and M. Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, vol.134, issue.1-6, pp.381-413, 1992.
DOI : 10.1007/BF01758770

C. L. Lawson, Software for C 1 surface interpolation, Math. Software III, pp.161-194, 1977.

G. Liotta, P. Franco, R. Preparata, and . Tamassia, Robust proximity queries, Proceedings of the thirteenth annual symposium on Computational geometry , SCG '97, pp.864-889, 1998.
DOI : 10.1145/262839.262922

R. Motwani and P. Raghavan, Randomized Algorithms, 1995.

P. Ernst, I. Mücke, B. Saias, and . Zhu, Fast randomized point location without preprocessing in two-and three-dimensional Delaunay triangulations, Proc. 12th Annu. ACM Sympos, pp.274-283, 1996.

K. Mulmuley, Randomized multidimensional search trees: Dynamic sampling, Proc. 7th Annu. ACM Sympos, pp.121-131, 1991.
DOI : 10.1109/sfcs.1991.185371

K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, 1993.

M. S. Paterson and F. F. Yao, On nearest-neighbor graphs, Proc. 19th Internat. Colloq. Automata Lang. Program, pp.416-426, 1992.
DOI : 10.1007/3-540-55719-9_93

R. Seidel, The nature and meaning of perturbations in geometric computing, Proc. 11th Sympos, pp.3-17, 1994.

J. R. Shewchuk, Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator, First Workshop on Applied Computational Geometry, 1996.
DOI : 10.1007/BFb0014497

P. Su and R. Drysdale, A comparison of sequential Delaunay triangulation algorithms, Computational Geometry, vol.7, issue.5-6, pp.361-386, 1997.
DOI : 10.1016/S0925-7721(96)00025-9