Higher-dimensional Delaunay triangulations

Background

Attali and Boissonnat recently showed that the complexity of the Delaunay triangulation of a set of point scattered ``nicely" on a polyhedral surface in 3D is O(n), rather than the worst-case O(n^2) for arbitrary point sets. Their paper is available online through the library.

Dominique Attali and Jean-Daniel Boissonnat. A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces. Discrete and Computational Geometry. Vol. 31, No. 3, February, pages 369--384, 2004.

You could read and present this paper as a project.

We know that the worst-case examples of point sets in 3D consist of points distributed on 1D curves in space.

What is the complexity of the Delaunay triangulation of nicely distributed points on a three-dimensional surface in 4D? How about points nicely distributed on a 2D surface in 4D? A 3D surface in 6D? and so on. This is an open question, although we suspect that the answer is O(n^ceiling((d-k+1)/2)).

Experiments

Use Ken Clarkson's hull program for convex hulls and Delaunay triangulations in fixed dimension to find out. For some dimension k less than d, fix a k-dimensional surface in d-dimensions (not too degenerate; for instance a cubic surface), and sample it more and more densely. Look at how the size of the Delaunay triangulation of the sample grows with the size of the sample. Present the results of your experiments to the class.