Abstract
Delaunay has shown that the Delaunay complex of a finite set of points \(P\) of Euclidean space \(\mathbb {R}^m\) triangulates the convex hull of \(P,\) provided that \(P\) satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on \(P\) are required. A natural one is to assume that \(P\) is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
This is standard folklore. We are not aware of a published reference.
References
Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Boissonnat, J.-D., Dyer, R., Ghosh, A.: The stability of Delaunay triangulations. Int. J. Comput. Geom. Appl. 23(4–5), 303–333 (2013)
Boissonnat, J.-D., Dyer, R., Ghosh, A.: Delaunay triangulation of manifolds. Found. Comput. Math. doi:10.1007/s10208-017-9344-1 (2017)
Boissonnat, J.-D., Guibas, L.J., Oudot, S.Y.: Manifold reconstruction in arbitrary dimensions using witness complexes. Discret. Comput. Geom. 42(1), 37–70 (2009)
Boissonnat, J.-D., Nielsen, F., Nock, R.: Bregman Voronoi diagrams. Discret. Comput. Geom. 44(2), 281–307 (2010)
Cairns, S.S.: A simple triangulation method for smooth manifolds. Bull. Am. Math. Soc. 67(4), 389–390 (1961)
Canas, G.D., Gortler, S.J.: Duals of orphan-free anisotropic Voronoi diagrams are embedded meshes. In: Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG’12), pp. 219–228. ACM, New York (2012)
Canas, G.D., Gortler, S.J.: On the embeddability of Delaunay triangulations in anisotropic, normed, and Bregman spaces. arXiv:1512.03589 (2015)
Chavel, I.: Riemannian Geometry: A Modern Introduction. Cambridge Studies in Advanced Mathematics, vol. 98, 2nd edn. Cambridge University Press, Cambridge (2006)
Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05), pp. 1018–1027. SIAM, Philadelphia (2005)
Clarkson, K.L.: Building triangulations using epsilon-nets. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC’06), pp. 326–335. ACM, New York (2006)
de Laat, D.: Approximating manifolds by meshes: asymptotic bounds in higher codimension. Master’s Thesis, University of Groningen, Groningen (2011)
Delaunay, B.: Sur la sphère vide. Bull. Acad. Sci. URSS Cl. Sci. Technol. 6, 793–800 (1934)
Dyer, R., Zhang, H., Möller, T.: Surface sampling and the intrinsic Voronoi diagram. Comput. Graph. Forum 27(5), 1393–1402 (2008)
Leibon, G.D.: Random Delaunay triangulations, the Thurston–Andreev theorem, and metric uniformization. PhD Thesis, University of California, San Diego (1999). arXiv:math/0011016v1
Leibon, G., Letscher, D.: Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In: Proceedings of the 16th Annual Symposium on Computational Geometry (SoCG’00), pp. 341–349. ACM, New York (2000)
Acknowledgements
We thank Gert Vegter for suggesting that we look for an obstruction that can exist at all scales. We also thank David Cohen-Steiner and Mathijs Wintraecken for illuminating discussions. This research has been partially supported by the 7th 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.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in charge: Kenneth Clarkson
Rights and permissions
About this article
Cite this article
Boissonnat, JD., Dyer, R., Ghosh, A. et al. An Obstruction to Delaunay Triangulations in Riemannian Manifolds. Discrete Comput Geom 59, 226–237 (2018). https://doi.org/10.1007/s00454-017-9908-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-017-9908-5