Article

Loops in reeb graphs of 2-manifolds

Authors:

Kree Cole-McLaughlin,

Herbert Edelsbrunner,

Vijay Natarajan,

Valerio PascucciAuthors Info & Claims

SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

Pages 344 - 350

https://doi.org/10.1145/777792.777844

Published: 08 June 2003 Publication History

Abstract

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 depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(nlogn), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.

References

[1]

P. S. Alexandrov. Combinatorial Topology. Republication of three volumes published in 1956, 57, 60, Dover, Mineola, New York, 1998.

[2]

C. L. Bajaj, V. Pascucci and D. R. Schikore. The contour spectrum. In "Proc. IEEE Visualization, 1997", 167--175.

Digital Library

[3]

H. Carr, J. Snoeyink and U. Axen. Computing contour trees in all dimensions. Comput. Geom. Theory Appl. 24 (2002), 75--94.

Digital Library

[4]

T. H. Cormen, C. E. Leiserson and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1994.

Digital Library

[5]

H. Edelsbrunner, J. Harer and A. Zomorodian. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete Comput. Geom., to appear.

[6]

A. T. Fomenko and T. L. Kunii, (eds). Topological Methods for Visualization. Springer-Verlag, Tokyo, Japan, 1997.

[7]

M. Goresky and R. MacPhearson. Stratified Morse Theory. Springer-Verlag, Heidelberg, Germany, 1988.

[8]

M. Hilaga, Y. Shinagawa, T. Komura and T. L. Kunii. Topology matching for fully automatic similarity estimation of 3D shapes. In "Computer Graphics Proc., Siggraph 2001", 203--212.

Digital Library

[9]

M. van Kreveld, R. van Oostrum, C. L. Bajaj, V. Pascucci and D. R. Schikore. Contour trees and small seed sets for isosurface traversal. In "Proc. 13th Ann. Sympos. Comput. Geom., 1997", 212--220.

Digital Library

[10]

W. S. Massey. Algebraic Topology: An Introduction. Springer-Verlag, New York, 1967.

[11]

K. Mehlhorn, S. Naher and H. Alt. A lower bound on the complexity of the union-split-find problem. SIAM J. Comput. 17 (1988), 1093--1102.

Digital Library

[12]

V. Pascucci and K. Cole-McLaughlin. Efficient computation of the topology of level sets. Algorithmica, to appear.

[13]

G. Reeb. Sur les points singuliers d'une forme de Pfaff complement integrable ou d'une fonction numerique. Comptes Rendus de L'Academie ses Seances, Paris 222 (1946), 847--849.

[14]

R. Seidel and C. Aragon. Randomized search trees. Algorithmica 16 (1996), 464--497.

[15]

H. Seifert and W. Threlfall. Lehrbuch der Topologie. Chelsea, New York, 1934.

[16]

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

Digital Library

[17]

Y. Shinagawa, T. L. Kunii, H. Sato and M. Ibusuki. Modeling contact of two complex objects: with an application to characterizing dental articulations. Computers and Graphics 19 (1995), 21--28.

[18]

S. Yoshihisa, T. L. Kunii and Y. L. Kergosian. Surface coding based on Morse theory. IEEE Comput. Graphics Appl. 11 (1991), 66--78.

Digital Library

Cited By

Ramamurthi YAgarwal TChattopadhyay A(2022)A Topological Similarity Measure Between Multi-Resolution Reeb SpacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.308727328:12(4360-4374)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TVCG.2021.3087273
Vidal JGuillou PTierny J(2021)A Progressive Approach to Scalar Field TopologyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.306050027:6(2833-2850)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TVCG.2021.3060500
Vidal JTierny J(2021)Fast Approximation of Persistence Diagrams with Guarantees2021 IEEE 11th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV53230.2021.00008(1-11)Online publication date: Oct-2021
https://doi.org/10.1109/LDAV53230.2021.00008
Show More Cited By

Index Terms

Loops in reeb graphs of 2-manifolds
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Reeb graphs: approximation and persistence
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

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 ...
Time-varying reeb graphs for continuous space-time data
SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

We study the evolution of the Reeb graph of a time-varying continuous function defined in three-dimensional space. While maintaining the Reeb graph, we compress the evolving sequence into a single, partially persistent data structure. We envision this ...
Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

June 2003

398 pages

ISBN:1581136633

DOI:10.1145/777792

Conference Chair:
Steve Fortune
Bell Laboratories

Copyright © 2003 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: 08 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG03

Sponsor:

SoCG03: Annual ACM Symposium on Computational Geometry

June 8 - 10, 2003

California, San Diego, USA

Acceptance Rates

SCG '03 Paper Acceptance Rate 42 of 118 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
559
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ramamurthi YAgarwal TChattopadhyay A(2022)A Topological Similarity Measure Between Multi-Resolution Reeb SpacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.308727328:12(4360-4374)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TVCG.2021.3087273
Vidal JGuillou PTierny J(2021)A Progressive Approach to Scalar Field TopologyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.306050027:6(2833-2850)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TVCG.2021.3060500
Vidal JTierny J(2021)Fast Approximation of Persistence Diagrams with Guarantees2021 IEEE 11th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV53230.2021.00008(1-11)Online publication date: Oct-2021
https://doi.org/10.1109/LDAV53230.2021.00008
P. Thomas DBorgo RS. Laramee RJ. Hands S(2019)Topological Visualisation Techniques for Volume Multifield DataComputer Graphics and Imaging10.5772/intechopen.82185Online publication date: 23-Oct-2019
https://doi.org/10.5772/intechopen.82185
Jallepalli ALevine JKirby R(2019)The Effect of Data Transformations on Scalar Field Topological Analysis of High-Order FEM SolutionsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934338(1-1)Online publication date: 2019
https://doi.org/10.1109/TVCG.2019.2934338
Gueunet CFortin PTierny JJomier J(2019)Task-based Augmented Contour Trees with Fibonacci HeapsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.2898436(1-1)Online publication date: 2019
https://doi.org/10.1109/TPDS.2019.2898436
Tu JHajij MRosen P(2019)Propagate and Pair: A Single-Pass Approach to Critical Point Pairing in Reeb GraphsAdvances in Visual Computing10.1007/978-3-030-33720-9_8(99-113)Online publication date: 21-Oct-2019
https://doi.org/10.1007/978-3-030-33720-9_8
Tierny JTierny J(2018)AbstractionTopological Data Analysis for Scientific Visualization10.1007/978-3-319-71507-0_3(35-66)Online publication date: 18-Jan-2018
https://doi.org/10.1007/978-3-319-71507-0_3
Tierny JTierny J(2018)BackgroundTopological Data Analysis for Scientific Visualization10.1007/978-3-319-71507-0_2(3-33)Online publication date: 18-Jan-2018
https://doi.org/10.1007/978-3-319-71507-0_2
Kiss GAndo YSchifko M(2017)Retained Liquid and Bake Drip Simulation Using Geodesic Curves on TriangulationsSAE Technical Paper Series10.4271/2017-01-0508Online publication date: 28-Mar-2017
https://doi.org/10.4271/2017-01-0508
Show More Cited By

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