On the behavior of 1-Laplacian ratio cuts on nearly rectangular domains

摘要

The p-Laplacian has attracted more and more attention in data analysis disciplines in the past decade. However, there is still a knowledge gap about its behavior, which limits its practical application. In this paper, we are interested in its iterative behavior in domains contained in two-dimensional Euclidean space. Given a connected set Ω_0 ? R~2, define a sequence of sets (Ω_n)_(n=0)~∞ where Ω_(n+1) is the subset of Ω_n where the first eigenfunction of the (properly normalized) Neumann p-Laplacian -Δ~((p))φ = λ_1|φ|~(p-2)φ is positive (or negative). For p = 1, this is also referred to as the ratio cut of the domain. We conjecture that these sets converge to the set of rectangles with eccentricity bounded by 2 in the Gromov-Hausdorff distance as long as they have a certain distance to the boundary ?Ω_0. We establish some aspects of this conjecture for p = 1 where we prove that (1) the 1-Laplacian spectral cut of domains sufficiently close to rectangles is a circular arc that is closer to flat than the original domain (leading eventually to quadrilaterals) and (2) quadrilaterals close to a rectangle of aspect ratio 2 stay close to quadrilaterals and move closer to rectangles in a suitable metric. We also discuss some numerical aspects and pose many open questions.