2026-09-05T11:58:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25869 2026-06-23T12:59:56Z ddc:004 open_access

Computing the Bottleneck Distance Between Persistent Homology Transforms Kerber, Michael Wang, Elena Xinyi Kinetic data structure bottleneck distance persistent homology transform vineyards The Persistent Homology Transform (PHT) summarizes a shape in ℝ^m by collecting persistence diagrams obtained from linear height filtrations in all directions on 𝕊^{m-1}. It enjoys strong theoretical guarantees, including continuity, stability, and injectivity. A natural way to compare two PHTs is to use the bottleneck distance between their diagrams as the direction varies. Prior work has either compared PHTs by sampling directions or, in 2D, computed the exact integral of bottleneck distance over all angles via a kinetic data structure. We improve the integral objective to Õ(n⁵) in place of the earlier Õ(n⁶) bound, where n denotes the number of simplices. For the max objective, we give an Õ(n³) expected-time algorithm in ℝ² and an Õ(n⁵) expected-time algorithm in ℝ³. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Kerber and Elena Xinyi Wang 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.62 urn:nbn:de:0030-drops-258693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.62 eng https://creativecommons.org/licenses/by/4.0/legalcode