N. Amenta, D. Attali, and O. Devillers, Complexity of delaunay triangulation for points on lowerdimensional polyhedra, Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms, 2007.

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.201-210, 2003.
DOI : 10.1145/777792.777823

J. Boissonnat, D. Cohen-steiner, B. Mourrain, G. Rote, and G. Vegter, Meshing of surfaces. Effective Computational Geometry for Curves and Surfaces, pp.181-229, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00488274

J. Cardinal, S. Collette, and S. Langerman, Region counting graphs, 21st European Workshop on Computational Geometry, 2005.

J. Cardinal, S. Collette, and S. Langerman, Empty region graphs, Computational Geometry, vol.42, issue.3, 2006.
DOI : 10.1016/j.comgeo.2008.09.003
URL : http://doi.org/10.1016/j.comgeo.2008.09.003

F. Cazals and J. Giesen, Delaunay triangulation based surface reconstruction. Effective Computational Geometry for Curves and Surfaces, pp.231-276, 2006.
DOI : 10.1007/978-3-540-33259-6_6
URL : https://hal.archives-ouvertes.fr/inria-00070609

T. Chan, J. Snoeyink, and C. Yap, Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams, Discrete & Computational Geometry, vol.18, issue.4, pp.433-454, 1997.
DOI : 10.1007/PL00009327

R. Dwyer, The expected number of k-faces of a Voronoi diagram, Computers & Mathematics with Applications, vol.26, issue.5, pp.13-21, 1993.
DOI : 10.1016/0898-1221(93)90068-7

H. Edelsbrunner, Geometry for modeling biomolecules Robotics: The Algorithmic Perspective, Proc. 3rd WAFR), pp.265-277, 1998.

J. Erickson, Nice Point Sets Can Have Nasty Delaunay Triangulations, Discrete and Computational Geometry, vol.30, issue.1, pp.109-132, 2003.
DOI : 10.1007/s00454-003-2927-4
URL : http://arxiv.org/abs/cs/0103017

J. Erickson, Dense Point Sets Have Sparse Delaunay Triangulations or ?... But Not Too Nasty?, Discrete & Computational Geometry, vol.33, issue.1, pp.83-115, 2005.
DOI : 10.1007/s00454-004-1089-3
URL : http://arxiv.org/pdf/cs/0110030v1.pdf

M. Golin and N. H. , 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

M. Golin and H. Na, The probabilistic complexity of the Voronoi diagram of points on a polyhedron, Proceedings of the eighteenth annual symposium on Computational geometry , SCG '02, pp.209-216, 2002.
DOI : 10.1145/513400.513426

E. W. Jaromczyk and G. T. Toussaint, Relative neighborhood graphs and their relatives, Proc. IEEE, pp.1502-1517, 1992.
DOI : 10.1109/5.163414
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1575

D. J. Marchette, Neighborhood graphs. Random Graphs for Statistical Pattern Recognition, pp.73-128, 2004.

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

A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2000.

R. Seidel, A convex hull algorithm optimal for point sets in even dimensions, M.Sc. thesis, Dept. Comput. Sci, 1981.

R. Seidel, Exact upper bounds for the number of faces in d-dimensional Voronoi diagrams Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.4, pp.517-530, 1991.

R. Seidel, Convex hull computations. Handbook of Discrete and Computational Geometry, chapter 19, pp.361-376, 1997.
DOI : 10.1201/9781420035315.pt3

D. Talmor, Well-Spaced Points and Numerical Methods, 1997.

S. Teng, Points, Spheres, and Separators: A Unified Geometric Approach to Graph Partitioning, 1992.