| A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)), where k = ceil(d+1)/(p+1)$. This bound is tight, and improves on the prior upper bound for most values of p. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||