Abstract
We define a discrete Laplace–Beltrami operator for simplicial surfaces (Definition 16). It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the well known finite-elements Laplacian (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic functions, discrete mean curvature, and discrete minimal surfaces. The definition of the discrete Laplace–Beltrami operator depends on the existence and uniqueness of Delaunay tessellations in piecewise flat surfaces. While the existence is known, we prove the uniqueness. Using Rippa’s Theorem we show that, as claimed, Musin’s harmonic index provides an optimality criterion for Delaunay triangulations, and this can be used to prove that the edge flipping algorithm terminates also in the setting of piecewise flat surfaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexandrov, A.D.: Convex Polyhedra. Springer Monographs in Mathematics. Springer, Berlin (2005). English translation with additional material of the 1950 Russian monograph.
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 201–290. North-Holland, Amsterdam (2000)
Bobenko, A.I., Hoffmann, T., Springborn, B.A.: Minimal surfaces from circle patterns: Geometry from combinatorics. Ann. Math. 164, 231–264 (2006)
Botsch, M., Kobbelt, L.: An intuitive framework for real time freeform modeling. ACM Trans. Graph. 23(3), 630–634 (2004)
Delaunay, B.N.: Sur la sphère vide. Izv. Akad. Nauk SSSR, Otd. Mat. Estestv. Nauk 7, 793–800 (1934)
Desbrun, M., Meyer, M., Alliez, P.: Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 209–218 (2002)
Duffin, R.J.: Distributed and lumped networks. J. Math. Mech. 8(5), 793–826 (1959)
Duffin, R.J.: Potential theory on a rhombic lattice. J. Comb. Theory 5, 258–272 (1968)
Dziuk, G.: Finite elements for the Beltrami operator on arbitrary surfaces. In: Hildebrandt, S., Leis, R. (eds.) Partial Differential Equations and Calculus of Variations. Lecture Notes in Mathematics, vol. 1357, pp. 142–155. Springer, Berlin (1988)
Edelsbrunner, H.: Geometry and Topology for Mesh Generation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2001)
Indermitte, C., Liebling, Th.M., Troyanov, M., Clemençon, H.: Voronoi diagrams on piecewise flat surfaces and an application to biological growth. Theor. Comput. Sci. 263, 263–274 (2001)
Lambert, T.: The Delaunay triangulation maximizes the mean inradius. In: Proceedings of the 6th Canadian Conference on Computational Geometry (CCCG’94), pp. 201–206 (1994)
Leibon, G., Letscher, D.: Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Hong Kong, 2000, pp. 341–349. ACM, New York (2000)
Meyer, M., Desbrun, M., Schröder, P., Barr, A.H.: Discrete differential-geometry operators for triangulated 2-manifolds. In: Hege, H.-C., Polthier, K. (eds.) Visualization and Mathematics III, pp. 35–57. Springer, Heidelberg (2003)
Mercat, C.: Discrete Riemann surfaces and the Ising model. Commun. Math. Phys. 218, 177–216 (2001)
Musin, O.: Properties of the Delaunay triangulation. In: Proceedings of the 13th Annual Symposium on Computational Geometry (SCG ’97), pp. 424–426. ACM, New York (1997)
Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2(1), 15–36 (1993)
Rippa, S.: Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Des. 7, 489–497 (1990)
Rivin, I.: Euclidean structures on simplicial surfaces and hyperbolic volume. Ann. Math. 139, 553–580 (1994)
Troyanov, M.: Les surface Euclidiennes à singularités coniques. Enseign. Math. 32, 79–94 (1986)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces” and the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.
Rights and permissions
About this article
Cite this article
Bobenko, A.I., Springborn, B.A. A Discrete Laplace–Beltrami Operator for Simplicial Surfaces. Discrete Comput Geom 38, 740–756 (2007). https://doi.org/10.1007/s00454-007-9006-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-007-9006-1