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 TrillosBrown University Applied Mathematics Providence, RInicolas_garcia_trillos@brown.edu Dejan SlepčevDepartment of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213slepcev@andrew.cmu.edu James Von BrechtDepartment of Mathematics and Statistics California State University Long Beach, Ca 90840, USAjames.vonbrecht@csulb.eduAbstract: 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