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