Curve Reconstruction from Noisy Samples

Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-Hung Poon, Edgar Ramos


We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation in the normal directions. Our reconstruction is faithful with probability at least $1 - O(n^{-\Omega(\sqrt{\ln n}/f^2_{\max})}(f^2_{\max} + \sqrt{\ln n}))$, where $n$ is the number of noisy samples and $f_{\max}$ is the maximum local feature size. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

Computational Geometry - Theory and Applications (CGTA), Vol. 31, Issue 1-2, May 2005, p. 63-100 (invited papers from SoCG 2003)
a preliminary version appeared in Proc. 19th ACM Symposium on Computational Geometry (SoCG) 2003, San Diego
PDF