Stability of persistence diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stability of persistence diagrams

Full text

Pdf (187 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-first annual symposium on Computational geometry table of contents

Pisa, Italy

SESSION: Geometry and topology table of contents

Pages: 263 - 271

Year of Publication: 2005

ISBN:1-58113-991-8

Authors

David Cohen-Steiner	Duke University, Durham, NC
Herbert Edelsbrunner	Duke University, Durham and Raindrop Geomagic, RTP, NC
John Harer	Duke University, Durham, NC

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): 4, Downloads (12 Months): 31, Citation Count: 18

Additional Information:

abstract references cited by 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/1064092.1064133 What is a DOI?

ABSTRACT

The persistence diagram of a real-valued function on a topological space is a multiset of points in the extended plane. We prove that under mild assumptions on the function, the persistence diagram is stable: small changes in the function imply only small changes in the diagram. We apply this result to estimating the homology of sets in a metric space and to comparing and classifying geometric shapes.

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 (1999), 481--504.
	2	F. L. Bookstein. Morphometric Tools for Landmark Data. Cambridge Univ. Press, England, 1999.
	3	Gunnar Carlsson , Afra Zomorodian , Anne Collins , Leonidas Guibas, Persistence barcodes for shapes, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057449]
	4	Afra Zomorodian , Gunnar Carlsson, Computing persistent homology, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997870]
	5	F. Chazal and A. Lieutier. Stability and homotopy of a subset of the medial axis. In "Proc. 9th Ann. ACM Sympos. Solid Modeling Appl., 2004".
	6	Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064132]
	7	David Cohen-Steiner , Herbert Edelsbrunner, Inequalities for the curvature of curves and surfaces, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064134]
	8	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	9	V. de Silva and G. Carlsson. Topological estimation using witness complexes. In "Proc. Sympos. Point-Based Graphics, 2004", 157--166.
	10	Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997867]
	11	H. Edelsbrunner, D. Letscher and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom. 28 (2002), 511--533.
	12	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
	13	J. H. G. Fu. Tubular neighborhoods in Euclidean spaces. Duke Math. J. 52 (1995), 1025--1046.
	14	M. Goresky and R. MacPherson. Stratified Morse Theory. Springer-Verlag, New York, 1988.
	15	L. Loväsz and M. D. Plummer. Matching Theory. North-Holland, Amsterdam, the Netherlands, 1986.
	16	J. Milnor. Morse Theory. Princeton Univ. Press, New Jersey, 1963.
	17	J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Redwood City, California, 1984.
	18	P. Niyogi, S. Smale and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Manuscript, Toyota Technological Institute, Chicago, Illinois, 2004.
	19	V. Robins. Toward computing homology from finite approximations. Topology Proceedings 24 (1999), 503--532.
	20	Geometric partial differential equations and image analysis, Cambridge University Press, New York, NY, 2001
	21	E. Spanier. Algebraic Topology. McGraw-Hill or Springer-Verlag, New York, 1966.
	22	G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, Wellesley, Massachusetts, 1993.

CITED BY 18

	David Cohen-Steiner , Herbert Edelsbrunner, Inequalities for the curvature of curves and surfaces, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Reeb graphs for shape analysis and applications, Theoretical Computer Science, v.392 n.1-3, p.5-22, February, 2008
	Frédéric Chazal , David Cohen-Steiner , André Lieutier, A sampling theory for compact sets in Euclidean space, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Jean-Daniel Boissonnat , Steve Oudot, Provably good sampling and meshing of Lipschitz surfaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	David Cohen-Steiner , Herbert Edelsbrunner , Dmitriy Morozov, Vines and vineyards by updating persistence in linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Herbert Edelsbrunner , Dmitriy Morozov , Valerio Pascucci, Persistence-sensitive simplification functions on 2-manifolds, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Frédéric Chazal , David Cohen-Steiner , André Lieutier , Boris Thibert, Shape smoothing using double offsets, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	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
	Frédéric Chazal , Leonidas J. Guibas , Steve Y. Oudot , Primoz Skraba, Analysis of scalar fields over point cloud data, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1021-1030, January 04-06, 2009, New York, New York
	Leonidas J. Guibas , Steve Y. Oudot, Reconstruction using witness complexes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1076-1085, January 07-09, 2007, New Orleans, Louisiana
	Jie Gao , Leonidas J. Guibas , Steve Y. Oudot , Yue Wang, Geodesic Delaunay triangulation and witness complex in the plane, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.571-580, January 20-22, 2008, San Francisco, California
	Frédéric Chazal , Steve Yann Oudot, Towards persistence-based reconstruction in euclidean spaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	S. Biasotti , A. Cerri , P. Frosini , D. Giorgi , C. Landi, Multidimensional Size Functions for Shape Comparison, Journal of Mathematical Imaging and Vision, v.32 n.2, p.161-179, October 2008
	Eitan Yaffe , Dan Halperin, Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008
	Frédéric Chazal , David Cohen-Steiner , André Lieutier, Normal cone approximation and offset shape isotopy, Computational Geometry: Theory and Applications, v.42 n.6-7, p.566-581, August, 2009
	Frédéric Chazal , David Cohen-Steiner , Marc Glisse , Leonidas J. Guibas , Steve Y. Oudot, Proximity of persistence modules and their diagrams, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark