A Cheeger set C of a given domain D is a subset of D that minimizes Perimeter(D)/Area(D). While such a set is not unique for a general non-convex domain D, it is possible to define and study a maximal Cheeger set. This maximal Cheeger set finds applications in landslide modeling and segmentation in computer vision. Using a projection on functions of bounded total variation, it is possible to approximate this maximal Cheeger. An iterative algorithm computes numerically this approximate Cheeger. This notion of maximal Cheeger can be extended to handle a weighted perimeter and a weighted area.

 

Here are the papers describing the extraction of the maximal Cheeger set in theory and in practice:

• On the selection of maximal Cheeger sets, [PDF]
  Giuseppe Buttazzo, Guillaume Carlier, Myriam Comte,
  Differential and Integral Equations, 20, no 9, pp. 991-1004 (2007).
• On a weighted total variation minimization problem, [PDF]
  Guillaume Carlier, Myriam Comte,
  J. Funct. Anal., 250, pp. 214-226 (2007)
• Approximation of Maximal Cheeger Sets by Projection, [PDF]
  Guillaume Carlier, Myriam Comte, Gabriel Peyré,
  ESAIM: Mathematical Modelling and Numerical Analysis, Vol. 43(1), p.131-150, 2009.

Here is the Matlab toolbox that implements the algorithm [Matlab].

Here are some examples of Cheegers in 2D and 3D, for uniform total variation, for weighted total variation and for crystalline norms (L1 and Linf).

Original shape	L2 Cheeger	L1 Cheeger	Linf Cheeger
Original shape	L2 Cheeger	L1 Cheeger	Linf Cheeger

Original shape	L2 Cheeger

The original shape is composed of two rectangles linked with a tube of increasing width. The corresponding Cheeger sets are displayed on the right.

Cheeger sets in a 2D square several non-constant weights for the perimeter.