Pith. sign in

REVIEW 3 major objections 5 minor 53 references

Accelerating Computation of Stable Merge Tree Edit Distances using Parameterized Heuristics

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a user-chosen look-ahead parameter makes the NP-complete deformation-based merge tree edit distance computable in polynomial time for fixed look-ahead, with small values closely approximating the exact distance on…

desk verdict A useful and well-engineered heuristic for the NP-hard merge tree edit distance, with strong experiments; the central formal claim about what the heuristic computes is stated without proof. read the letter →

arxiv 2501.05529 v1 pith:SRF6EQRJ submitted 2025-01-09 cs.CG

Florian Wetzels , Heike Leitte , Christoph Garth This is my paper · ORCID
classification cs.CG
keywords mergetreeseditdistancedeformation-basedlook-aheadparameterfixed-parametertractabilitysaddleswapsstabilitytopologicaldataanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to make the stable, deformation-based edit distance for merge trees practical. That distance, which correctly handles saddle swaps, is NP-complete, and the exact solver becomes infeasible beyond about 30 vertices; the fast path mapping distance is computable in polynomial time but misses saddle swaps. The authors propose a heuristic that adds a user-chosen look-ahead parameter h to the path mapping recursion: with h=0 it reduces to path mapping, with h equal to tree depth it becomes the full deformation distance, and for intermediate h it runs in time polynomial in tree size and exponential only in h. Experiments on four established datasets show that small values (2 to 4) already produce distance matrices nearly identical to the exact distance, while cutting computation from five days to seconds.

What carries the argument

The load-bearing object is the look-ahead recursion itself: the path mapping dynamic program is extended by a fourth case, OptCollapse, which enumerates all strongly connected edge sets within look-ahead h below the nodes being matched, contracts them, and then computes the optimal assignment between the remaining leaf subtrees using the Hungarian or auction solver. The strongly connected edge sets, denoted SCESh, capture the consecutive inner-edge deletions that effect saddle swaps. This machinery is what makes the running time O($n^{4}$ + $n^{2}$ f(h)), polynomial in input size with an exponential factor in h.

What would settle it

Take all pairs of labeled merge trees with up to ten nodes, compute δh with h=1 and h=2 using the open-source implementation, and compare with the exact δE obtained by brute-force enumeration of edit sequences. If any pair has δh > δE while the optimal sequence uses no more than h consecutive deletions or insertions, then the recursion fails to capture the advertised edit model.

Watch

Extended reading notes

Core claim

The central claim is that the recursively defined distance δh, which allows collapsing strongly connected sets of up to h consecutive edges below matched nodes before solving an optimal assignment between the resulting subtrees, is a valid interpolation between the path mapping distance δ0 and the unconstrained deformation distance δE. The paper argues that such collapses correspond exactly to edit sequences whose deletions and insertions never involve more than h consecutive edges, so δh is a restricted deformation distance; as h grows to tree depth, every deletion is allowed and δh equals δE. On the TOSCA, MVK, ionization front, and vortex street datasets, the heuristic converges quickly to δE, with mean relative differences of 0.8% (TOSCA) and 2.7% (MVK) at h=2 and below 1% by h=3 to 6, while matrix runtimes drop from days to seconds.

Load-bearing premise

The load-bearing premise is that every edit sequence whose deletions and insertions never touch more than h consecutive edges can be reproduced by the three original recursive cases plus the collapse of strongly connected edge sets within look-ahead h; the paper states this model intuitively rather than proving the equivalence.

Editorial extensions

