Complexity of the Delaunay triangulation of points on polyhedral surfaces (Q1434252)

This paper studies the expected complexity of the Delaunay triangulations of points distributed on the boundary of a given polyhedron in 3-space. It is shown that under certain sampling conditions the expected complexity is \(O(n^{1.8})\) for general polyhedral surfaces and \(O(n\sqrt{n})\) for convex polyhedral surfaces. This differs remarkably from the known worst-case complexity of \(O(n^2)\), and the expected linear complexity for uniform distribution on a cube or ball. The result is based on a result that shows the medial axis is well approximated by a subset of the Voronoi vertices of the sample points.