Document Open Access Logo

Maintaining Reeb Graphs of Triangulated 2-Manifolds

Authors Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.8.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
Kyle Fox
Abhinandan Nath

Cite As Get BibTex

Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath. Maintaining Reeb Graphs of Triangulated 2-Manifolds. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.8

Abstract

Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for 
maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.

Subject Classification

Keywords
  • Reeb graphs
  • 2-manifolds
  • topological graph theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algo., 5(1):4:1-4:37, 2008. Google Scholar
  2. Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang, and Jungwoo Yang. Maintaining contour trees of dynamic terrains. In Proc. 31st Int. Symp. Comp. Geom., pages 796-811, 2015. Google Scholar
  3. Pankaj K. Agarwal and Micha Sharir. Davenport-schinzel sequences and their geometric applications. Handbook of computational geometry, pages 1-47, 2000. Google Scholar
  4. Julien Basch, Leonidas J Guibas, and John Hershberger. Data structures for mobile data. J. Algo., 31(1):1-28, 1999. Google Scholar
  5. Dmitriy Bespalov, William C Regli, and Ali Shokoufandeh. Reeb graph based shape retrieval for cad. In Proc. Int. Des. Engg. Tech. Conf. Comput. Inf. Engg., pages 229-238, 2003. Google Scholar
  6. Kree Cole-McLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci. Loops in Reeb graphs of 2-manifolds. In 19th Int. Symp. Comp. Geome., pages 344-350. ACM, 2003. Google Scholar
  7. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong. Computational geometry. Springer, 3rd edition, 2000. Google Scholar
  8. Harish Doraiswamy and Vijay Natarajan. Computing reeb graphs as a union of contour trees. IEEE Trans. Visualiz. Comput. Graph., 19(2):249-262, 2013. Google Scholar
  9. Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, and Valerio Pascucci. Time-varying Reeb graphs for continuous space-time data. In 20th Int. Symp. Comp. Geome., pages 366-372. ACM, 2004. Google Scholar
  10. A. T. Fomenko and T. L. Kunii. Topological Methods for Visualization. Springer-Verlag, Tokyo, Japan, 1997. Google Scholar
  11. Leonidas J. Guibas. Modeling motion. In Handbook of Discrete and Computational Geometry, Second Edition., pages 1117-1134. 2004. Google Scholar
  12. William Harvey, Yusu Wang, and Rephael Wenger. A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In Proc. 26th Symp. Comput. Geom., pages 267-276, 2010. Google Scholar
  13. Salman Parsa. A deterministic O(m log m) time algorithm for the Reeb graph. Disc. Comput. Geom., 49(4):864-878, 2013. Google Scholar
  14. Valerio Pascucci, Giorgio Scorzelli, Peer-Timo Bremer, and Ajith Mascarenhas. Robust on-line computation of reeb graphs: simplicity and speed. ACM Trans. Graph., 26(3):58, 2007. Google Scholar
  15. Georges Reeb. Sur les points singuliers d’une forme de pfaff completement intégrable ou d’une fonction numérique. CR Acad. Sci. Paris, 222(847-849):2, 1946. Google Scholar
  16. Yoshihisa Shinagawa and Tosiyasu L Kunii. Constructing a Reeb graph automatically from cross sections. IEEE Comp. Graph. App., 11(6):44-51, 1991. Google Scholar
  17. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. Google Scholar
  18. B-S Sohn and Chandrajit Bajaj. Time-varying contour topology. IEEE Trans. Visual. and Comp. Graph, 12(1):14-25, 2006. Google Scholar
  19. Andrzej Szymczak. Subdomain aware contour trees and contour evolution in time-dependent scalar fields. In Inter. Conf. Shape Modeling Appli., pages 136-144. IEEE, 2005. Google Scholar
  20. Tony Tung and Francis Schmitt. The augmented multiresolution reeb graph approach for content-based retrieval of 3d shapes. Int. J. Shape Modeling, 11(01):91-120, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact