Constructing Laplace operator from point clouds in Rd

ABSTRACT

We present an algorithm for approximating the Laplace-Beltrami operator from an arbitrary point cloud obtained from a k-dimensional manifold embedded in the d-dimensional space. We show that this PCD Laplace (Point-Cloud Data Laplace) operator converges to the Laplace-Beltrami operator on the underlying manifold as the point cloud becomes denser. Unlike the previous work, we do not assume that the data samples are independent identically distributed from a probability distribution and do not require a global mesh. The resulting algorithm is easy to implement. We present experimental results indicating that even for point sets sampled from a uniform distribution, PCD Laplace converges faster than the weighted graph Laplacian. We also show that using our PCD Laplacian we can directly estimate certain geometric invariants, such as manifold area.

REFERENCES

• 1: S. N. Afriat. Orthogonal and oblique projectors and the characteristics of pairs of vector spaces. Proc. Cambridge Philos. Soc., 53:800--816, 1957.
• 2: N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. Discr. Comput. Geom., 22:481--504, 1999.
• 3: N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. & Applications, 12:125--141, 2002.
• 4: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 5: M. Belkin and P. Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. In COLT, pages 486--500, 2005.
• 6: M. Belkin and P. Niyogi. Convergence of Laplacian Eigenmaps. Preprint, 2008.
• 7: Mikhail Belkin , Jian Sun , Yusu Wang, Discrete laplace operator on meshed surfaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377725]
• 8: Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Y. Oudot, Manifold reconstruction in arbitrary dimensions using witness complexes, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247106]
• 9: M. Craioveanu, M. Puta, and T. Rassias. Old and new aspects in spectral geometry in Mathematics and applications. Springer, 2001.
• 10: L. Demanet. Painless, highly accurate discretizations of the Laplacian on a smooth manifold. Technical report, Stanford University, 2006.
• 11: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 12: Joachim Giesen , Uli Wagner, Shape dimension and intrinsic metric from samples of manifolds with high co-dimension, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777841]
• 13: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 14: K. Hildebrandt, K. Polthier, and M. Wardetzky. On the convergence of metric and geometric properties of polyhedral surfaces. Geometriae Dedicata, 123(1):89--112, December 2006.
• 15: S. Lafon. Diffusion Maps and Geodesic Harmonics. PhD. Thesis, Yale University, 2004.
• 16: Z. Lu, M. C. Perpinan, and C. Sminchisescu. People Tracking with the Laplacian Eigenmaps Latent Variable Model. In Advances in Neural Information Processing Systems, 2007.
• 17: U. F. Mayer. Numerical solutions for the surface diffusion flow in three space dimensions. comput. Appl. Math, 20(3):361--379, 2001.
• 18: Partha Niyogi , Stephen Smale , Shmuel Weinberger, Finding the Homology of Submanifolds with High Confidence from Random Samples, Discrete & Computational Geometry, v.39 n.1, p.419-441, March 2008 [doi>10.1007/s00454-008-9053-2]
• 19: M. Ovsjanikov, J. Sun, and L. J. Guibas. Global intrinsic symmetries of shapes. In SGP to appear, 2008.
• 20: U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1):15--36, 1993.
• 21: M. Reuter, F.-E. Wolter, and N. Peinecke. Laplace-Beltrami spectra as "Shape-DNA" of surfaces and solids. Computer-Aided Design, 38(4):342--366, 2006.
• 22: S. Rosenberg. The Laplacian on a Riemannian Manifold: An Introduction to Analysis on Manifolds. Cambridge University Press, 1997.
• 23: Raif M. Rustamov, Laplace-Beltrami eigenfunctions for deformation invariant shape representation, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 24: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 25: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 26: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 27: Guoliang Xu, Discrete Laplace-Beltrami operators and their convergence, Computer Aided Geometric Design, v.21 n.8, p.767-784, October 2004 [doi>10.1016/j.cagd.2004.07.007]
• 28: Guoliang Xu, Convergence analysis of a discretization scheme for Gaussian curvature over triangular surfaces, Computer Aided Geometric Design, v.23 n.2, p.193-207, February 2006 [doi>10.1016/j.cagd.2005.07.002]
• 29: Z. Xu, G. Xu, and J.-G. Sun. Convergence analysis of discrete differential geometry operators over surfaces. In IMA Conference on the Mathematics of Surfaces, pages 448--457, 2005.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General