Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-23T06:44:26.232Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximation of maximal Cheeger sets by projection

Published online by Cambridge University Press:  16 October 2008

Guillaume Carlier ,
Myriam Comte  and
Gabriel Peyré
Guillaume Carlier
Affiliation:
CEREMADE, Université Paris Dauphine, France. [email protected]; [email protected]
Myriam Comte
Affiliation:
Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie, France. [email protected]
Gabriel Peyré
Affiliation:
CEREMADE, Université Paris Dauphine, France. [email protected]; [email protected]
Get access

Abstract

This article deals with the numerical computation of the Cheeger constant and the approximation of the maximal Cheeger set of a given subset of ${\mathbb R}^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.

Keywords

Cheeger setsCheeger constanttotal variation minimizationprojections.
Type
Research Article
Information
ESAIM: Mathematical Modelling and Numerical Analysis , Volume 43 , Issue 1 , January 2009 , pp. 139 - 150
Copyright
© EDP Sciences, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

F. Alter and V. Caselles, Uniqueness of the Cheeger set of a convex body. Preprint (2007) available at http://cvgmt.sns.it.
Alter, F., Caselles, V. and Chambolle, A., Evolution of characteristic functions of convex sets in the plane by the minimizing total variation flow. Interfaces Free Bound. 7 (2005) 29–53. CrossRef
L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs. Oxford University Press, New York (2000).
Appleton, B. and Talbot, H., Globally minimal surfaces by continuous maximal flows. IEEE Trans. Pattern Anal. Mach. Intell. 28 (2006) 106–118. CrossRef
Bellettini, G., Caselles, V., Chambolle, A. and Novaga, M., Crystalline mean curvature flow of convex sets. Arch. Ration. Mech. Anal. 179 (2006) 109–152. CrossRef
Buttazzo, G., Carlier, G. and Comte, M., On the selection of maximal Cheeger sets. Differential Integral Equations 20 (2007) 991–1004.
Carlier, G. and Comte, M., On a weighted total variation minimization problem. J. Funct. Anal. 250 (2007) 214–226. CrossRef
Caselles, V., Chambolle, A. and Novaga, M., Uniqueness of the Cheeger set of a convex body. Pacific J. Math. 232 (2007) 77–90. CrossRef
Chambolle, A., An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis. J. Math. Imaging Vision 20 (2004) 89–97. CrossRef
Chambolle, A. and Lions, P.-L., Image recovery via total variation minimization. Numer. Math. 76 (1997) 167–188. CrossRef
Combettes, P.-L., A block-iterative surrogate constraint splitting method for quadratic signal recovery. IEEE Trans. Signal Process. 51 (2003) 1771–1782. CrossRef
Combettes, P.-L. and Pesquet, J.-C., image restoration subject to a total variation constraint. IEEE Trans. Image Process. 13 (2004) 1213–1222. CrossRef
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.
Demengel, F., Théorèmes d'existence pour des équations avec l'opérateur “1-Laplacien”, première valeur propre de $-\Delta\sb 1$ . C. R. Math. Acad. Sci. Paris 334 (2002) 1071–1076. CrossRef
Demengel, F., Some existence's results for noncoercive “1-Laplacian” operator. Asymptotic Anal. 43 (2005) 287–322.
G. Duvaut and J.-L. Lions, Les inéquations en mécanique et en physique. Dunod, Paris (1972).
I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Classics in Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (1999).
L.C. Evans and R. Gariepy, Measure Theory and Fine Properties of Functions. CRC Press (1992).
Hassani, R., Ionescu, I.R. and Lachand-Robert, T., Shape optimization and supremal minimization approaches in landslides modeling. Appl. Math. Opt. 52 (2005) 349–364. CrossRef
Hild, P., Ionescu, I.R., Lachand-Robert, T. and Rosca, I., The blocking of an inhomogeneous Bingham fluid. Applications to landslides. ESAIM: M2AN 36 (2002) 1013–1026. CrossRef
Ionescu, I.R. and Lachand-Robert, T., Generalized Cheeger sets related to landslides. Calc. Var. Partial Differential Equations 23 (2005) 227–249. CrossRef
Nozawa, R., Max-flow min-cut theorem in an anisotropic network. Osaka J. Math. 27 (1990) 805–842.
Rudin, L.I., Osher, S. and Fatemi, E., Nonlinear total variation based noise removal algorithms. Physica D 60 (1992) 259–268. CrossRef
Strang, G., Maximal flow through a domain. Math. Programming 26 (1983) 123–143. CrossRef
G. Strang, Maximum flows and minimum cuts in the plane. J. Global Optimization (to appear).