Estimating perimeter using graph cuts

DOI10.1017/APR.2017.34MaRDI QIDQ5233201zbMATH OpenOpenAlexFDO

Authors Nicolás García Trillos, Dejan Slepčev, James H. von Brecht

Publication date 16 September 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.04102

zbMATH Keywords

nonparametric estimationconcentration inequalityperimeterrandom geometric graphpoint cloudgraph cut

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Geometric probability and stochastic geometry (60D05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate the estimation of the perimeter of a set by a graph cut of a random geometric graph. For $OmegasubsetD=(0,1{)}^d$, with $dgeq2$, we are given $n$ random i.i.d. points on $D$ whose membership in $Omega$ is known. We consider the sample as a random geometric graph with connection distance $varepsilon>0$. We estimate the perimeter of $Omega$ (relative to $D$) by the, appropriately rescaled, graph cut between the vertices in $Omega$ and the vertices in $$. We obtain bias and variance estimates on the error, which are optimal in scaling with respect to $n$ and $varepsilon$. We consider two scaling regimes: the dense (when the average degree of the vertices goes to $infty$) and the sparse one (when the degree goes to $0$). In the dense regime there is a crossover in the nature of approximation at dimension $d=5$: we show that in low dimensions $d=2,3,4$ one can obtain confidence intervals for the approximation error, while in higher dimensions one can only obtain error estimates for testing the hypothesis that the perimeter is less than a given number.

Recommendations

• Algorithm to estimate the perimeter of a plane figure from its discretized image
• Convex-set perimeter estimation from its two projections
• Balanced Cut Approximation in Random Geometric Graphs
• Balanced cut approximation in random geometric graphs
• Optimal Cheeger cuts and bisections of random geometric graphs

Cites work

• scientific article; zbMATH DE number 44375 (Why is no real title available?)
• scientific article; zbMATH DE number 491591 (Why is no real title available?)
• scientific article; zbMATH DE number 1552476 (Why is no real title available?)
• scientific article; zbMATH DE number 1448982 (Why is no real title available?)
• A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
• A nonparametric approach to the estimation of lengths and surface areas
• Consistency of Cheeger and ratio graph cuts
• Continuum limit of total variation on point clouds
• Heat flow and a faster algorithm to compute the surface area of a convex body
• Length and surface area estimation under smoothness restrictions
• Nonparametric estimation of boundary measures and related functionals: asymptotic results
• Nonparametric estimation of surface integrals
• On clusterings: good, bad and spectral
• Probability Inequalities for Sums of Bounded Random Variables
• Testing problems with sublearning sample complexity
• Testing surface area
• Testing surface area with arbitrary accuracy
• The normalized graph cut and Cheeger constant: from discrete to continuous
• Towards a universally consistent estimator of the Minkowski content

Cited in

(8)

• Lipschitz regularity of graph Laplacians on random data clouds
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Nonparametric estimation of surface integrals on level sets
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Consistent Dynamics of Stripes Formed by Cell-Type Interfaces
• Rates of convergence for Laplacian semi-supervised learning with low labeling rates
• Algorithm to estimate the perimeter of a plane figure from its discretized image
• Optimal Cheeger cuts and bisections of random geometric graphs

This page was built for publication: Estimating perimeter using graph cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233201)