Abstract
Merge trees are a common topological descriptor for data with a hierarchical component. The
interleaving distance, in turn, is a common distance measure for comparing merge trees. In this
abstract, we introduce a form of ordered merge trees and extend the interleaving distance to a
measure that preserves orders. Exploiting the additional structure of ordered merge trees, we then describe an O(n2) time algorithm that computes a 2-approximation of this new distance with an additive term G that captures the maximum height differences of leaves of the input merge trees.
interleaving distance, in turn, is a common distance measure for comparing merge trees. In this
abstract, we introduce a form of ordered merge trees and extend the interleaving distance to a
measure that preserves orders. Exploiting the additional structure of ordered merge trees, we then describe an O(n2) time algorithm that computes a 2-approximation of this new distance with an additive term G that captures the maximum height differences of leaves of the input merge trees.
| Original language | English |
|---|---|
| Pages | 2:1-2:8 |
| Number of pages | 8 |
| Publication status | Published - Mar 2024 |
| Event | 40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Greece Duration: 13 Mar 2024 → 15 Mar 2024 |
Conference
| Conference | 40th European Workshop on Computational Geometry (EuroCG 2024) |
|---|---|
| Country/Territory | Greece |
| City | Ioannina |
| Period | 13/03/24 → 15/03/24 |
Bibliographical note
40th European Workshop on Computational Geometry, Ioannina, Greece, March 13–15, 2024.This is an extended abstract of a presentation given at EuroCG’24.
Funding
Thijs Beurskens and Tim Ophelders are supported by the Dutch Research Council (NWO) under project numbers OCENW.M20.089 and VI.Veni.212.260, respectively.