The Delaunay triangulation of a set of points is a data structure, which in low dimensions has applications in mesh generation, surface reconstruction, molecular modeling, geographic information systems, and many other areas of science and engineering. Like many spatial partitioning techniques, however, it suffers from the ``curse of dimensionality": in higher dimensions, the complexity of the Delaunay triangulation increases exponentially.

In this talk, 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 $2 \leq p \leq d-1$, this improves on the well-known worst-case bound of $O(n^{\lceil d/2 \rceil})$.

This is a joint work with Nina Amenta and Olivier Devillers.