Provably Good Moving Least Squares
We analyze a moving least squares algorithm for reconstructing a surface from point cloud data. Our algorithm defines an implicit function I whose zero set U is the reconstructed surface. We prove that I is a good approximation to the signed distance function of the sampled surface F and that U is geometrically close to and homeomorphic to F . Our proof requires sampling conditions similar to ε-sampling, used in Delaunay reconstruction algorithms.
This paper won the Best Student Paper Award at SODA 2005.
Ravikrishna Kolluri. "Provably Good Moving Least Squares". In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pages 1008–1018, August 2005.