MergeTree

A merge tree is a data structure used in topological data analysis to summarize how the connected components of sublevel sets of a real-valued function evolve as the level varies. Given a function f: X → R on a topological space X, consider the sublevel sets X_a = {x in X | f(x) ≤ a}. As a increases, new components appear at local minima and existing components merge when a passes a saddle value. The merge tree records these birth and merge events in a hierarchical, tree-like form: leaves correspond to local minima, internal nodes to merge events, and the root represents the final merged component at high levels. The height of a node typically encodes the function value at the corresponding event.

Construction and interpretation: To build a merge tree, one traces the creation of components in the sublevel sets and the moments when pairs of components merge. At each merge, the corresponding components are linked under a common ancestor in the tree. The structure provides a compact, one-dimensional summary of the scalar field’s topology, capturing the persistence of connected components across thresholds. In many settings, the merge tree is equivalent to the 0-dimensional persistence barcode for the function.

Relation to other tools: In simply connected domains with Morse-type functions, the Reeb graph can collapse to a tree, and the merge tree becomes a convenient proxy for the contour tree or Reeb graph in the sublevel-set viewpoint. It complements other summaries such as persistence diagrams and is related to split trees when considering superlevel sets.

Applications and computation: Merge trees are computed from discrete representations of functions on triangulated domains, often using union-find data structures and discrete Morse theory. They are used in data visualization, feature detection, segmentation, and quantitative analysis of scalar fields, aiding robust interpretation of complex data.