Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2582112.2582162 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
single graph,elegant algorithm,split tree,reeb graph,contour tree,split trees,function value,connected component,continuous function,log2 n,tree output | Discrete mathematics,Range tree,Trémaux tree,Combinatorics,Tree (graph theory),K-ary tree,SPQR tree,Spanning tree,Gomory–Hu tree,Mathematics,Reeb graph | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suyi Wang | 1 | 9 | 1.21 |
| Yusu Wang | 2 | 860 | 57.40 |
| Rephael Wenger | 3 | 441 | 43.54 |