Integral estimation from point cloud in d-dimensional space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Integral estimation from point cloud in d-dimensional space: a geometric view

Full text

Pdf (1.22 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the 25th annual symposium on Computational geometry table of contents

Aarhus, Denmark

SESSION: Monday, June 8 - 4:40-5:40 pm table of contents

Pages 116-124

Year of Publication: 2009

ISBN:978-1-60558-501-7

Authors

Chuanjiang Luo	The Ohio State University, Columbus, OH, USA
Jian Sun	Stanford University, Palo Alto, CA, USA
Yusu Wang	The Ohio State University, Columbus, OH, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 58, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1542362.1542389 What is a DOI?

ABSTRACT

Integration over a domain, such as a Euclidean space or a Riemannian manifold, is a fundamental problem across scientific fields. Many times, the underlying domain is only accessible through a discrete approximation, such as a set of points sampled from it, and it is crucial to be able to estimate integral in such discrete settings. In this paper, we study the problem of estimating the integral of a function defined over a k-submanifold embedded in $d$-dimensional space, from its function values at a set of sample points. Previously, such estimation is usually obtained in a statistical setting, where input data is typically assumed to be drawn from certain probabilistic distribution. Our paper is the first to consider this important problem of estimating integral from point clouds data (PCD) under the more general non-statistical setting, and provide certain theoretical guarantees. Our approaches consider the problem from a geometric point of view. Specifically, we estimate the integral by computing a weighted sum, and propose two weighting schemes: the Voronoi and the Principle Eigenvector schemes. The running time of both methods depends mostly on the intrinsic dimension of the underlying manifold, instead of on the ambient dimensions. We show that the estimation based on the Voronoi scheme converges to the true integral under the so-called (ε, δ)-sampling condition with explicit error bound presented. This is the first result of this sort for estimating integral from general PCD. For the Principle Eigenvector scheme, although no theoretical guarantee is established, we present its connection to the Heat diffusion operator, and illustrate justifications behind its construction. Experimental results show that both new methods consistently produce more accurate integral estimations than common statistical methods under various sampling conditions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22:481--504, 1999.
	2	N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. Appl., 12:125--141, 2002.
	3	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]
	4	M. Belkin and P. Niyogi. Towards a theoretical foundation for laplacian-based manifold methods. In Proc. 18th Annu. Comp. Learn. Theo., pages 486--500, 2005.
	5	M. Belkin and P. Niyogi. Convergence of Laplacian Eigenmaps. Preprint, 2008.
	6	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]
	7	Mikhail Belkin , Jian Sun , Yusu Wang, Constructing Laplace operator from point clouds in R^d, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1031-1040, January 04-06, 2009, New York, New York
	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	Siu-Wing Cheng , Man-Kwun Chiu, Dimension detection via slivers, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1001-1010, January 04-06, 2009, New York, New York
	10	S.-W. Cheng, Y. Wang, and Z. Wu. Provable dimension detection using principal component analysis. Internat. J. Comput. Geom. Appl., 18:414--440, 2008.
	11	Tamal K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
	12	Tamal K. Dey , Joachim Giesen , Samrat Goswami , Wulue Zhao, Shape dimension and approximation from samples, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.772-780, January 06-08, 2002, San Francisco, California
	13	G. Elekes. A geometric inequality and the complexity of computing volume. Discrete Comput. Geom., 1:289--292, 1986.
	14	Z Furedi , I Barany, Computing the volume is difficult, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.442-447, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12176]
	15	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]
	16	J. M. Hammersley. Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci., 86:844--874, 1960.
	17	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]
	18	A. Ihler and M. Mandel. Kernel density estimation toolbox for matlab. In http://www.ics.uci.edu/ ihler/code/.
	19	S. Lafon. Diffusion Maps and Geodesic Harmonics. Ph.D. thesis, Yale University, 2004.
	20	X. Li, W. Wang, R. R. Martin, and A. Bowyer. Using low-discrepancy sequences and the Crofton formula to compute surface areas of geometric models. Computer-Aided Design, 35(9):771--782, 2003.
	21	Y.-S. Liu, J.-H. Yong, H. Zhang, D.-M. Yan, and J.-G. Sun. A quasi-Monte Carlo method for computing areas of point-sampled surfaces. Computer-Aided Design, 38(1):55--68, 2006.
	22	S. Rosenberg. The Laplacian on a Riemannian Manifold: An Introduction to Analysis on Manifolds. Cambridge University Press, 1997.
	23	L. A. Santaló. Integral geometry. In Chern SS, editor. Studies in global geometry and analysis, pages 147--95. Washington, DC: The Press of The Mathematical Association of America, 1967.