Uniform samples of generic surfaces have nice Delaunay triangulations

• Download preprint (bugs and all):

• Slides from my talk at the DIMACS surface reconstruction workshop: displayed or printed

• See also:
  • Nice point sets can have nasty Delaunay triangulations
  • Dense point sets have sparse Delaunay triangulations

Abstract:

Let S be a fixed smooth surface in R³, such that no medial ball touches more than four times, counting with multiplicity, or more than three times at any single point. We show that the Delaunay triangulation of any uniform sample of S has complexity O(n log n) in the worst case. We also prove that the Delaunay triangulation of n random points on S has complexity O(n log³ n) with high probability. In both upper bounds, the hidden constants depend on the surface.

Note: This paper has several technical flaws. The same result was independently discovered, and correctly proved, by Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier; their paper "Complexity of the Delaunay Triangulation of Points on Surfaces: The Generic Case" will be published in SOCG 2003.

I was always delighted by the way [René] Thom discussed mathematics, using sentences obviously having no strict logical meaning.

- Vladimir Igorevich Arnol'd, in "An Interview with Vladimir Arnol'd",
Notices of the AMS 44(4):432-438, 1997.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 05 May 2003