If this is right

  • For any fixed look-ahead h, the runtime is polynomial in the size of the merge trees, so stable distance matrices become feasible for trees with up to roughly 100 vertices.
  • δh is monotone in h: increasing the look-ahead can only reduce the distance, so a user can push h as high as computational budget allows.
  • At h=0 the method reproduces the path mapping distance, and at h=depth it reproduces the unconstrained deformation distance, giving a continuous spectrum of trade-offs.
  • On the tested datasets, look-ahead values of 2 to 4 reproduce the exact stable distance matrices closely enough for clustering and periodicity detection, and the resulting t-SNE embeddings show the expected smooth periodic structure.
  • The speedup enables stable comparisons on data with low simplification thresholds, where the exact solver cannot run at all.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The observed convergence suggests that saddle swaps in real scalar fields are usually shallow and local; if true, small look-ahead values should suffice broadly, but this is a conjecture beyond the paper's evidence.
  • A formal proof that δh equals the cost of optimal edit sequences with at most h consecutive deletions or insertions would turn the heuristic into an exact parameterized distance; the paper only sketches the model.
  • The collapse enumeration could likely be replaced by dynamic programming over tree shapes, which might remove the exponential dependence on h for bounded-degree trees; this is not proposed by the authors.
  • Combining δh with ε-preprocessing may give a monotone stability parameter, since the paper notes ε-preprocessing alone is not monotone; this combination is mentioned as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a parameterized heuristic for computing a stable edit distance on merge trees. The authors extend the polynomial-time path mapping distance with a user-chosen look-ahead parameter h, adding a recursive 'OptCollapse' case (Algorithm 1 and line 22 of Algorithm 2) that contracts strongly connected edge sets within distance h of the current nodes. They claim that the resulting distance δh interpolates between the path mapping distance (h=0) and the unconstrained deformation-based edit distance (h=depth), that the algorithm runs in time polynomial in the input size for fixed h (FPT-like), and that small h values produce distance matrices quantitatively close to the exact NP-complete distance while reducing runtime from days to seconds. The paper reports experiments on four datasets (TOSCA, MVK, ionization front, vortex street), including convergence measurements against the exact deformation distance and qualitative/quantitative stability assessments.

Significance. The practical contribution is substantial: if the algorithmic claims are correct, the paper opens a route to using a stable, NP-complete merge tree distance on trees with dozens to hundreds of nodes, whereas the previous exact MIP implementation is infeasible beyond about 30 vertices. The paper provides an open-source implementation and reproducible experiments, and the convergence numbers in Table 1 are compared against the independent exact distance δE from prior work, so there is no circularity in the experimental evaluation. The central theoretical claim, however—that Algorithm 2 computes the optimum over the described class of look-ahead edit sequences—is asserted without proof, and the experiments use an approximate auction solver for the inner assignment problems, leaving the connection between the implemented heuristic and the claimed distance model unquantified. The significance hinges on that theoretical gap, which is fixable in principle but is currently load-bearing.

major comments (3)
  1. [Section 4.3, 'Edit Operation Model'; Algorithm 2 line 22] The central claim that δh equals the cost of an optimal edit sequence whose deletions/insertions never contract more than h consecutive edges is not proved. The text explicitly says 'We restrict to an intuitive description,' and neither the main text nor the appendix provides an induction or any formal equivalence argument. To support the claim one must show that (a) every restricted edit sequence can be reorganized so that all non-leaf deletions occur as strongly connected edge sets within the look-ahead region at the recursion level where they are handled, and (b) the assignment over the resulting leaf subtrees in line 22 (and lines 7–9 of Algorithm 1) finds the optimum over all such reorganizations. Without this, the advertised properties—monotonicity in h, δh=δ0 at h=0, and δh=δE when h equals tree depth—are not established for the computed function. Since these properties are stated in the abstract and in Section 4.3 as the paper's main theoretical contribution, this missing proof is load-bearing.
  2. [Section 4.2, 'Parallelization & Optimal Assignment Algorithm'] The implementation uses the approximate auction solver for the assignment instances, and the paper acknowledges that this yields a heuristic solution, while the theoretical runtime bounds and the distance characterization implicitly assume exact assignment via the Hungarian method. No quantification of the approximation error is provided. Consequently, the convergence values in Table 1 and the stability comparisons are for the auction-based heuristic, not necessarily for the exact recursion defined by δh. The authors should either modify the experiments to use an exact assignment solver (the trees are small, so this may be feasible), or add a validation of the auction solver on the actual instances, e.g., comparing auction and Hungarian on a representative subset and reporting the frequency and magnitude of suboptimality.
  3. [Section 4.3, 'Complexity'; Equation (1)] The claimed fixed-parameter running time is not supported by a concrete upper bound. The text defines f(h) as f′(h)^2 · d^{3h}, where f′(h) is described as the number of d-ary trees of depth h, and then states that no closed form is known. This leaves the exponential dependence on h essentially unspecified: without an upper bound on f′(h) (e.g., f′(h) ∈ O(d^{O(h)}) or a double exponential), the statement 'polynomial in the size of the input but exponential in the look-ahead value' is not a rigorous complexity result. Additionally, the claim that the dynamic programming optimization reduces the runtime from n^4·f(h) to n^4 + n^2·f(h) is stated without a detailed argument; since the recursion's base values δh still depend on the parent-edge choices p1,p2, the memoization of OptCollapse alone does not obviously eliminate the depth factors from the first term. Please provide a precise accounting of all terms in the runtime bound.
