Delaunay triangulation programs on surface data

ABSTRACT

The Delaunay triangulation of a set of points in 3D can have size Θ(n²) in the worst case, but this is rarely if ever observed in practice. We compare three production-quality Delaunay triangulation programs on some 'real-world' sets of points lying on or near 2D surfaces.

REFERENCES

• 1: The CGAL website. www.cgal.org
• 2: D. Attali and J-D. Boissonnat. Complexity of the Delaunay triangulation of points on a smooth surface. Manuscript, (2001).
• 3: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four Results on Randomized Incremental Constructions, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.463-474, February 13-15, 1992
• 4: Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276896]
• 5: Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
• 6: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 7: M. Golin and H. Na. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Proc. 12th Canadian Conference on Computational Geometry, (2000), pp 127-135.
• 8: Ernst P. Mücke , Isaac Saias , Binhai Zhu, Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.274-283, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237396]
• 9: S. Pion. Personal communication.