Computer Graphics

University of California - Berkeley

Provably Good Moving Least Squares

Download Paper
Download Bibtex


  • Ravi Kolluri


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.

Supplemental Material

Talk slides from SODA 2005.