minor comments (5)
  1. [Section 4.3] Typo: 'consectuive' should be 'consecutive'.
  2. [Appendix A.1] Typo: 'Alogirthm 2' should be 'Algorithm 2'.
  3. [Appendix F] Typo: 'integrate the the adapted module' should be 'integrate the adapted module'.
  4. [Section 3, definition of SCESh] The phrase 'within look-ahead h of v' is initially defined with the condition depthT(x) − depthT(v) <= h, but it is clearer to explicitly state that the edge (x,y) is directed with x being the parent of y; please add a small note to avoid ambiguity between the two endpoints.
  5. [Section 5.5, 'Look-ahead Scaling'] The text says the runtime grows exponentially at first but then saturates; a logarithmic y-axis would make this clearer, and the hypothesis about the asymptotics taking effect late is informal. Consider adding a brief explanation of saturation in terms of tree depth.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: δh is defined constructively and benchmarked against the independent exact distance δE; the unproven equivalence in Section 4.3 is a correctness gap, not a circular step.

full rationale

Section 4 defines δh operationally: 'We denote the distance computed by the adapted recursion with look-ahead h by δh,' and Algorithm 2 together with Algorithm 1 specify the computation. No parameter is fitted to the TOSCA, MVK, ionization front, or vortex street data; the look-ahead h is a user-chosen input, and the experimental comparison in Table 1 uses independently computed MIP solutions from prior work on the same preprocessed trees, with the same geometric constraints on MVK. The small relative differences are therefore measurements of approximation quality, not a fitted quantity renamed as a prediction. The self-citations to [40,41] supply the baseline distances, the NP-hardness motivation, and the previously established fact that deletions and insertions can be reordered; these are appropriate prior results, not assumptions that δh equals δE. The main gap is Section 4.3's edit-operation model: the paper says 'We restrict to an intuitive description' and asserts, rather than proves, that the recursion computes the optimum over look-ahead-h edit sequences and that setting h to the tree depth yields δE. That is an omitted correctness proof and a correctness risk, but it is not a circular step, because the algorithm's value is not defined in terms of the quantity it is claimed to equal. The runtime bound is read directly from the enumeration in Algorithms 1 and 2 and is not a renamed input. No equation in the paper reduces δh to δE or to a fitted parameter by construction.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central contribution is an algorithmic construction, not a derived constant. The only tunable number is the user-chosen look-ahead h. The main assumptions are the correctness of the underlying path mapping recursion, the bound on merge tree degree for the runtime bound, and the unproven recursive characterization of look-ahead edit sequences.

free parameters (1)
  • Look-ahead parameter h = User-specified, ranging from 0 to tree depth; experiments use 1 to 8.
    Controls the maximum number of consecutive edge contractions allowed; trades accuracy for runtime. Not fitted to data, but the method's behavior and run time depend on it.
assumptions (4)
  • standard math The path mapping recursion and its dynamic programming solution (from Wetzels et al. [41]) correctly compute δ0.
    Section 3 restates the recursive formulation; the paper relies on this prior result without re-proving it.
  • standard math Deletions can be moved to the front and insertions to the back of an optimal edit sequence.
    Invoked in Section 4.3 to reformulate δh as a sequence of deletions, one-degree edits, and insertions; attributed to [41].
  • domain assumption Merge trees considered in the runtime analysis have bounded degree.
    Section 4.2: 'For readability, we will assume bounded-degree trees in our runtime analysis, which is a reasonable assumption for merge trees.' This excludes high-degree nodes from the asymptotic guarantee.
  • ad hoc to paper Every edit sequence whose deletions and insertions are limited to h consecutive edges is exactly captured by the recursion's three original cases plus the strongly-connected edge-set collapse case (OptCollapse).
    Section 4.3 'Edit Operation Model' describes this equivalence, but the main text gives no proof; the appendix provides illustrations only. This is the load-bearing unproven step.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Accelerating Computation of Stable Merge Tree Edit Distances using Parameterized Heuristics." pith.science (2026). https://pith.science/paper/SRF6EQRJ

@misc{pith2026250105529,
  author       = {Pith},
  title        = {Pith review of: Accelerating Computation of Stable Merge Tree Edit Distances using Parameterized Heuristics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRF6EQRJ}},
  note         = {Machine review of arXiv:2501.05529}
}
read the original abstract

In this paper, we present a novel heuristic algorithm for the stable but NP-complete deformation-based edit distance on merge trees. Our key contribution is the introduction of a user-controlled look-ahead parameter that allows to trade off accuracy and computational cost. We achieve a fixed parameter tractable running time that is polynomial in the size of the input but exponential in the look-ahead value. This extension unlocks the potential of the deformation-based edit distance in handling saddle swaps, while maintaining feasible computation times. Experimental results demonstrate the computational efficiency and effectiveness of this approach in handling specific perturbations.

Figures

Figures reproduced from arXiv: 2501.05529 by the authors.

