The JS-graphs of Join and Split Trees

ABSTRACT

Let f be a continuous function defined on a topological space. As we increase the function value, connected components in the level set of f appear, disappear, merge, or split, and the Reeb graph tracks these changes. The join and split trees of f track the changes of connected components in the sublevel and superlevel set respectively. If the Reeb graph is loop-free, then it is a tree called the contour tree. Given a piecewise linear function f defined on a simplicial complex K, Carr, Snoeyink and Axen proposed a simple and elegant algorithm to compute the contour tree of f by "merging" its join and split trees in near-linear time.

In practice, there are often scenarios where one applies the algorithm of Carr et al. hoping to obtain a tree output, even if the Reeb graph of the input scalar field may have loops. This is particular common when handling high dimensional unorganized point clouds data. In this paper, we explore the validity of applying the algorithm of Carr et al. to any join and split tree and suggest modifications. We show that if the Reeb graph of f is not a tree, then the algorithm sometimes fails to produce a tree which reflects the input join and split trees.

We introduce the concept of a JS-graph as a generalization of the contour tree. The JS-graph is a single graph which fully encodes the information in both join and split trees. A join tree, TJ, and split tree, TS, may have more than one JS-graph. We provide a characterization for all JS-graphs of TJ and TS. While the Reeb graph of f is a JS-graph, constructing the Reeb graph of f requires building and using the 2-skeleton of K. Our algorithm, based on the algorithm of Carr et al., constructs a JS-graph with at most 2(n−1) edges in O(n log2 n) time from just the join and split trees of K, where n is the number of vertices in K.

References

1. C. L. Bajaj, V. Pascucci, and D. R. Schikore. The contour spectrum. In IEEE Visualization '97, 1997.
2. H. Carr and J. Snoeyink. Path seeds and flexible isosurfaces using topology for exploratory visualization. In VISSYM '03: Proceedings of the symposium on Data visualisation 2003, pages 49--58. Eurographics Association, 2003.
3. H. Carr, J. Snoeyink, and U. Axen. Computing contour trees in all dimensions. Computational Geometry: Theory and Applications, 24:75--94, 2003.
4. H. Carr, J. Snoeyink, and M. van de Panne. Simplifying flexible isosurfaces using local geometric measures. In IEEE Visualization, pages 497--504, 2004.
5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and S. Clifford. Introduction to Algorithms. MIT Press, Cambridge, MA, 2001.
6. M. de Bert, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applciations. Springer-Verlag, third edition, 2008.
7. D. Demir, K. Beketayev, G. H. Weber, P.-T. Bremer, V. Pascucci, and B. Hamann. Topology exploration with hierarchical landscapes. In Proceedings of the Workshop at SIGGRAPH Asia, WASA '12, pages 147--154, 2012.
8. H. Edelsbrunner and J. Harer. Computational Topology. An Introduction. Amer. Math. Soc., Providence, Rhode Island, 2009.
9. W. Harvey and Y. Wang. Generating and exploring a collection of topological landscapes for visualization of scalar-valued functions. Comput. Graphics Forum, 29(3):993--1002, June 2010.
10. W. Harvey, Y. Wang, and R. Wenger. A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. In Proceedings of the Annual Symposium on Computational Geometry, pages 267--276. ACM Press, 2010.
11. P. Oesterling, C. Heine, H. Janicke, and G. Scheuermann. Visual analysis of high dimensional point clouds using topological landscapes. In Pacific Visualization Symposium (PacificVis), 2010 IEEE, pages 113--120, 2010.
12. S. Parsa. A deterministic O(m log m) time algorithm for the Reeb graph. In Proceedings of the Symposium on Computational Geometry, pages 269--276. ACM Press, 2012.
13. S. Takahashi, I. Fujishiro, and M. Okada. Applying manifold learning to plotting approximate contour trees. IEEE Transactions on Visualization and Computer Graphics, 15(6), 2009.
14. M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, and D. Schikore. Contour trees and small seed sets for isosurface traversal. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 212--220, 1997.
15. G. Weber, P.-T. Bremer, and V. Pascucci. Topological landscapes: A terrain metaphor for scientific data. IEEE Trans. Vis. Comput. Graph., 13(6):1416--1423, 2007.
16. G. H. Weber, S. E. Dillard, H. Carr, V. Pascucci, and B. Hamann. Topology-controlled volume rendering. IEEE Transactions on Visualization and Computer Graphics, 13(2):330--341, 2007.
17. R. Wenger. Isosurfaces: Geometry, Topology, and Algorithms. CRC Press, Boca Raton, Florida, 2013.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry