Skip to main content
SpringerLink
Log in

A weak characterisation of the Delaunay triangulation

  • Original Paper
  • Published:
Geometriae Dedicata Aims and scope Submit manuscript

Abstract

We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional (strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented by a finite point sample.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22, 481–504 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Amenta, N., Choi, S., Dey, T.K., Leekha, N.: A simple algorithm for homeomorphic surface reconstruction. Int. J. Comput. Geom. Appl. 12(1–2), 125–141 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Attali, D., Edelsbrunner, H., Harer, J., Mileyko, Y.: Parametrized witness complexes. In: Proceedings 10th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, vol. 4619, pp. 386–397. Springer-Verlag (2007)

  4. Attali, D., Edelsbrunner, H., Mileyko, Y.: Weak witnesses for Delaunay triangulations of submanifolds. In: SPM’07: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, pp. 143–150, New York (2007)

  5. Boissonnat, J.-D., Guibas, L.J., Oudot, S.Y.: Manifold reconstruction in arbitrary dimensions using witness complexes. In: Proceedings 23rd ACM Symposium on Computational Geomentry, (2007)

  6. Chazal, F., Oudot, S.Y.: Towards persistence-based reconstruction in Euclidean spaces. In: Proce. 24th ACM Sympos. Comput. Geom. (2008, to appear).

  7. Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in Euclidean space. In: SoCG ’06: Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 319–326. ACM Press, New York (2006)

  8. Chazal, F., Lieutier, A.: Stability and computation of topological invariants of solids in R n. Discrete Comput. Geom. 37(4), 601–617 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  9. Cheng, S.-W., Dey, T.K., Ramos, E.: Manifold reconstruction from point samples. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1018–1027 (2005)

  10. Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103–120 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  11. de Silva, V., Carlsson, G.: Topological estimation using witness complexes. In: Alexa, M., Rusinkiewicz, S. (eds.) Eurographics Symposium on Point-Based Graphics, ETH, Zürich, Switzerland (2004)

  12. Edelsbrunner, H.: The union of balls and its dual shape. Discrete Comput. Geom. 13(3–4), 415–440 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533 (2002)

    MATH  MathSciNet  Google Scholar 

  14. Edelsbrunner, H., Mücke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graph. 13(1), 43–72 (1994)

    Article  MATH  Google Scholar 

  15. Edelsbrunner, H., Shah, N.R.: Triangulating topological spaces. Int. J. Comput. Geom. Appl. 7(4), 365–378 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)

    MATH  Google Scholar 

  17. Leibon, G., Letscher, D.: Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In: SCG’00: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, pp. 341–349. ACM Press, New York (2000)

  18. Martinetz, T., Schulten, K.: Topology representing networks. Neural Netw. 7(3), 507–522 (1994)

    Article  Google Scholar 

  19. Motzkin, T.S.: Beiträge zur Theorie der linearen Ungleichungen. PhD thesis, University of Basel (1933)

  20. Motzkin, T.S.: Two consequences of the transposition theorem on linear inequalities. Econometrika 19, 184–185 (1951)

    Article  MATH  MathSciNet  Google Scholar 

  21. Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39, 419–441 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  22. Oudot, S.Y.: On the topology of the restricted Delaunay triangulation and witness complex in higher dimensions. Manuscript, preprint available at http://graphics.stanford.edu/projects/lgl/papers/o-trdwchd-06/o-trdwchd-06.pdf, November 2006.

  23. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer Verlag, New York (1985)

    Google Scholar 

  24. Sugihara, K.: Laguerre voronoi diagram on the sphere. J. Geom. Graph. 6(1), 69–81 (2002)

    MATH  MathSciNet  Google Scholar 

  25. Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Pomona College, 610 N. College Avenue, Claremont, CA, 91711, USA

    Vin de Silva

Authors
  1. Vin de Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vin de Silva.

Rights and permissions

Reprints and permissions

About this article

Cite this article

de Silva, V. A weak characterisation of the Delaunay triangulation. Geom Dedicata 135, 39–64 (2008). https://doi.org/10.1007/s10711-008-9261-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10711-008-9261-1

Keywords

Mathematics Subject Classification (2000)

Search

Navigation