N. Amenta, D. Attali, and O. Devillers, Complexity of Delaunay triangulation for points on lower-dimensional polyhedra, Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pp.1106-1113, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00182835

S. Arya, T. Malamatos, and D. M. Mount, A simple entropy-based algorithm for planar point location, ACM Transactions on Algorithms, vol.3, issue.2, p.17, 2007.
DOI : 10.1145/1240233.1240240

D. Attali and J. Boissonnat, A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces, Discrete and Computational Geometry, vol.31, issue.3, pp.369-384, 2004.
DOI : 10.1007/s00454-003-2870-4
URL : https://hal.archives-ouvertes.fr/inria-00072135

D. Attali, J. Boissonnat, and A. Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth conference on Computational geometry , SCG '03, pp.237-246, 2003.
DOI : 10.1145/777792.777823

J. Beardwood, J. H. Halton, and J. M. Hammersley, The shortest path through many points, Math. Proc. Camb, pp.299-327, 1959.
DOI : 10.2307/2031707

P. Bose and L. Devroye, On the stabbing number of a random Delaunay triangulation, Computational Geometry, vol.36, issue.2, pp.89-105, 2007.
DOI : 10.1016/j.comgeo.2006.05.005

A. Bowyer, Computing Dirichlet tessellations, The Computer Journal, vol.24, issue.2, pp.162-166, 1981.
DOI : 10.1093/comjnl/24.2.162

. Cgal-editorial and . Board, CGAL User and Reference Manual, 3.6 edition, 2010.

J. Carufel, C. Dillabaugh, and A. Mahesgwari, Point location in well-shaped meshes using jump-and-walk, Proc. CCCG'11, pp.147-152, 2011.

P. M. De-castro and O. Devillers, On the asymptotic growth rate of some spanning trees embedded in, Operations Research Letters, vol.39, issue.1, pp.44-48, 2011.
DOI : 10.1016/j.orl.2010.10.005

P. M. De-castro and O. Devillers, A pedagogic JavaScript program for point location strategies. Demo, Proc. 27th Annu. Symp. Comp. Geom, pp.295-296, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00850551

C. Delage, Spatial sorting, CGAL User and Reference Manual. 3.6 edition, 2010.

E. D. Demaine, J. S. Mitchell, and J. O-'rourke, The Open Problems Project

E. D. Demaine, J. Iacono, and S. Langerman, Proximate point searching, Computational Geometry, vol.28, issue.1, pp.29-40, 2004.
DOI : 10.1016/j.comgeo.2004.01.005

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

L. Devroye, C. Lemaire, and J. Moreau, Expected time analysis for Delaunay point location, Computational Geometry, vol.29, issue.2, pp.61-89, 2004.
DOI : 10.1016/j.comgeo.2004.02.002

L. Devroye, E. P. 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. Dwyer, Convex hulls of samples from spherically symmetric distributions, Discrete Applied Mathematics, vol.31, issue.2, pp.113-132, 1991.
DOI : 10.1016/0166-218X(91)90064-4

S. Funke, K. Mehlhorn, and S. Näher, Structural filtering: a paradigm for efficient and exact geometric programs, Proc. 11th Canadian Conf. on Comp. Geom, 1999.
DOI : 10.1016/j.comgeo.2004.12.007

J. Gao and J. M. Steele, General Spacefilling Curve Heuristics and Limit Theory for the Traveling Salesman Problem, Journal of Complexity, vol.10, issue.2, pp.230-245, 1994.
DOI : 10.1006/jcom.1994.1011

M. J. Golin and H. Na, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, Computational Geometry, vol.25, issue.3, pp.197-231, 2003.
DOI : 10.1016/S0925-7721(02)00123-2

P. J. Green and R. R. Sibson, Computing Dirichlet Tessellations in the Plane, The Computer Journal, vol.21, issue.2, pp.168-173, 1978.
DOI : 10.1093/comjnl/21.2.168

I. Haran and D. Halperin, An experimental study of point location in planar arrangements in CGAL, Journal of Experimental Algorithmics, vol.13, pp.2-3, 2009.
DOI : 10.1145/1412228.1412237

J. Iacono, Improved Upper Bounds for Pairing Heaps, Proc. 7th Scandinavian Workshop on Algorithm Theor, pp.32-45, 2000.
DOI : 10.1007/3-540-44985-X_5

J. Iacono and S. Langerman, Proximate planar point location, Proceedings of the nineteenth conference on Computational geometry , SCG '03, pp.220-226, 2003.
DOI : 10.1145/777792.777826

J. Iacono, Expected asymptotically optimal planar point location, Computational Geometry, vol.29, issue.1, pp.19-22, 2004.
DOI : 10.1016/j.comgeo.2004.03.010

J. Iacono, A static optimality transformation with applications to planar point location, Proc. 27th Annu. Symp. Comp. Geom, pp.21-26, 2011.

M. Kazhdan, M. Bolitho, and H. Hoppe, Poisson surface reconstruction, Proc. 4th Eurographics Symp. on Geom. Processing, pp.61-70, 2006.

L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap, Classroom Examples of Robustness Problems in Geometric Computations, Proc. 12th European Symp. on Algorithms, pp.702-713, 2004.
DOI : 10.1007/978-3-540-30140-0_62
URL : https://hal.archives-ouvertes.fr/inria-00344515

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

D. E. Knuth, Optimum binary search trees, Acta Informatica, vol.6, issue.1, pp.14-25, 1971.
DOI : 10.1007/BF00264289

T. Malamatos, Lower bounds for expected-case planar point location, Computational Geometry, vol.39, issue.2, pp.91-103, 2008.
DOI : 10.1016/j.comgeo.2007.06.001

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

S. Pion and M. Teillaud, 3D triangulations, 2010.

L. K. Platzman, J. J. Bartholdi, and I. , Spacefilling curves and the planar travelling salesman problem, Journal of the ACM, vol.36, issue.4, pp.719-737, 1989.
DOI : 10.1145/76359.76361

L. A. Santaló, Integral Geometry and Geometric Probability, 1976.

J. R. Shewchuk, Stabbing Delaunay Tetrahedralizations, Discrete & Computational Geometry, vol.32, issue.3, p.343, 2002.
DOI : 10.1007/s00454-004-1095-5

S. Steven and . Skiena, The Algorithm Design Manual, 2008.

J. M. Steele, Cost of sequential connection for points in space, Operations Research Letters, vol.8, issue.3, pp.137-142, 1989.
DOI : 10.1016/0167-6377(89)90039-4

J. M. Steele and T. L. Snyder, Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization, SIAM Journal on Computing, vol.18, issue.2, pp.278-287, 1989.
DOI : 10.1137/0218019

C. K. Yap and T. Dubé, THE EXACT COMPUTATION PARADIGM, Computing in Euclidean Geometry, pp.452-492, 1995.
DOI : 10.1142/9789812831699_0011

M. Yvinec, 2D triangulations, CGAL User and Reference Manual. 3.6 edition, 2010.

B. Zhu, Adaptive Point Location with almost No Preprocessing in Delaunay Triangulations, 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering, pp.84-89, 2012.
DOI : 10.1109/ISVD.2012.16