Document Open Access Logo

Avoiding the Global Sort: A Faster Contour Tree Algorithm

Authors Benjamin Raichel, C. Seshadhri

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.57.pdf
  • Filesize: 475 kB
  • 14 pages

Document Identifiers

Author Details

Benjamin Raichel
C. Seshadhri

Cite As Get BibTex

Benjamin Raichel and C. Seshadhri. Avoiding the Global Sort: A Faster Contour Tree Algorithm. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.57

Abstract

We revisit the classical problem of computing the contour tree of a scalar field f:M to R, where M is a triangulated simplicial mesh in R^d. The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization.

All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) Omega(n log n) time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. If C denotes the set of critical points in M, the running time is roughly O(sum_{v in C} log l_v), where l_v is the depth of v in the contour tree. This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in M or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm.

Our algorithm requires several novel ideas: partitioning M in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.

Subject Classification

Keywords
  • contour trees
  • computational topology
  • computational geometry

Metrics

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

References

  1. C. Bajaj, M. van Kreveld, R. W. van Oostrum, V. Pascucci, and D. R. Schikore. Contour trees and small seed sets for isosurface traversal. Technical Report UU-CS-1998-25, Department of Information and Computing Sciences, Utrecht University, 1998. Google Scholar
  2. K. Beketayev, G. Weber, M. Haranczyk, P.-T. Bremer, M. Hlawitschka, and B. Hamann. Visualization of topology of transformation pathways in complex chemical systems. In Computer Graphics Forum (EuroVis 2011), pages 663-672, 2011. Google Scholar
  3. R. Boyell and H. Ruston. Hybrid techniques for real-time radar simulation. In Proceedings of Fall Joint Computer Conference, pages 445-458, 1963. Google Scholar
  4. P.-T. Bremer, G. Weber, V. Pascucci, M. Day, and J. Bell. Analyzing and tracking burning structures in lean premixed hydrogen flames. IEEE Transactions on Visualization and Computer Graphics, 16(2):248-260, 2010. Google Scholar
  5. P.-T. Bremer, G. Weber, J. Tierny, V. Pascucci, M. Day, and J. Bell. Analyzing and tracking burning structures in lean premixed hydrogen flames. IEEE Transactions on Visualization and Computer Graphics, 17(9):1307-1325, 2011. Google Scholar
  6. H. Carr. Topological Manipulation of Isosurfaces. PhD thesis, University of British Columbia, 2004. Google Scholar
  7. H. Carr, J. Snoeyink, and U. Axen. Computing contour trees in all dimensions. Computational Geometry: Theory and Applications, 24(2):75-94, 2003. Google Scholar
  8. Y. Chiang, T. Lenz, X. Lu, and G. Rote. Simple and optimal output-sensitive construction of contour trees using monotone paths. Computational Geometry: Theory and Applications, 30(2):165-195, 2005. URL: http://dx.doi.org/10.1016/j.comgeo.2004.05.002.
  9. K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci. Loops in reeb graphs of 2-manifolds. In Proceedings of the Symposium on Computational Geometry (SoCG), pages 344-350, 2003. URL: http://dx.doi.org/10.1145/777792.777844.
  10. H. Doraiswamy and V. Natarajan. Efficient algorithms for computing reeb graphs. Computational Geometry: Theory and Applications, 42:606-616, 2009. Google Scholar
  11. H. Doraiswamy and V. Natarajan. Computing reeb graphs as a union of contour trees. IEEE Transactions on Visualization and Computer Graphics, 19(2):249-262, 2013. Google Scholar
  12. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer, 1987. Google Scholar
  13. H. Freeman and S. Morse. On searching a contour map for a given terrain elevation profile. Journal of the Franklin Institute, 284(1):1-25, 1967. Google Scholar
  14. W. Harvey, Y. Wang, and R. Wenger. A randomized o(m log m) time algorithm for computing reeb graph of arbitrary simplicial complexes. In Proceedings of the Symposium on Computational Geometry (SoCG), pages 267-276, 2010. Google Scholar
  15. D. Laney, P.-T. Bremer, A. Macarenhas, P. Miller, and V. Pascucci. Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities. IEEE Transactions on Visualization and Computer Graphics, 12(6):1053-1060, 2006. Google Scholar
  16. A. Mascarenhas, R. Grout, P.-T. Bremer, V. Pascucci, E. Hawkes, and J. Chen. Topological feature extraction for comparison of length scales in terascale combustion simulation data. In Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications, pages 229-240, 2011. Google Scholar
  17. S. Parsa. A deterministic o(m log m) time algorithm for the reeb graph. In Proceedings of the Symposium on Computational Geometry (SoCG), pages 269-276, 2012. Google Scholar
  18. V. Pascucci and K. Cole-McLaughlin. Efficient computation of the topology of level set. In IEEE Visualization, pages 187-194, 2002. URL: http://dx.doi.org/10.1109/VISUAL.2002.1183774.
  19. V. Pascucci, G. Scorzelli, P.-T. Bremer, and A. Mascarenhas. Robust on-line computation of reeb graphs: simplicity and speed. ACM Transactions on Graphics, 26(58), 2007. Google Scholar
  20. B. Raichel and C. Seshadhri. Avoiding the global sort: A faster contour tree algorithm. CoRR, abs/1411.2689, 2014. Google Scholar
  21. Y. Shinagawa and T. Kunii. Constructing a reeb graph automatically from cross sections. IEEE Comput. Graphics Appl., 11(6):44-51, 1991. Google Scholar
  22. S. Tarasov and M. Vyalyi. Construction of contour trees in 3d in O(n log n) steps. In Proceedings of the Symposium on Computational Geometry (SoCG), pages 68-75, 1998. URL: http://dx.doi.org/10.1145/276884.276892.
  23. J. Tierny, A. Gyulassy, E. Simon, and V. Pascucci. Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees. IEEE Trans. on Visualization and Computer Graphics, 15(6):1177-1184, 2009. Google Scholar
  24. M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, and D. Schikore. Contour trees and small seed sets for isosurface traversal. In Proceedings of the Symposium on Computational Geometry (SoCG), pages 212-220, 1997. URL: http://dx.doi.org/10.1145/262839.269238.
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