Approximation of maximal Cheeger sets by projection
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 43 (2009) no. 1, p. 139-150

This article deals with the numerical computation of the Cheeger constant and the approximation of the maximal Cheeger set of a given subset of d . This problem is motivated by landslide modelling as well as by the continuous maximal flow problem. Using the fact that the maximal Cheeger set can be approximated by solving a rather simple projection problem, we propose a numerical strategy to compute maximal Cheeger sets and Cheeger constants.

DOI : https://doi.org/10.1051/m2an/2008040
Classification:  49Q10,  65K10
Keywords: Cheeger sets, Cheeger constant, total variation minimization, projections
@article{M2AN_2009__43_1_139_0,
     author = {Carlier, Guillaume and Comte, Myriam and Peyr\'e, Gabriel},
     title = {Approximation of maximal Cheeger sets by projection},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     pages = {139-150},
     doi = {10.1051/m2an/2008040},
     zbl = {1161.65046},
     mrnumber = {2494797},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2009__43_1_139_0}
}
Carlier, Guillaume; Comte, Myriam; Peyré, Gabriel. Approximation of maximal Cheeger sets by projection. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 43 (2009) no. 1, pp. 139-150. doi : 10.1051/m2an/2008040. http://www.numdam.org/item/M2AN_2009__43_1_139_0/

[1] F. Alter and V. Caselles, Uniqueness of the Cheeger set of a convex body. Preprint (2007) available at http://cvgmt.sns.it. | MR 2358032 | Zbl 1167.52005

[2] F. Alter, V. Caselles and A. Chambolle, Evolution of characteristic functions of convex sets in the plane by the minimizing total variation flow. Interfaces Free Bound. 7 (2005) 29-53. | MR 2126142 | Zbl 1084.49003

[3] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs. Oxford University Press, New York (2000). | MR 1857292 | Zbl 0957.49001

[4] B. Appleton and H. Talbot, Globally minimal surfaces by continuous maximal flows. IEEE Trans. Pattern Anal. Mach. Intell. 28 (2006) 106-118.

[5] G. Bellettini, V. Caselles, A. Chambolle and M. Novaga, Crystalline mean curvature flow of convex sets. Arch. Ration. Mech. Anal. 179 (2006) 109-152. | MR 2208291 | Zbl 1148.53049

[6] G. Buttazzo, G. Carlier and M. Comte, On the selection of maximal Cheeger sets. Differential Integral Equations 20 (2007) 991-1004. | MR 2349376

[7] G. Carlier and M. Comte, On a weighted total variation minimization problem. J. Funct. Anal. 250 (2007) 214-226. | MR 2345913 | Zbl 1120.49011

[8] V. Caselles, A. Chambolle and M. Novaga, Uniqueness of the Cheeger set of a convex body. Pacific J. Math. 232 (2007) 77-90. | MR 2358032 | Zbl pre05366256

[9] A. Chambolle, An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis. J. Math. Imaging Vision 20 (2004) 89-97. | MR 2049783

[10] A. Chambolle and P.-L. Lions, Image recovery via total variation minimization. Numer. Math. 76 (1997) 167-188. | MR 1440119 | Zbl 0874.68299

[11] P.-L. Combettes, A block-iterative surrogate constraint splitting method for quadratic signal recovery. IEEE Trans. Signal Process. 51 (2003) 1771-1782. | MR 1996963

[12] P.-L. Combettes and J.-C. Pesquet, image restoration subject to a total variation constraint. IEEE Trans. Image Process. 13 (2004) 1213-1222.

[13] N. Cristescu, A model of stability of slopes in Slope Stability 2000, in Proceedings of Sessions of Geo-Denver 2000, D.V. Griffiths, G.A. Fenton, T.R. Martin Eds., Geotechnical special publication 101 (2000) 86-98.

[14] F. Demengel, Théorèmes d’existence pour des équations avec l’opérateur “1-Laplacien”, première valeur propre de -Δ 1 . C. R. Math. Acad. Sci. Paris 334 (2002) 1071-1076. | MR 1911649 | Zbl 1142.35408

[15] F. Demengel, Some existence's results for noncoercive “1-Laplacian” operator. Asymptotic Anal. 43 (2005) 287-322. | MR 2160702 | Zbl 1192.35036 | Zbl pre02215157

[16] G. Duvaut and J.-L. Lions, Les inéquations en mécanique et en physique. Dunod, Paris (1972). | MR 464857 | Zbl 0298.73001

[17] I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Classics in Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (1999). | MR 1727362 | Zbl 0939.49002

[18] L.C. Evans and R. Gariepy, Measure Theory and Fine Properties of Functions. CRC Press (1992). | MR 1158660 | Zbl 0804.28001

[19] R. Hassani, I.R. Ionescu and T. Lachand-Robert, Shape optimization and supremal minimization approaches in landslides modeling. Appl. Math. Opt. 52 (2005) 349-364. | MR 2174019 | Zbl 1081.49030

[20] P. Hild, I.R. Ionescu, T. Lachand-Robert and I. Rosca, The blocking of an inhomogeneous Bingham fluid. Applications to landslides. ESAIM: M2AN 36 (2002) 1013-1026. | Numdam | MR 1958656 | Zbl 1057.76004

[21] I.R. Ionescu and T. Lachand-Robert, Generalized Cheeger sets related to landslides. Calc. Var. Partial Differential Equations 23 (2005) 227-249. | MR 2138084 | Zbl 1062.49036

[22] R. Nozawa, Max-flow min-cut theorem in an anisotropic network. Osaka J. Math. 27 (1990) 805-842. | MR 1088184 | Zbl 0723.90020

[23] L.I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Physica D 60 (1992) 259-268. | Zbl 0780.49028

[24] G. Strang, Maximal flow through a domain. Math. Programming 26 (1983) 123-143. | MR 700642 | Zbl 0513.90026

[25] G. Strang, Maximum flows and minimum cuts in the plane. J. Global Optimization (to appear). | MR 2490506 | Zbl 1192.49050