Abstract
We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced for a perturbed point set provided the transition functions are bi-Lipschitz with a constant close to 1, and the original sample points meet a local density requirement; no smoothness assumptions are required. If the transition functions are smooth, the output is a triangulation of the manifold. The output complex is naturally endowed with a piecewise-flat metric which, when the original manifold is Riemannian, is a close approximation of the original Riemannian metric. In this case the output complex is also a Delaunay triangulation of its vertices with respect to this piecewise-flat metric.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A manifold simplicial complex that admits an atlas of piecewise linear coordinate charts from the stars of the vertices is called piecewise linear. There exists manifold simplical complexes that are not piecewise linear [20, Example 3.2.11].
References
N. Amenta, M. Bern. Surface reconstruction by Voronoi filtering. Discrete and Computational Geometry, 22(4):481–504, 1999.
A. I. Bobenko, B. A. Springborn. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete and Computational Geometry, 38(4):740–756, 2007.
J.-D. Boissonnat, R. Dyer, A. Ghosh. Constructing intrinsic Delaunay triangulations of submanifolds. Research Report RR-8273, INRIA, 2013. arXiv:1303.6493.
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.
J.-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay stability via perturbations. Int. J. Comp. Geom. & Appl., 24(2):125–152, 2014. arXiv:1310.7696.
J.-D. Boissonnat, A. Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete and Computational Geometry, 51(1):221–267, 2014.
J.-D. Boissonnat, C. Wormser, M. Yvinec. Anisotropic Delaunay mesh generation. SIAM J. Comput., 44(2):467–512, 2015.
W. M. Boothby. An Introduction to Differentiable Manifolds and Riemannian Geometry. Academic Press, Orlando, Florida, second edition, 1986.
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.
S.-W. Cheng, T. K. Dey, E. A. Ramos. Manifold reconstruction from point samples. In SODA, pages 1018–1027, 2005.
B. Delaunay. Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7:793–800, 1934.
R. Dyer. Self-Delaunay meshes for surfaces. PhD thesis, Simon Fraser University, Burnaby, Canada, 2010.
R. Dyer, G. Vegter, M. Wintraecken. Riemannian simplices and triangulations. Geometriae Dedicata, 179(1):91–138, 2015.
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.
A. N. Hirani, K. Kalyanaraman, E. B. VanderZee. Delaunay Hodge star. Computer-Aided Design, 45(2):540–544, 2012.
D. Jiménez, G. Petrova. On matching point configurations. Preprint accessed 2013.05.17: http://www.math.tamu.edu/~gpetrova/JP.pdf, 2013.
F. Labelle, J. R. Shewchuk. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SoCG, pages 191–200, 2003.
G. Leibon. Random Delaunay triangulations, the Thurston-Andreev theorem, and metric uniformization. PhD thesis, UCSD, 1999. arXiv:math/0011016v1.
G. Leibon, D. Letscher. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In SoCG, pages 341–349, 2000.
W. P. Thurston. Three-Dimensional Geometry and Topology. Princeton University Press, 1997.
Acknowledgements
This research has been partially supported by the Seventh Framework Programme for Research of the European Commission, under FET-Open Grant Number 255827 (CGL Computational Geometry Learning). Partial support has also been provided by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship Number SB/S2/RJN-064/2015. Part of this work was done when he was a researcher at the Max Planck Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Part of this work was also done, while he was a visiting scientist at the Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India. We gratefully profited from discussions with Mathijs Wintraeken. We also thank the reviewers for the careful reading and thoughtful comments that significantly improved the final manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Herbert Edelsbrunner.
Rights and permissions
About this article
Cite this article
Boissonnat, JD., Dyer, R. & Ghosh, A. Delaunay Triangulation of Manifolds. Found Comput Math 18, 399–431 (2018). https://doi.org/10.1007/s10208-017-9344-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-017-9344-1