Figure 1
Figure 1. Four distance matrices (entry (i, j) is the distance between i-th and j-th tree, shown as heatmaps) of the vortex street dataset (axes ordered by time) for different look-ahead values together with corresponding t-SNE embeddings. The color of the t-SNE points encodes time. The periodic behavior becomes more apparent in the smoother matrices with higher look-ahead values. The t-SNE embeddings also show cleaner period… view at source ↗
Figure 2
Figure 2. Distance matrices (axes ordered by shape [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Example for the look-ahead method: T1 and T2 differ by a horizon￾tal instability. Thus, using a constrained edit distance, correctly matching any two of the features A,B,C,D, requires deletion of the other two. In contrast, if we collapse the saddle of feature D (T ′ 1 and T ′ 2 ), we can al￾ways match D and two other features, but have to delete one. If we also collapse the saddle of C (T ′′ 1 and T ′′ 2 ), we can … view at source ↗
Figures from the paper (21 more)
Figure 4
Figure 4. Figure 4: Example members of (a) the TOSCA ensemble, (b) the MVK time [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: A selection of distance matrices (axes ordered by time) for the [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: Ionization front time series: example members of the different phases (mid) and distance matrices for look-ahead [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 8
Figure 8. Figure 8: Runtimes for different look-ahead values as a function of tree size [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 7
Figure 7. Figure 7: Average runtimes for different datasets and look-ahead values in [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 9
Figure 9. Figure 9: Illustrations of example cases in the original (a,b) and look-ahead (c,d) recursion. Fixed matchings are shown in blue, collapsed edges in gray, [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Distance matrices on the ionization front time series: comparison of all computed distances. [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]
Figure 11
Figure 11. Figure 11: Distance matrices on the TOSCA ensemble using various different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: Comparison of distance matrices on the TOSCA ensemble using varying look-ahead values and simplification thresholds. [PITH_FULL_IMAGE:figures/full_fig_p016_12.png]
Figure 13
Figure 13. Figure 13: MDS embeddings of the TOSCA ensemble using various different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p017_13.png]
Figure 14
Figure 14. Figure 14: Embeddings of the ionization time series with t-SNE for perplexity [PITH_FULL_IMAGE:figures/full_fig_p018_14.png]
Figure 15
Figure 15. Figure 15: Embeddings of the ionization time series with t-SNE for perplexity [PITH_FULL_IMAGE:figures/full_fig_p018_15.png]
Figure 18
Figure 18. Figure 18: Embeddings of the ionization time series with t-SNE for perplexity [PITH_FULL_IMAGE:figures/full_fig_p019_18.png]
Figure 19
Figure 19. Figure 19: Embeddings of the ionization time series with t-SNE for perplexity [PITH_FULL_IMAGE:figures/full_fig_p019_19.png]
Figure 23
Figure 23. Figure 23: Distance matrices for the complete vortex street time series with [PITH_FULL_IMAGE:figures/full_fig_p020_23.png]
Figure 24
Figure 24. Figure 24: Distance matrices for vortex street time series using branch [PITH_FULL_IMAGE:figures/full_fig_p020_24.png]
Figure 25
Figure 25. Figure 25: Distance matrices for the S1 hole field of the MVK molecule. Stable behavior is reached at look-ahead 4. (a) Wasserstein Distance (b) Merge Tree Edit Distance (c) Path Mapping Distance (d) Look-ahead 1 (e) Look-ahead 2 (f) Look-ahead 3 (g) Look-ahead 4 (h) Unconstrain…
Figure 27
Figure 27. Figure 27: Distance matrices for the S1 particle field of the MVK molecule. Stable behavior is reached at look-ahead 6. (a) Wasserstein Distance (b) Merge Tree Edit Distance (c) Path Mapping Distance (d) Look-ahead 1 (e) Look-ahead 2 (f) Look-ahead 3 (g) Look-ahead 4 (h) Look-ah…
Figure 29
Figure 29. Figure 29: MDS embeddings for the vortex street dataset with different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p023_29.png]
Figure 30
Figure 30. Figure 30: t-SNE embeddings using high perplexity (60) for the vortex street dataset with different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p023_30.png]
Figure 31
Figure 31. Figure 31: t-SNE embeddings using low perplexity (15) for the vortex street dataset with different distance metrics. [PITH_FULL_IMAGE:figures/full_fig_p024_31.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 26 canonical work pages

  1. [1]

    Bauer, B

    U. Bauer, B. D. Fabio, and C. Landi. An edit distance for reeb graphs. In A. Ferreira, A. Giachetti, and D. Giorgi, eds., 9th Eurographics Work- shop on 3D Object Retrieval, 3DOR@Eurographics 2016, Lisbon, Por- tugal, May 8, 2016. Eurographics Association, 2016. doi: 10.2312/3dor. 20161084 2

    doi:10.2312/3dor 2016

  2. [2]

    Beketayev, D

    K. Beketayev, D. Yeliussizov, D. Morozov, G. H. Weber, and B. Hamann. Measuring the distance between merge trees. In P. Bremer, I. Hotz, V . Pas- cucci, and R. Peikert, eds., Topological Methods in Data Analysis and Visualization III, Theory, Algorithms, and Applications , pp. 151–165. Springer, 2014. doi: 10.1007/978-3-319-04099-8_10 2

    doi:10.1007/978-3-319-04099-8_10 2014

  3. [3]

    D. P. Bertsekas. A new algorithm for the assignment problem. Math. Program., 21(1):152–171, 1981. doi: 10.1007/BF01584237 3, 4

    doi:10.1007/bf01584237 1981

  4. [4]

    P. Bille. A survey on tree edit distance and related problems. Theoretical Computer Science, 337(1-3):217–239, 2005. doi: 10.1016/j.tcs.2004.12. 030 2

    work page doi:10.1016/j.tcs.2004.12 2005

  5. [5]

    Bollen, P

    B. Bollen, P. Tennakoon, and J. A. Levine. Computing a stable distance on merge trees. IEEE Trans. Vis. Comput. Graph., 29(1):1168–1177, 2023. doi: 10.1109/TVCG.2022.3209395 2

    arXiv 2023

  6. [6]

    A. M. Bronstein, M. M. Bronstein, and R. Kimmel. Numerical Geometry of Non-Rigid Shapes. Monographs in Computer Science. Springer, 2009. doi: 10.1007/978-0-387-73301-2 6

    work page doi:10.1007/978-0-387-73301-2 2009

  7. [7]

    H. A. Carr, J. Snoeyink, and U. Axen. Computing contour trees in all dimensions. In D. B. Shmoys, ed., Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, pp. 918–926. ACM/SIAM, 2000. 1, 2

    work page 2000

  8. [8]

    Chakraborty, R

    P. Chakraborty, R. C. Couto, and N. H. List. Deciphering methyla- tion effects on s2 (ππ *) internal conversion in the simplest linear α, β- unsaturated carbonyl. The Journal of Physical Chemistry A, 127(25):5360– 5373, 2023. PMID: 37331016. doi: 10.1021/acs.jpca.3c02582 7

    work page doi:10.1021/acs.jpca.3c02582 2023

Show all 53 references
  1. [9]

    Chazal, D

    F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, and S. Oudot. Prox- imity of persistence modules and their diagrams. In J. Hershberger and E. Fogel, eds., Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 8-10, 2009, pp. 237–246. ACM,...

    2009

  2. [10]

    Cohen-Steiner, H

    D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discret. Comput. Geom., 37(1):103–120, 2007. doi: 10.1007/ s00454-006-1276-5 2

    2007

  3. [11]

    Dagum and R

    L. Dagum and R. Menon. OpenMP: An Industry Standard API for Shared- Memory Programming. Computational Science & Engineering, IEEE , 5(1):46–55, 1998. 4

    1998

  4. [12]

    Edelsbrunner and J

    H. Edelsbrunner and J. Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. 2

    2010

  5. [13]

    Edelsbrunner, D

    H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pp. 454–463. IEEE Computer Society, 2000. doi: 10.1109/SFCS...

  6. [14]

    B. D. Fabio and C. Landi. Stability of reeb graphs of closed curves. In L. Fajstrup, E. Goubault, and M. Raussen, eds., Proceedings of the workshop on Geometric and Topological Methods in Computer Science, GETCO 2010, Aalborg, Denmark, January 11-15, 2010 , vol. 283 of Electro...

    2010

  7. [15]

    B. D. Fabio and C. Landi. The edit distance for reeb graphs of surfaces. Discret. Comput. Geom., 55(2):423–461, 2016. doi: 10.1007/s00454-016 -9758-6 2

    2016 doi

  8. [16]

    Flum and M

    J. Flum and M. Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi: 10. 1007/3-540-29953-X 4

    2006

  9. [17]

    Gasparovic, E

    E. Gasparovic, E. Munch, S. Oudot, K. Turner, B. Wang, and Y . Wang. Intrinsic interleaving distance for merge trees. CoRR, 1908.00063, 2019. 2

    1908 arXiv

  10. [18]

    Heine, H

    C. Heine, H. Leitte, M. Hlawitschka, F. Iuricich, L. D. Floriani, G. Scheuer- mann, H. Hagen, and C. Garth. A survey of topology-based methods in visualization. Comput. Graph. Forum, 35(3):643–667, 2016. doi: 10. 1111/cgf.12933 2

    2016

  11. [19]

    Hilaga, Y

    M. Hilaga, Y . Shinagawa, T. Komura, and T. L. Kunii. Topology matching for fully automatic similarity estimation of 3D shapes. In ACM SIG- GRAPH, 2001. 6

    2001

  12. [20]

    A. P. Lohfink, F. Gartzky, F. Wetzels, L. V ollmer, and C. Garth. Time- varying fuzzy contour trees. In 2021 IEEE Visualization Conference, IEEE VIS 2021 - Short Papers, New Orleans, LA, USA, October 24-29, 2021, pp. 86–90. IEEE, 2021. doi: 10.1109/VIS49827.2021.9623286 1

    2021

  13. [21]

    A. P. Lohfink, F. Wetzels, J. Lukasczyk, G. H. Weber, and C. Garth. Fuzzy contour trees: Alignment and joint layout of multiple contour trees. Comput. Graph. Forum, 39(3):343–355, 2020. doi: 10.1111/cgf.13985 1, 2, 9

    2020 doi

  14. [22]

    Morozov, K

    D. Morozov, K. Beketayev, and G. H. Weber. Interleaving distance be- tween merge trees. In TopoInVis. 2014. 2

    2014

  15. [23]

    Morozov and G

    D. Morozov and G. H. Weber. Distributed merge trees. In A. Nicolau, X. Shen, S. P. Amarasinghe, and R. W. Vuduc, eds., ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, Shenzhen, China, February 23-27, 2013, pp. 93–102. ACM, 2013. doi: 10.114...

    2013

  16. [24]

    J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38,

  17. [25]

    Narayanan, D

    V . Narayanan, D. M. Thomas, and V . Natarajan. Distance between ex- tremum graphs. In S. Liu, G. Scheuermann, and S. Takahashi, eds., 2015 IEEE Pacific Visualization Symposium, PacificVis 2015, Hangzhou, China, April 14-17, 2015, pp. 263–270. IEEE Computer Society, 2015. doi:...

    2015

  18. [26]

    OpenMP Application Program Interface Version 3.0, May 2008

    OpenMP Architecture Review Board. OpenMP Application Program Interface Version 3.0, May 2008. 4

    2008

  19. [27]

    Pont and J

    M. Pont and J. Tierny. Wasserstein auto-encoders of merge trees (and persistence diagrams). IEEE Trans. Vis. Comput. Graph., 30(9):6390– 6406, 2024. doi: 10.1109/TVCG.2023.3334755 9

    2024

  20. [28]

    M. Pont, J. Vidal, J. Delon, and J. Tierny. Wasserstein distances, geodesics and barycenters of merge trees. IEEE Trans. Vis. Comput. Graph. , 28(1):291–301, 2022. doi: 10.1109/TVCG.2021.3114839 1, 2, 3, 5, 7, 9

    2022

  21. [29]

    M. Pont, J. Vidal, and J. Tierny. Principal geodesic analysis of merge trees (and persistence diagrams). IEEE Trans. Vis. Comput. Graph., 29(2):1573– 1589, 2023. doi: 10.1109/TVCG.2022.3215001 1, 9

    2023

  22. [30]

    S. Popinet. Free computational fluid dynamics. ClusterWorld, 2(6), 2004. 7

    2004

  23. [31]

    P. J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53–65, 1987. doi: 10.1016/0377-0427(87)90125-7 6

    1987 doi

  24. [32]

    Saikia, H

    H. Saikia, H. Seidel, and T. Weinkauf. Extended branch decomposition graphs: Structural comparison of scalar data. Comput. Graph. Forum, 33(3):41–50, 2014. doi: 10.1111/cgf.12360 1, 2, 7

    2014 doi

  25. [33]

    S. M. Selkow. The tree-to-tree editing problem. Inf. Process. Lett. , 6(6):184–186, 1977. doi: 10.1016/0020-0190(77)90064-3 2

    1977 doi

  26. [34]

    Sridharamurthy, T

    R. Sridharamurthy, T. B. Masood, A. Kamakshidasan, and V . Natarajan. Edit distance between merge trees. IEEE Trans. Vis. Comput. Graph., 26(3):1518–1531, 2020. doi: 10.1109/TVCG.2018.2873612 1, 2, 3, 5, 6, 7

    2020

  27. [35]

    Sridharamurthy and V

    R. Sridharamurthy and V . Natarajan. Comparative analysis of merge trees using local tree edit distance. IEEE Trans. Vis. Comput. Graph. , 29(2):1518–1530, 2023. doi: 10.1109/TVCG.2021.3122176 1, 2

    2023

  28. [36]

    Taylor, A

    R. Taylor, A. Chourasia, D. Whalen, and M. L. Norman. The IEEE SciVis Contest. http://sciviscontest.ieeevis.org/2008/, 2008. 7

    2008

  29. [37]

    D. M. Thomas and V . Natarajan. Detecting symmetry in scalar fields using augmented extremum graphs. IEEE Trans. Vis. Comput. Graph., 19(12):2663–2672, 2013. doi: 10.1109/TVCG.2013.148 1, 2

    2013 doi

  30. [38]

    Tierny, G

    J. Tierny, G. Favelier, J. A. Levine, C. Gueunet, and M. Michaux. The topology toolkit. IEEE Trans. Vis. Comput. Graph., 24(1):832–842, 2018. doi: 10.1109/TVCG.2017.2743938 3

    2018

  31. [39]

    Weinkauf and H

    T. Weinkauf and H. Theisel. Streak lines as tangent curves of a derived vector field. IEEE Transactions on Visualization and Computer Graphics (Proceedings Visualization 2010), 16(6):1225–1234, November - Decem- ber 2010. 7

    2010

  32. [40]

    Wetzels, M

    F. Wetzels, M. Anders, and C. Garth. Taming horizontal instability in merge trees: On the computation of a comprehensive deformation- based edit distance. In 2023 Topological Data Analysis and Visualization (TopoInVis), pp. 82–92, 2023. doi: 10.1109/TopoInVis60193.2023.00015 1...

    2023

  33. [41]

    Wetzels and C

    F. Wetzels and C. Garth. A deformation-based edit distance for merge trees. In 2022 Topological Data Analysis and Visualization (TopoInVis), pp. 29–38, 2022. doi: 10.1109/TopoInVis57755.2022.00010 1, 2, 3, 4, 7

    2022

  34. [42]

    Wetzels, H

    F. Wetzels, H. Leitte, and C. Garth. Branch decomposition-independent edit distances for merge trees. Computer Graphics Forum, 41(3):367–378,

  35. [43]

    Wetzels, H

    F. Wetzels, H. Leitte, and C. Garth. Accelerating computation of stable merge tree edit distances using parameterized heuristics (supplementary source code). https://github.com/scivislab/ Path-Mappings-with-Lookahead , 2025. 9

    2025

  36. [44]

    Wetzels, T

    F. Wetzels, T. B. Masood, N. H. List, I. Hotz, and C. Garth. Exploring Electron Density Evolution using Merge Tree Mappings. In C. Tomin- ski, M. Waldner, and B. Wang, eds., EuroVis 2024 - Short Papers. The Eurographics Association, 2024. doi: 10.2312/evs.20241069 7

    2024 doi

  37. [45]

    Wetzels, M

    F. Wetzels, M. Pont, J. Tierny, and C. Garth. Merge tree geodesics and barycenters with path mappings. IEEE Trans. Vis. Comput. Graph., 30(1):1095–1105, 2024. doi: 10.1109/TVCG.2023.3326601 1, 7

    2024

  38. [46]

    L. Yan, T. Bin Masood, F. Rasheed, I. Hotz, and B. Wang. Geometry aware merge tree comparisons for time-varying data with interleaving distances. IEEE Transactions on Visualization and Computer Graphics, pp. 1–1, 2022. doi: 10.1109/TVCG.2022.3163349 2

    2022

  39. [47]

    L. Yan, T. B. Masood, R. Sridharamurthy, F. Rasheed, V . Natarajan, I. Hotz, and B. Wang. Scalar field comparison with topological descriptors: Prop- erties and applications for scientific visualization. Comput. Graph. Forum, 40(3):599–633, 2021. doi: 10.1111/cgf.14331 2

    2021 doi

  40. [48]

    L. Yan, Y . Wang, E. Munch, E. Gasparovic, and B. Wang. A structural average of labeled merge trees for uncertainty visualization. IEEE Trans. Vis. Comput. Graph., 26(1):832–842, 2020. doi: 10.1109/TVCG.2019. 2934242 2

    2020 doi

  41. [49]

    K. Zhang. A constrained edit distance between unordered labeled trees. Algorithmica, 15(3):205–222, 1996. doi: 10.1007/BF01975866 3

    1996 doi

  42. [50]

    Zhang, R

    K. Zhang, R. Statman, and D. E. Shasha. On the editing distance between unordered labeled trees. Inf. Process. Lett., 42(3):133–139, 1992. doi: 10. 1016/0020-0190(92)90136-J 2 A A LGORITHM DETAILS In this section, we provide additional descriptions and illustrations for the al...

    1992

  43. [1957]

    doi: 10.1137/0105003 3, 4

    doi

  44. [2010]

    doi: 10.1016/J.ENTCS.2012.05.006 2

    2012 doi

  45. [2022]

    doi: 10.1111/cgf.14547 1, 2, 7

    doi

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.