# Task-based Augmented Contour Trees with Fibonacci Heaps

arXiv: https://arxiv.org/abs/1902.04805 · HTML: https://mlsanity.com/paper/1902.04805/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2019.

## Built on by (most cited first, 15 of 15)

- [Wasserstein Distances, Geodesics and Barycenters of Merge Trees](https://mlsanity.com/paper/2107.07789/) (2021)
- [Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark](https://mlsanity.com/paper/2206.13932/) (2022)
- [Topological Analysis of Ensembles of Hydrodynamic Turbulent Flows -- An Experimental Study](https://mlsanity.com/paper/2207.14080/) (2022)
- [Principal Geodesic Analysis of Merge Trees (and Persistence Diagrams)](https://mlsanity.com/paper/2207.10960/) (2022)
- [Wasserstein Dictionaries of Persistence Diagrams](https://mlsanity.com/paper/2304.14852/) (2023)
- [Wasserstein Auto-Encoders of Merge Trees (and Persistence Diagrams)](https://mlsanity.com/paper/2307.02509/) (2023)
- [TTK is Getting MPI-Ready](https://mlsanity.com/paper/2310.08339/) (2023)
- [A Practical Solver for Scalar Data Topological Simplification](https://mlsanity.com/paper/2407.12399/) (2024)
- [BondMatcher: H-Bond Stability Analysis in Molecular Systems](https://mlsanity.com/paper/2504.03205/) (2025)
- [Robust Barycenters of Persistence Diagrams](https://mlsanity.com/paper/2509.14904/) (2025)
- [Some equivalence relation between persistent homology and morphological dynamics](https://mlsanity.com/paper/2205.12546/) (2022)
- [Enabling Fast and Accurate Crowdsourced Annotation for Elevation-Aware Flood Extent Mapping](https://mlsanity.com/paper/2408.05350/) (2024)
- [Topology Aware Neural Interpolation of Scalar Fields](https://mlsanity.com/paper/2508.17995/) (2025)
- [Continuous Edit Distance, Geodesics and Barycenters of Time-varying Persistence Diagrams](https://mlsanity.com/paper/2512.12939/) (2025)
- [DebrisTracer: Reliable Tracking in Hypervelocity Impact Fast Imaging](https://mlsanity.com/paper/2607.15986/) (2026)

## Abstract (arXiv)

This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.