Approximation of maximal Cheeger sets by projection
Carlier, Guillaume ; Comte, Myriam ; Peyré, Gabriel
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 43 (2009), p. 139-150 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/m2an/2008040
Classification:  49Q10,  65K10 
@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},
     volume = {43},
     year = {2009},
     pages = {139-150},
     doi = {10.1051/m2an/2008040},
     mrnumber = {2494797},
     zbl = {1161.65046},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 43 (2009) pp. 139-150. doi : 10.1051/m2an/2008040. http://gdmltest.u-ga.fr/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