An Interleaving Distance for Ordered Merge Trees

Merge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance measure for comparing merge trees. However, the interleaving distance for merge trees is solely based on the hierarchical structure, and disregards any other geometrical or topological properties that might be present in the underlying data. For example, the channel networks formed by braided rivers carry intrinsic orders induced by the relative position of channels: from one bank to another, or from upstream to downstream. In this paper, we introduce a form of ordered merge trees that does capture intrinsic order present in the data. Furthermore, we define the monotone interleaving distance, which is an order preserving distance measure for ordered merge trees. Analogous to the regular interleaving distance for merge trees, we show that the monotone variant has three equivalent definitions in terms of two maps, a single map, or a labelling. There is no efficient constant factor approximation known to compute the interleaving distance. In contrast, we describe an $O(n^2)$ time algorithm that computes a 2-approximation of the monotone interleaving distance with an additive term $G$ that captures the maximum height differences of leaves of the input merge trees. In the real world setting of river network analysis, all leaves are at height 0; hence $G$ equals 0, and our algorithm is a proper 2-approximation.