Geometry Helps to Compare Persistence Diagrams

DOI10.1145/3064175zbMath1414.68129arXiv1606.03357OpenAlexW2294510945MaRDI QIDQ4577947

Dmitriy Morozov, Arnur Nigmetov, Michael Kerber

Publication date: 6 August 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.03357

zbMATH Keywords

assignment problemsbipartite matchingpersistent homologyk-d tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other homology theories in algebraic topology (55N35)

Related Items

A feasibility study for a persistent homology-based \(k\)-nearest neighbor search algorithm in melanoma detection ⋮ Signal classification with a point process distance on the space of persistence diagrams ⋮ Topological Data Analysis on Simple English Wikipedia Articles ⋮ Persistence Flamelets: Topological Invariants for Scale Spaces ⋮ Cancer Fingerprints by Topological Data Analysis ⋮ Bayesian topological learning for classifying the structure of biological networks ⋮ Unnamed Item ⋮ Functional summaries of persistence diagrams ⋮ Topological learning for brain networks ⋮ On the Stability of Multigraded Betti Numbers and Hilbert Functions ⋮ Bottleneck profiles and discrete Prokhorov metrics for persistence diagrams ⋮ Filtration simplification for persistent homology via edge contraction ⋮ Same But Different: Distance Correlations Between Topological Summaries ⋮ Computing the interleaving distance is NP-hard ⋮ Spatiotemporal persistent homology for dynamic metric spaces ⋮ Optimal transport: discretization and algorithms ⋮ Barcode embeddings for metric graphs ⋮ Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computational Complexity of the Interleaving Distance ⋮ Unnamed Item ⋮ Generalized persistence diagrams for persistence modules over posets ⋮ Tropical Sufficient Statistics for Persistent Homology ⋮ Persistent topology of protein space ⋮ Compression for \(2\)-parameter persistent homology ⋮ Metric Spaces with Expensive Distances ⋮ An Overview of the Topology ToolKit ⋮ Supervised learning with indefinite topological Kernels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stability of persistence diagrams
• The auction algorithm for the transportation problem
• Lipschitz functions have \(L_{p}\)-stable persistence
• Exploring uses of persistent homology for statistical analysis of landmark-based shape data
• Parallel synchronous and asynchronous implementations of the auction algorithm
• The auction algorithm: A distributed relaxation method for the assignment problem
• Topological persistence and simplification
• Geometry Helps in Matching
• Algorithms for the Assignment and Transportation Problems
• Assignment Problems
• Space-time tradeoffs for approximate nearest neighbor searching
• Multidimensional binary search trees used for associative searching
• Improvements on geometric pattern matching problems
• Geometry Helps to Compare Persistence Diagrams
• Approximation algorithms for bipartite matching with metric and geometric costs
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Geometry helps in bottleneck matching and related problems