Estimating perimeter using graph cuts

DOI10.1017/APR.2017.34zbMATH Open1425.60014arXiv1602.04102OpenAlexW2963988444MaRDI QIDQ5233201FDOQ5233201

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

Publication date: 16 September 2019

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
• Continuum limit of total variation on point clouds
• The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
• A nonparametric approach to the estimation of lengths and surface areas
• On clusterings
• Length and surface area estimation under smoothness restrictions
• Testing problems with sublearning sample complexity
• Heat flow and a faster algorithm to compute the surface area of a convex body
• Nonparametric estimation of surface integrals
• Consistency of Cheeger and ratio graph cuts
• Nonparametric estimation of boundary measures and related functionals: asymptotic results
• Towards a universally consistent estimator of the Minkowski content
• Testing Surface Area
• Testing surface area with arbitrary accuracy

Cited In (8)

• 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
• Lipschitz Regularity of Graph Laplacians on Random Data Clouds
• 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)