Complexity of the delaunay triangulation of points on surfaces the smooth case

ABSTRACT

It is well known that the complexity of the Delaunay triangulation of N points in R ³, i.e. the number of its faces, can be O (N²). The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface.In this paper, we bound the complexity of the Delaunay triangulation of points distributed on generic smooth surfaces of R ³. Under a mild uniform sampling condition, we show that the complexity of the 3D Delaunay triangulation of the points is O(N log N).

REFERENCES

• 1: Nina Amenta and Marshall Bern. Surface reconstruction by voronoi filtering. Discrete Comput. Geom., 22:481--504, 1999.
• 2: Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566304]
• 3: A. G. Belyaev, E. V. Anoshkina, and T. L. Kunii. Ridges, ravines and singularities. In A. T. Fomenko and T. L. Kunii, editors, Topological Modeling for Visualization. Springer, 1997.
• 4: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 5: Jean-Daniel Boissonnat and Frédéric Cazals. Smooth surface reconstruction via natural neighbour interpolati on of distance functions. Comp. Geometry Theory and Applications, pages 185--203, 2002.
• 6: T. M. Chan, J. Snoeyink, and C. K. Yap. Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d Voronoi diagrams. Discrete Comput. Geom., 18:433--454, 1997.
• 7: Olivier Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163--180, 2002.
• 8: T. K. Dey. Curve and surface reconstruction. In in Handbook of Discrete and Computational Geometry, Goodman and O' Rourke eds., CRC press, 2nd edition, 2001.
• 9: Tamal K. Dey , Joachim Giesen , James Hudson, Delaunay based shape reconstruction from large data, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
• 10: 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]
• 11: Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
• 12: Mordecai Golin and HyeonSuk Na. On the average complexity of 3d-voronoi diagrams of random points on convex polytopes. In Proc. 12th Canad. Conf. Comput. Geom., pages 127--135, 2000.
• 13: Mordecai J. Golin , Hyeon-Suk Na, The probabilistic complexity of the Voronoi diagram of points on a polyhedron, Proceedings of the eighteenth annual symposium on Computational geometry, p.209-216, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513426]
• 14: Laurent Schwartz. Analyse, Topologie générale et analyse fonctionnelle. Hermann, 1970. Deuxième édition revue et corrigée.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Performance, Theory

Keywords:
Delaunay triangulation, Voronoi diagram, complexity, generic surfaces, reconstruction, smooth surfaces