In this paper, we give a new characterization of the cut locus of a point on a compact Riemannian manifold as the zero set of the optimal transport density solution of the Monge–Kantorovich equations, a PDE formulation of the optimal transport problem with cost equal to the geodesic distance. Combining this result with an optimal transport numerical solver, based on the so-called dynamical Monge–Kantorovich approach, we propose a novel framework for the numerical approximation of the cut locus of a point in a manifold. We show the applicability of the proposed method on a few examples settled on 2d-surfaces embedded in ℝ3, and discuss advantages and limitations.
Keywords: Cut locus, Riemannian geometry, Optimal Transport problem, Monge–Kantorovich equations, geodesic distance
@article{M2AN_2022__56_6_1939_0,
author = {Facca, Enrico and Berti, Luca and Fass\`o, Francesco and Putti, Mario},
title = {Computing the cut locus of a {Riemannian} manifold \protect\emph{via} optimal transport},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {1939--1954},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {6},
doi = {10.1051/m2an/2022059},
mrnumber = {4481118},
language = {en},
url = {https://www.numdam.org/articles/10.1051/m2an/2022059/}
}
TY - JOUR AU - Facca, Enrico AU - Berti, Luca AU - Fassò, Francesco AU - Putti, Mario TI - Computing the cut locus of a Riemannian manifold via optimal transport JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2022 SP - 1939 EP - 1954 VL - 56 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/m2an/2022059/ DO - 10.1051/m2an/2022059 LA - en ID - M2AN_2022__56_6_1939_0 ER -
%0 Journal Article %A Facca, Enrico %A Berti, Luca %A Fassò, Francesco %A Putti, Mario %T Computing the cut locus of a Riemannian manifold via optimal transport %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2022 %P 1939-1954 %V 56 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/m2an/2022059/ %R 10.1051/m2an/2022059 %G en %F M2AN_2022__56_6_1939_0
Facca, Enrico; Berti, Luca; Fassò, Francesco; Putti, Mario. Computing the cut locus of a Riemannian manifold via optimal transport. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 56 (2022) no. 6, pp. 1939-1954. doi: 10.1051/m2an/2022059
[1] , On the stability of the cut locus. Nonlinear Anal. Theory Methods Appl. 136 (2016) 51–61. | MR | DOI
[2] , Lecture notes on optimal transport problems. In: Lecture Notes in Mathematics. Springer, Berlin, Heidelberg (2003) 1–52. | MR | Zbl
[3] and , Geometrically intrinsic modeling of shallow water flows. ESAIM: Math. Model. Num. Anal. 54 (2020) 2125–2157. | MR | Numdam | DOI
[4] , and , Numerical solution of the L1-optimal transport problem on surfaces. Preprint (2021). | arXiv
[5] , A derivation of -dimensional spherical coordinates. Am. Math. Mon. 67 (1960) 63–66. | MR | DOI
[6] , , and , Conjugate and cut loci of a two-sphere of revolution with application to optimal control. Ann. Inst. H. Poincaré Anal. Non Linéaire 26 (2009) 1081–1098. | MR | Zbl | Numdam | DOI
[7] , and , Geometric and Numerical Techniques to Compute Conjugate and Cut Loci on Riemannian Surfaces. Springer International Publishing, Cham (2014) 53–72. | MR | Zbl
[8] and , Characterization of optimal shapes and masses through Monge–Kantorovich equation. J. Eur. Math. Soc. 3 (2001) 139–168. | MR | Zbl | DOI
[9] and , On regularity of transport density in the Monge–Kantorovich problem. SIAM J. Control Optim. 42 (2003) 1044–1055. | MR | Zbl | DOI
[10] , and , ct: control toolbox – numerical tools and examples in optimal control. Working paper or preprint (Feb. 2022). | HAL
[11] , Riemannian Geometry: A Modern Introduction. Cambridge Studies in Advanced Mathematics, 2nd edition. Cambridge University Press (2006). | MR | Zbl
[12] , and , Geodesics in heat: a new approach to computing distance based on heat flow. ACM Trans. Graph. 32 (2013) 1–11. | DOI
[13] , and , Integral estimates for transport densities. Bull. London Mat. Soc. 36 (2004) 383–395. | MR | Zbl | DOI
[14] and , Cut locus and topology from surface point data. In: Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry (2009) 125–134.
[15] and , Finite element methods for surface pdes. Acta Num. 22 (2013) 289–396. | MR | Zbl | DOI
[16] and , Differential Equations Methods for the Monge–Kantorovich Mass Transfer Problem. Vol. 653. American Mathematical Soc. (1999). | MR | Zbl
[17] and , Fast iterative solution of the optimal transport problem on graphs. SIAM J. Sci. Comput. 43 (2021) A2295–A2319. | MR | DOI
[18] , and , Towards a stationary Monge–Kantorovich dynamics: the physarum polycephalum experience. SIAM J. Appl. Math. 78 (2018) 651–676. | MR | DOI
[19] , , and , Numerical solution of Monge–Kantorovich equations via a dynamic formulation. J. Sci. Comput. 82 (2020) 1–26. | MR | DOI
[20] , and , transport energy. Appl. Math. Optim. 86 (2022) 1–40. | MR | DOI
[21] and , Monge’s transport problem on a riemannian manifold. Trans. Amer. Math. Soc. 354 (2001) 1667–1697. | MR | Zbl | DOI
[22] and , Uniqueness and transport density in monge’s mass transportation problem. Calc. Var. Part. Diff. Equ. 15 (2002) 81–113. | MR | Zbl | DOI
[23] and , Mass transportation on sub-riemannian manifolds. Geom. Funct. Anal. 20 (2010) 124–159. | MR | Zbl | DOI
[24] and , An approximation lemma about the cut locus, with applications in optimal transport theory. Methods App. Anal. 15 (2008) 149–154. | MR | Zbl | DOI
[25] , and , Tangent cut loci on surfaces. Differ. Geom. Appl. 29 (2011) 154–159. | MR | Zbl | DOI
[26] , and , Cut locus on compact manifolds and uniform semiconcavity estimates for a variational inequality. Preprint (2020). | arXiv | MR
[27] , and , Numerical computation of the cut locus via a variational approximation of the distance function. ESAIM: Math. Model. Num. Anal. 56 (2022) 105–120. | MR | Zbl | Numdam | DOI
[28] , , and , The cut locus of a torus of revolution. Asian J. Math. 9 (2005) 103–120. | MR | Zbl | DOI
[29] and , The cut loci and the conjugate loci on ellipsoids. Manuscr. Math. 114 (2004) 247–264. | MR | Zbl
[30] and , Thaw: a tool for approximating cut loci on a triangulation of a surface. Exp. Math. 13 (2004) 309–325. | MR | Zbl | DOI
[31] and , The Lipschitz continuity of the distance function to the cut locus. Trans. Amer. Math. Soc. 353 (2001) 21–40. | MR | Zbl | DOI
[32] , Riemannian Geometry and Geometric Analysis. Vol. 42005, Springer (2008). | MR | Zbl
[33] , Geodesics on a toroid. Am. J. Math. 52 (1930) 29–52. | MR | JFM | DOI
[34] , and , Practical computation of the cut locus on discrete surfaces. Comput. Graph Forum 40 (2021) 261–273. | DOI
[35] and , Hamilton-Jacobi equations and distance functions on Riemannian manifolds. Appl. Math. Optim. 47 (2003) 1–25. | MR | Zbl | DOI
[36] , , and , Cut locus construction using deformable simplicial complexes. In: 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD). IEEE (2011) 134–141. | DOI
[37] , Generalized Curvatures. Vol. 2 of Geometry and Computing. Springer Science & Business Media, Berlin, Heidelberg (2008). | MR | Zbl
[38] and , A simple mesh generator in Matlab. SIAM Rev. 46 (2004) 329–345. | MR | Zbl | DOI
[39] , Equivalence between some definitions for the optimal mass transport problem and for the transport density on manifolds. Ann. Mat. Pura App. 184 (2005) 215–238. | MR | Zbl | DOI
[40] , Riemannian Geometry. Vol. 149, American Mathematical Society (1996). | MR | Zbl | DOI
[41] , Absolute continuity and summability of transport densities: simpler proofs and new estimates. Calc. Var. Part. Diff. Equ. 36 (2009) 343–354. | MR | Zbl | DOI
[42] , Optimal Transport for Applied Mathematicians. Birkäuser, NY (2015). | MR | DOI
[43] and , Loki: software for computing cut loci. Exp. Math. 11 (2002) 1–25. | MR | Zbl | DOI
[44] and , Regularization techniques for numerical approximation of PDEs with singularities. J. Scient. Comput. 19 (2003) 527–552. | MR | Zbl | DOI
[45] and , Numerical approximations of singular source terms in differential equations. J. Comp. Phys. 200 (2004) 462–488. | MR | Zbl | DOI
[46] , Topics in Optimal Transportation. Vol. 58 of Graduate Studies in Mathematics. American Mathematical Society (2003). | MR | Zbl
[47] , Optimal Transport: Old and New. Vol. 338, Springer Science & Business Media (2008). | MR | Zbl
[48] , Regularity of optimal transport and cut locus: from nonsmooth analysis to geometry to smooth analysis. Discrete Contin. Dyn. Syst. Ser. A 30 (2011) 559–571. | MR | Zbl | DOI
Cité par Sources :
