Delaunay triangulation of manifolds. (English) Zbl 1395.57032
This paper is part of a series devoted to reconstruction and triangulation of manifolds from a finite sample [J.-D. Boissonnat et al., Int. J. Comput. Geom. Appl. 24, No. 2, 125–152 (2014; Zbl 1319.68226); Comput. Geom. 66, 32–67 (2017; Zbl 1387.68243); Discrete Comput. Geom. 59, No. 1, 226–237 (2018 Zbl 1384.52013)]. The input of the presented algorithm is a set of points in a suitable atlas of a given manifold. The conditions are reasonable and very carefully stated. By playing on a (far from trivial) perturbation of points, a new set free from “forbidden configurations” is obtained. A Delaunay simplicial complex is built; if the given manifold is Riemannian, a natural homeomorphism with the complex is granted. The algorithm and the properties are described in extreme detail.
Reviewer: Massimo Ferri (Bologna)
MSC:
| 57R05 | Triangulating |
| 52B70 | Polyhedral manifolds |
| 54B15 | Quotient spaces, decompositions in general topology |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | N. Amenta, M. Bern. Surface reconstruction by Voronoi filtering. Discrete and Computational Geometry, 22(4):481-504, 1999. · Zbl 0939.68138 · doi:10.1007/PL00009475 |
| [2] | A. I. Bobenko, B. A. Springborn. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete and Computational Geometry, 38(4):740-756, 2007. · Zbl 1144.65011 · doi:10.1007/s00454-007-9006-1 |
| [3] | J.-D. Boissonnat, R. Dyer, A. Ghosh. Constructing intrinsic Delaunay triangulations of submanifolds. Research Report RR-8273, INRIA, 2013. arXiv:1303.6493. · Zbl 0939.68138 |
| [4] | J.-D. Boissonnat, R. Dyer, A. Ghosh. The stability of Delaunay triangulations. Int. J. Comp. Geom. & Appl., 23(04n05):303-333, 2013. arXiv:1304.2947. · Zbl 1297.68231 |
| [5] | J.-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay stability via perturbations. Int. J. Comp. Geom. & Appl., 24(2):125-152, 2014. arXiv:1310.7696. · Zbl 1319.68226 |
| [6] | J.-D. Boissonnat, A. Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete and Computational Geometry, 51(1):221-267, 2014. · Zbl 1312.68209 · doi:10.1007/s00454-013-9557-2 |
| [7] | J.-D. Boissonnat, C. Wormser, M. Yvinec. Anisotropic Delaunay mesh generation. SIAM J. Comput., 44(2):467-512, 2015. · Zbl 1329.68259 |
| [8] | W. M. Boothby. An Introduction to Differentiable Manifolds and Riemannian Geometry. Academic Press, Orlando, Florida, second edition, 1986. · Zbl 0596.53001 |
| [9] | G. D. Cañas, S. J. Gortler. Duals of orphan-free anisotropic Voronoi diagrams are embedded meshes. In SoCG, pages 219-228, New York, NY, USA, 2012. ACM. · Zbl 1293.68283 |
| [10] | S.-W. Cheng, T. K. Dey, E. A. Ramos. Manifold reconstruction from point samples. In SODA, pages 1018-1027, 2005. · Zbl 1297.68235 |
| [11] | B. Delaunay. Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7:793-800, 1934. · Zbl 0010.41101 |
| [12] | R. Dyer. Self-Delaunay meshes for surfaces. PhD thesis, Simon Fraser University, Burnaby, Canada, 2010. |
| [13] | R. Dyer, G. Vegter, M. Wintraecken. Riemannian simplices and triangulations. Geometriae Dedicata, 179(1):91-138, 2015. · Zbl 1333.57036 · doi:10.1007/s10711-015-0069-5 |
| [14] | R. Dyer, H. Zhang, T. Möller. Surface sampling and the intrinsic Voronoi diagram. Computer Graphics Forum (Special Issue of Symp. Geometry Processing), 27(5):1393-1402, 2008. · doi:10.1111/j.1467-8659.2008.01279.x |
| [15] | A. N. Hirani, K. Kalyanaraman, E. B. VanderZee. Delaunay Hodge star. Computer-Aided Design, 45(2):540-544, 2012. · doi:10.1016/j.cad.2012.10.038 |
| [16] | D. Jiménez, G. Petrova. On matching point configurations. Preprint accessed 2013.05.17: http://www.math.tamu.edu/ gpetrova/JP.pdf, 2013. · Zbl 1469.65063 |
| [17] | F. Labelle, J. R. Shewchuk. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SoCG, pages 191-200, 2003. · Zbl 1375.68154 |
| [18] | G. Leibon. Random Delaunay triangulations, the Thurston-Andreev theorem, and metric uniformization. PhD thesis, UCSD, 1999. arXiv:math/0011016v1. · Zbl 0939.68138 |
| [19] | G. Leibon, D. Letscher. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In SoCG, pages 341-349, 2000. · Zbl 1375.68156 |
| [20] | W. P. Thurston. Three-Dimensional Geometry and Topology. Princeton University Press, 1997. · Zbl 0873.57001 |
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.
