An Interleaving Distance for Ordered Merge Trees

Research output: Contribution to conferencePaperAcademic

19 Downloads (Pure)

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.
Original languageEnglish
Pages2:1-2:8
Number of pages8
Publication statusPublished - Mar 2024
Event40th European Workshop on Computational Geometry (EuroCG 2024) - Ioannina, Greece
Duration: 13 Mar 202415 Mar 2024

Conference

Conference40th European Workshop on Computational Geometry (EuroCG 2024)
Country/TerritoryGreece
CityIoannina
Period13/03/2415/03/24

Fingerprint

Dive into the research topics of 'An Interleaving Distance for Ordered Merge Trees'. Together they form a unique fingerprint.

Cite this