Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra

This research was initiated at the McGill-INRIAWorkshop on Computational Geometry in Computer Graphics, February 2006, co-organized by H. Everett, S. Lazard, and S. Whitesides, and held at the Bellairs Research Institute of McGill University.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 of order n to the power (d-1)/p for p between 2 and d-1. This improves on the well-known worst-case bound of n to the power ceiling of d/2