Publication 16-CNA-001
Estimating Perimeter using Graph Cuts
Nicolas García Trillos
Brown University
Applied Mathematics
Providence, RI
nicolas_garcia_trillos@brown.edu
Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
slepcev@andrew.cmu.edu
James Von Brecht
Department of Mathematics and Statistics
California State University
Long Beach, Ca 90840, USA
james.vonbrecht@csulb.edu
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
