Let S be a fixed smooth surface in R3, 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 log3 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.