A weak characterisation of the Delaunay triangulation. (English) Zbl 1165.52014
The author introduces a variant of the well-known Delaunay triangulation of a finite point set in a metric space, the so-called weak Delaunay triangulation, which in general contains additional simplices. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in spherical and hyperbolic space and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and the author proves equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. Finally, the application which motivated these ideas is discussed: how to recover the topology of a manifold (or simplicial complex) from a finite sample of points.
Reviewer: Johann Linhart (Salzburg)
MSC:
| 52B55 | Computational aspects related to convexity |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
Delaunay triangulation; Voronoi diagram; witness complex; manifold reconstruction; topological approximationReferences:
| [1] | Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22, 481–504 (1999) · Zbl 0939.68138 · doi:10.1007/PL00009475 |
| [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) · Zbl 1152.68653 · doi:10.1142/S0218195902000773 |
| [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) · Zbl 1209.68577 |
| [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) · Zbl 1221.68257 |
| [6] | Chazal, F., Oudot, S.Y.: Towards persistence-based reconstruction in Euclidean spaces. In: Proce. 24th ACM Sympos. Comput. Geom. (2008, to appear). · Zbl 1271.57058 |
| [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) · Zbl 1153.68525 |
| [8] | Chazal, F., Lieutier, A.: Stability and computation of topological invariants of solids in R n. Discrete Comput. Geom. 37(4), 601–617 (2007) · Zbl 1138.68057 · doi:10.1007/s00454-007-1309-8 |
| [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) · Zbl 1297.68235 |
| [10] | Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103–120 (2007) · Zbl 1117.54027 · doi:10.1007/s00454-006-1276-5 |
| [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) · Zbl 0826.68053 · doi:10.1007/BF02574053 |
| [13] | Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533 (2002) · Zbl 1011.68152 |
| [14] | Edelsbrunner, H., Mücke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graph. 13(1), 43–72 (1994) · Zbl 0806.68107 · doi:10.1145/174462.156635 |
| [15] | Edelsbrunner, H., Shah, N.R.: Triangulating topological spaces. Int. J. Comput. Geom. Appl. 7(4), 365–378 (1997) · Zbl 0887.57028 · doi:10.1142/S0218195997000223 |
| [16] | Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) · Zbl 1044.55001 |
| [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) · Zbl 1375.68156 |
| [18] | Martinetz, T., Schulten, K.: Topology representing networks. Neural Netw. 7(3), 507–522 (1994) · doi:10.1016/0893-6080(94)90109-0 |
| [19] | Motzkin, T.S.: Beiträge zur Theorie der linearen Ungleichungen. PhD thesis, University of Basel (1933) · Zbl 0014.24601 |
| [20] | Motzkin, T.S.: Two consequences of the transposition theorem on linear inequalities. Econometrika 19, 184–185 (1951) · Zbl 0042.01201 · doi:10.2307/1905733 |
| [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) · Zbl 1148.68048 · doi:10.1007/s00454-008-9053-2 |
| [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) · Zbl 0575.68059 |
| [24] | Sugihara, K.: Laguerre voronoi diagram on the sphere. J. Geom. Graph. 6(1), 69–81 (2002) · Zbl 1009.51007 |
| [25] | Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2005) · Zbl 1069.55003 · doi:10.1007/s00454-004-1146-y |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
