Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra

Nina Amenta (1) , Dominique Attali (2) , Olivier Devillers (3)

1 Visualization and Graphics Research Group.
2 GIPSA-GPIG - GIPSA - Géométrie, Perception, Images, Geste
3 GEOMETRICA - Geometric computing

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p between 2 and d-1, this improves on the well-known worst-case bound of $O(n^ceil(d/2))$.

Domaines: Géométrie algorithmique [cs.CG]

Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra. ACM-SIAM Symposium on Discrete Algorithms, Jan 2007, New Orleans, United States. pp.1106--1113. ⟨inria-00182835v2⟩