research-article

Reeb graphs: approximation and persistence

Authors:

Yusu WangAuthors Info & Claims

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Pages 226 - 235

https://doi.org/10.1145/1998196.1998230

Published: 13 June 2011 Publication History

Abstract

Given a continuous function f:X -> S on a topological space X, its level set f^-1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H₁-homology of the Reeb graph from P. It takes O(n log n) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm to compute the rank of H₁(MM) from point data. The best known previous algorithm for this problem takes O(n³) time for point data.

The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H₁-homology for the Reeb graphs in O(n n_e³) time, where n is the size of the 2-skeleton and n_e is the number of edges in K.

References

[1]

M. Bernstein, V. de Silva, J. Lanford, and J. Tenenbaum. Graph approximations to geodesics on embedded manifolds. Technical report, Dept. Psychology, Stanford University, USA, 2000.

[2]

S. Biasotti, D. Giorgi, M. Spagnuolo, and B. Falcidieno. Reeb graphs for shape analysis and applications. Theor. Comput. Sci., 392(1--3):5--22, 2008.

Digital Library

[3]

F. Chazal, L. J. Guibas, S. Oudot, and P. Skraba. Analysis of scalar fields over point cloud data. In Proc. 20th ACM-SIAM Sympos. Discrete Algorithms, pages 1021--1030, 2009.

Digital Library

[4]

F. Chazal, L. J. Guibas, S. Y. Oudot, and P. Skraba. Persistence-based clustering in Riemannian manifolds. Technical Report Research Report RR-6968, INRIA, June 2009.

[5]

F. Chazal and S. Oudot. Towards persistence-based reconstruction in Euclidean spaces. In Proc. 24th ACM Sympos. on Comput. Geom., pages 232--241, 2008.

Digital Library

[6]

D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Extending persistence using Poincaré and Lefschetz duality. Foundations of Computational Mathematics, 9(1):79--103, 2009.

Digital Library

[7]

D. Cohen-Steiner, H. Edelsbrunner, and D. Morozov. Vines and vineyards by updating persistence in linear time. In Proc. 22nd Annu. Sympos. Comput. Geom., pages 119--126, 2006.

Digital Library

[8]

K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci. Loops in Reeb graphs of 2-manifolds. Discrete Comput. Geom., 32(2):231--244, 2004.

Digital Library

[9]

T. K. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge U. Press, New York, NY, USA, 2007.

Digital Library

[10]

T. K. Dey and K. Li. Cut locus and topology from surface point data. In Proc. 25th Annu. Sympos. Comput. Geom., pages 125--134, 2009.

Digital Library

[11]

T. K. Dey, J. Sun, and Y. Wang. Approximating loops in a shortest homology basis from point data. In Proc. 26th Annu. Sympos. Compu. Geom., pages 166--175, 2010.

Digital Library

[12]

H. Doraiswamy and V. Natarajan. Efficient output-sensitive construction of Reeb graphs. In Proc. 19th Internat. Sym. Alg. and Comput., pages 556--567, 2008.

Digital Library

[13]

H. Doraiswamy and V. Natarajan. Efficient algorithms for computing Reeb graphs. Computational Geometry: Theory and Applications, 42:606--616, 2009.

Digital Library

[14]

H. Edelsbrunner and J. Harer. Persistent homology -- a survey. In J. E. Goodman, J. Pach, and R. Pollack, editors, Surveys on Discrete and Computational Geometry. Twenty Years Later, pages 257--282. Amer. Math. Soc., Providence, Rhode Island, 2008. Contemporary Mathematics 453.

[15]

H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, and J. Snoeyink. Time-varying Reeb graphs for continuous space-time data. Comput. Geom., 41(3):149--166, 2008.

Digital Library

[16]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28:511--533, 2002.

Digital Library

[17]

W. Harvey, R. Wenger, and Y. Wang. A randomized O(m log m) time algorithm for computing Reeb graph of arbitrary simplicial complexes. In Proc. 26th Annu. Sympos. Compu. Geom., pages 267--276, 2010.

Digital Library

[18]

J.-C. Hausmann. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. In Prospects in Topology: Proc. Conf. in Honour of William Browder, Ann. Math. Stud., 138, pages 175--188. Princeton Univ. Press, 1995.

[19]

J. R. Munkres. Elements of Algebraic Topology. Westview Press, 1996.

