The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
Ery Arias-Castro, Bruno Pelletier, Pierre Pudlo · Advances in Applied Probability · 2012
LetMbe a bounded domain of with a smooth boundary. We relate the Cheeger constant ofMand the conductance of a neighborhood graph defined on a random sample fromM. By restricting the minimization defining the latter over a particular class of subsets, we obtain consistency (after normalization) as the sample size increases, and show that any minimizing sequence of subsets has a subsequence converging to a Cheeger set ofM.