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
Nicolas García Trillos Dejan Slepčev James Von Brecht 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 |