[20]

P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39:419--441, 2008.

Digital Library

[21]

V. Pascucci, G. Scorzelli, P.-T. Bremer, and A. Mascarenhas. Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. Graph., 26(3):58, 2007.

Digital Library

[22]

G. Reeb. Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 222:847--849, 1946.

[23]

Y. Shinagawa and T. L. Kunii. Constructing a Reeb graph automatically from cross sections. IEEE Comput. Graph. Appl., 11(6):44--51, 1991.

Digital Library

[24]

J. Tierny, A. Gyulassy, E. Simon, and V. Pascucci. Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees. IEEE Trans. Vis. Comput. Graph., 15(6):1177--1184, 2009.

Digital Library

Cited By

Zhang XGao YZhang YLi FLi HLei F(2024)Identification of Autism Spectrum Disorder Using Topological Data AnalysisJournal of Imaging Informatics in Medicine10.1007/s10278-024-01002-337:3(1023-1037)Online publication date: 13-Feb-2024
https://doi.org/10.1007/s10278-024-01002-3
Dey TFan FWang Yda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Graph induced complex on point dataProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462387(107-116)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462387
Parsa S(2013)A Deterministic $$O(m \log {m})$$O(mlogm) Time Algorithm for the Reeb GraphDiscrete & Computational Geometry10.1007/s00454-013-9511-349:4(864-878)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00454-013-9511-3
Show More Cited By

Index Terms

Reeb graphs: approximation and persistence
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Loops in reeb graphs of 2-manifolds
SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that ...
Reeb Graphs: Approximation and Persistence

Given a continuous function f:Xźź on a topological space X, its level setfź1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes ...
Automatic decomposition of 3D solids into contractible pieces using Reeb graphs
Abstract
This work is motivated by the need to generate volumetric spline models for isogeometric analysis. There exist numerous constructions of volumetric spline models that represent contractible solids. We present a novel decomposition ...
Highlights
- 3D solids are automatically subdivided into contractible pieces.
- Segmentation ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

June 2011

532 pages

ISBN:9781450306829

DOI:10.1145/1998196

Program Chairs:
Ferran Hurtado
Universitat Politècnica de Catalunya
,
Marc van Kreveld
Utrecht University

Copyright �� 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '11

Sponsor:

SoCG '11: Symposium on Computational Geometry

June 13 - 15, 2011

Paris, France

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
176
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang XGao YZhang YLi FLi HLei F(2024)Identification of Autism Spectrum Disorder Using Topological Data AnalysisJournal of Imaging Informatics in Medicine10.1007/s10278-024-01002-337:3(1023-1037)Online publication date: 13-Feb-2024
https://doi.org/10.1007/s10278-024-01002-3
Dey TFan FWang Yda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Graph induced complex on point dataProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462387(107-116)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462387
Parsa S(2013)A Deterministic $$O(m \log {m})$$O(mlogm) Time Algorithm for the Reeb GraphDiscrete & Computational Geometry10.1007/s00454-013-9511-349:4(864-878)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00454-013-9511-3
Buchin KBuchin Mvan Kreveld MSpeckmann BStaals F(2013)Trajectory grouping structureProceedings of the 13th international conference on Algorithms and Data Structures10.1007/978-3-642-40104-6_19(219-230)Online publication date: 12-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40104-6_19
Biasotti SFalcidieno BGiorgi DSpagnuolo M(2012)The hitchhiker's guide to the galaxy of mathematical tools for shape analysisACM SIGGRAPH 2012 Courses10.1145/2343483.2343499(1-33)Online publication date: 5-Aug-2012
https://dl.acm.org/doi/10.1145/2343483.2343499
Parsa SDey TWhitesides S(2012)A deterministic o(m log m) time algorithm for the reeb graphProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261289(269-276)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261289
Ma T(2012)Reeb graph computation through spectral clusteringOptical Engineering10.1117/1.OE.51.1.01720951:1(017209)Online publication date: 8-Feb-2012
https://doi.org/10.1117/1.OE.51.1.017209
Dey TGe XQue QSafa IWang LWang Y(2012)Feature-Preserving Reconstruction of Singular SurfacesComputer Graphics Forum10.1111/j.1467-8659.2012.03183.x31:5(1787-1796)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1111/j.1467-8659.2012.03183.x

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents