CMU Campus
Center for                           Nonlinear Analysis
CNA Home People Seminars Publications Workshops and Conferences CNA Working Groups CNA Comments Form Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses SIAM Chapter Seminar Positions Contact
Publication 16-CNA-001

Estimating Perimeter using Graph Cuts

Nicolas García Trillos
Brown University
Applied Mathematics
Providence, RI

Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213

James Von Brecht
Department of Mathematics and Statistics
California State University
Long Beach, Ca 90840, USA

Abstract: We investigate the estimation of the perimeter of a set by a graph cut of a random geometric graph. For $\Omega \subset D = (0,1)^d$, with $d \geq 2$, 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 $\epsilon>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 $D \backslash \Omega$. We obtain bias and variance estimates on the error, which are optimal in scaling with respect to $n$ and $\epsilon$. 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.

Get the paper in its entirety as  16-CNA-001.pdf

«   Back to CNA Publications