pith. sign in

arxiv: 2512.00821 · v2 · submitted 2025-11-30 · 💻 cs.CG

Computing the Bottleneck Distance between Persistent Homology Transforms

Michael Kerber , Elena Xinyi Wang This is my paper

Pith reviewed 2026-05-17 03:24 UTC · model grok-4.3

classification 💻 cs.CG
keywords persistent homology transformbottleneck distancekinetic data structurescomputational geometrytopological data analysisshape comparison
0
0 comments X

The pith

Algorithms compute the bottleneck distance between persistent homology transforms in Õ(n^5) time for the integral and Õ(n^3) or Õ(n^5) for the maximum.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops faster algorithms to compare two shapes represented by their persistent homology transforms. These transforms collect persistence diagrams from height functions in every direction on the sphere. Rather than sampling directions, the methods track how the bottleneck distance between diagrams changes as the direction varies continuously. This yields an improved Õ(n^5) bound for the integral of the distance over all directions, replacing an earlier Õ(n^6) bound. Separate algorithms achieve Õ(n^3) time for the maximum distance in two dimensions and Õ(n^5) time in three dimensions.

Core claim

By maintaining a kinetic data structure over critical directions where the optimal matching between persistence diagrams changes, the integral of the bottleneck distance can be computed exactly in Õ(n^5) time while the maximum distance over directions can be found in Õ(n^3) time in R^2 and Õ(n^5) time in R^3.

What carries the argument

Kinetic data structure that enumerates and processes the finite sequence of directions at which the bottleneck matching between persistence diagrams changes.

If this is right

  • Exact comparison of shapes becomes feasible without relying on direction sampling.
  • Collections of three-dimensional objects can be compared using the maximum objective at reduced cost.
  • The same event-tracking technique may extend the integral computation to additional shape classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The kinetic approach could be adapted to other diagram distances such as Wasserstein.
  • Practical implementations might benefit from early termination when the running maximum already exceeds a user threshold.
  • The bounds suggest that higher-dimensional cases remain computationally heavy but still polynomial.

Load-bearing premise

Changes in the optimal bottleneck matching occur only at a finite, enumerable set of directions that the kinetic structure can locate without missing any transitions.

What would settle it

Run the new algorithm on two simple polyhedra whose persistence diagrams are known explicitly, then compare the output integral against a high-resolution numerical quadrature of the distance function sampled at millions of directions.

Figures

Figures reproduced from arXiv: 2512.00821 by Elena Xinyi Wang, Michael Kerber.

Figure 1
Figure 1. Figure 1: Construction of the bipartite graph G based on the persistence diagrams X and Y . given as finite lists of off-diagonal points. For any off-diagonal point z = (z1, z2), the orthogonal projection to the diagonal is z ′ = ((z1 + z2)/2,(z1 + z2)/2). Let X (resp. Y ) be the set of orthogonal projections of the points in X (resp. Y ). Set U = X ⊔ Y and V = Y ⊔ X. We define the complete bipartite graph G = (U ⊔ … view at source ↗
Figure 2
Figure 2. Figure 2: On the left are two simplices with vertices [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

The Persistent Homology Transform (PHT) summarizes a shape in $\mathbb{R}^m$ by collecting persistence diagrams obtained from linear height filtrations in all directions on $\mathbb{S}^{m-1}$. It enjoys strong theoretical guarantees, including continuity, stability, and injectivity on broad classes of shapes. 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 \textit{integral} of bottleneck distance over all angles via a kinetic data structure. We improve the integral objective to $\tilde O(n^5)$ in place of earlier $\tilde O(n^6)$ bound. For the \textit{max} objective, we give a $\tilde O(n^3)$ algorithm in $\mathbb{R}^2$ and a $\tilde O(n^5)$ algorithm in $\mathbb{R}^3$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents algorithms for computing the bottleneck distance between Persistent Homology Transforms (PHTs) of two shapes in R^m. It improves the integral objective to Õ(n^5) time (from prior Õ(n^6)), and for the max objective gives an Õ(n^3) algorithm in R^2 and an Õ(n^5) algorithm in R^3, relying on kinetic data structures that maintain the current bottleneck matching as the direction varies continuously on S^{m-1}.

Significance. If the central claims hold, the work advances exact, non-sampling comparison of PHTs, which are known to be continuous, stable, and injective on broad shape classes. The kinetic maintenance of bottleneck matchings and the improved asymptotics for both integral and max objectives represent a concrete algorithmic contribution in computational geometry and topological data analysis. No machine-checked proofs or reproducible code are mentioned, but the parameter-free derivation of the event-based accumulation between critical directions is a positive feature if fully substantiated.

major comments (2)
  1. [Kinetic data structure for integral objective] Kinetic data structure construction (integral objective): the Õ(n^5) bound rests on the assumption that all changes to the optimal bottleneck matching occur at finitely many algebraically computable critical directions (birth/death swaps and equal-length matching swaps) that can be predicted from the current diagram without exhaustive search or missed transitions. For general simplicial complexes the persistence coordinates are roots of polynomials whose degree grows with the filtration; the manuscript must bound this algebraic degree and prove that the kinetic certificate never misses a crossing, as this is load-bearing for the claimed improvement over the prior Õ(n^6) bound.
  2. [Max objective in R^3] Max-objective algorithm in R^3: the Õ(n^5) claim similarly depends on enumerating and tracking events on S^2 without hidden logarithmic factors or post-hoc degeneracy assumptions. A concrete complexity analysis of event prediction and interval-cost accumulation is required to confirm the bound.
minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly define the Õ notation and reference the prior Õ(n^6) result being improved upon.
  2. [Introduction] Notation for the sphere S^{m-1} and the height filtrations could be introduced with a short preliminary paragraph for readers outside computational geometry.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on the manuscript. We address each major comment below, clarifying the underlying assumptions and indicating the revisions we will make to strengthen the rigor of the analysis.

read point-by-point responses

  1. Referee: [Kinetic data structure for integral objective] Kinetic data structure construction (integral objective): the Õ(n^5) bound rests on the assumption that all changes to the optimal bottleneck matching occur at finitely many algebraically computable critical directions (birth/death swaps and equal-length matching swaps) that can be predicted from the current diagram without exhaustive search or missed transitions. For general simplicial complexes the persistence coordinates are roots of polynomials whose degree grows with the filtration; the manuscript must bound this algebraic degree and prove that the kinetic certificate never misses a crossing, as this is load-bearing for the claimed improvement over the prior Õ(n^6) bound.

    Authors: We agree that an explicit bound on algebraic degree and a proof of completeness for the kinetic certificate are necessary to fully substantiate the Õ(n^5) bound. In the manuscript we model shapes as simplicial complexes whose height filtrations assign to each simplex the maximum vertex height; consequently birth and death times are linear functions of the direction. Critical directions arise from equating bottleneck costs of adjacent matchings, yielding polynomial equations of bounded degree (at most 4). We will add a dedicated subsection that states this degree bound, enumerates the O(n^5) candidate events, and proves that the certificate maintained by the kinetic data structure detects every crossing without omission. This revision will make the improvement over the prior Õ(n^6) bound rigorous. revision: yes

  2. Referee: [Max objective in R^3] Max-objective algorithm in R^3: the Õ(n^5) claim similarly depends on enumerating and tracking events on S^2 without hidden logarithmic factors or post-hoc degeneracy assumptions. A concrete complexity analysis of event prediction and interval-cost accumulation is required to confirm the bound.

    Authors: We concur that a concrete complexity analysis for the spherical case is required. The R^3 algorithm lifts the 2D kinetic maintenance to S^2 by tracking events where the current bottleneck matching ceases to be optimal. Candidate events are generated by solving low-degree polynomial systems on the sphere; under general position these are processed with a priority queue in amortized constant time per event. We will insert a new subsection that counts the total number of events, shows that interval-cost accumulation for the max objective incurs no extra logarithmic factors, and explains how symbolic perturbation resolves degeneracies without changing the Õ(n^5) asymptotic. This will confirm the claimed bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic improvements are independent constructions

full rationale

The paper derives improved time bounds (Õ(n^5) integral, Õ(n^3)/Õ(n^5) max) for bottleneck distance on PHTs by extending kinetic data structures to track critical events on the sphere. These steps rely on standard computational geometry primitives (event prediction, certificate maintenance) whose validity is external to the present work and not reduced to self-definition, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain remains self-contained against external benchmarks in kinetic algorithms and persistent homology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of persistence diagrams and the combinatorial structure of critical directions on the sphere; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Persistence diagrams obtained from linear height filtrations are stable and can be compared via bottleneck distance.
    This is invoked implicitly when defining the distance between PHTs.
  • domain assumption The set of directions where the bottleneck matching changes is finite and can be tracked combinatorially.
    Required for the kinetic data structure to achieve the stated polynomial bounds.

pith-pipeline@v0.9.0 · 5460 in / 1523 out tokens · 35444 ms · 2026-05-17T03:24:11.057499+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Asymptotic improvements on the ex- act matching distance for 2-parameter persistence.Journal of Computational Geometry, 14(1):309–342, Dec

    Havard Bakke Bjerkevik and Michael Kerber. Asymptotic improvements on the ex- act matching distance for 2-parameter persistence.Journal of Computational Geometry, 14(1):309–342, Dec. 2023

    work page 2023

  2. [2]

    Geometric Matching and Bottleneck Problems

    Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric Matching and Bottleneck Problems. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:15, Dagstuhl, Germany, 2024. Schloss D...

    work page 2024

  3. [3]

    Perslay: A neural network layer for persistence diagrams and new graph topo- logical signatures

    Mathieu Carri` ere, Frederic Chazal, Yuichi Ike, Theo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topo- logical signatures. In Silvia Chiappa and Roberto Calandra, editors,Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 ofProce...

    work page 2020

  4. [4]

    Vines and vineyards by updating persistence in linear time

    David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. InProceedings of the Twenty-Second Annual Sym- posium on Computational Geometry, SCG ’06, page 119–126, New York, NY, USA, 2006. Association for Computing Machinery

    work page 2006

  5. [5]

    How many directions determine a shape and other sufficiency results for two topological transforms.Transactions of the American Mathematical Society, Series B, 2018

    Justin Curry, Sayan Mukherjee, and Katharine Turner. How many directions determine a shape and other sufficiency results for two topological transforms.Transactions of the American Mathematical Society, Series B, 2018

    work page 2018

  6. [6]

    Dey and Cheng Xin

    Tamal K. Dey and Cheng Xin. Computing Bottleneck Distance for 2-D Interval Decom- posable Modules. In Bettina Speckmann and Csaba D. T´ oth, editors,34th International Symposium on Computational Geometry (SoCG 2018), volume 99 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz...

    work page 2018

  7. [7]

    Cam- bridge University Press, 1 edition, 2017

    Tamal Krishna Dey and Yusu Wang.Computational Topology for Data Analysis. Cam- bridge University Press, 1 edition, 2017

    work page 2017

  8. [8]

    Herbert Edelsbrunner and John Harer.Computational Topology - an Introduction.Amer- ican Mathematical Society, 2010

    work page 2010

  9. [9]

    Merge trees of periodic filtrations, 2024

    Herbert Edelsbrunner and Teresa Heiss. Merge trees of periodic filtrations, 2024

    work page 2024

  10. [10]

    Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems.Algorithmica, 31(1):1–28, Sep 2001

    work page 2001

  11. [11]

    Persistent homology and Euler integral transforms.Journal of Applied and Computational Topology, 2(1):55–60, Oct 2018

    Robert Ghrist, Rachel Levanger, and Huy Mai. Persistent homology and Euler integral transforms.Journal of Applied and Computational Topology, 2(1):55–60, Oct 2018

    work page 2018

  12. [12]

    Clique topology reveals intrinsic geometric structure in neural correlations.Proceedings of the National Academy of Sciences, 112(44):13455–13460, 2015

    Chad Giusti, Eva Pastalkova, Carina Curto, and Vladimir Itskov. Clique topology reveals intrinsic geometric structure in neural correlations.Proceedings of the National Academy of Sciences, 112(44):13455–13460, 2015

    work page 2015

  13. [13]

    A survey of topological machine learning methods.Frontiers in Artificial Intelligence, Volume 4 - 2021, 2021

    Felix Hensel, Michael Moor, and Bastian Rieck. A survey of topological machine learning methods.Frontiers in Artificial Intelligence, Volume 4 - 2021, 2021

    work page 2021

  14. [14]

    Escolar, Kaname Mat- sue, and Yasumasa Nishiura

    Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson G. Escolar, Kaname Mat- sue, and Yasumasa Nishiura. Hierarchical structures of amorphous solids characterized by persistent homology.Proceedings of the National Academy of Sciences, 113(26):7035–7040, 2016

    work page 2016

  15. [15]

    Hopcroft and Richard M

    John E. Hopcroft and Richard M. Karp. Ann 5/2 algorithm for maximum matchings in bipartite graphs.SIAM J. Comput., 2(4):225–231, Dec 1973. 15

    work page 1973

  16. [16]

    Geometry helps to compare persistence diagrams.ACM J

    Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry helps to compare persistence diagrams.ACM J. Exp. Algorithmics, 22, sep 2017

    work page 2017

  17. [17]

    Knuth.The Art of Computer Programming, Volume 3: Sorting and Searching

    Donald E. Knuth.The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd edition, 1998. Section 5.1.1

    work page 1998

  18. [18]

    The kinetic hourglass data struc- ture for computing the bottleneck distance of dynamic data, 2025

    Elizabeth Munch, Elena Xinyi Wang, and Carola Wenk. The kinetic hourglass data struc- ture for computing the bottleneck distance of dynamic data, 2025

    work page 2025

  19. [19]

    Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawe l D lotko, Ran Levi, Kathryn Hess, and Henry Markram

    Michael W. Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawe l D lotko, Ran Levi, Kathryn Hess, and Henry Markram. Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers in Computational Neuroscience, Volume 11 - 2017, 2017

    work page 2017

  20. [20]

    Katharine Turner, Sayan Mukherjee, and Doug M. Boyer. Persistent homology transform for modeling shapes and surfaces.Information and Inference: A Journal of the IMA, 3(4):310–344, 12 2014. A Properties of difference curves A.1 Local maxima Lemma A.1.LetK, K ′ ⊂R 2 be simplicial complexes, and let∆ α,σ(ω)be a difference curve for simplicesα∈Kandσ∈K ′ withω...

    work page 2014

  21. [21]

    Insertion overlaps: WhenI α =I β over some region

    work page

  22. [22]

    Proof.In the bottleneck matching, each edge in the bipartite graph corresponds to a specific pair of simplices, not just their geometric values

    Difference overlaps: When ∆ α,σ = ∆β,τ over some region due to shared active vertices 17 B.2 Why Overlaps Don’t Affect the Algorithm Despite these geometric coincidences, our algorithm remains correct because: Lemma B.1.Each difference curve∆ α,σ maintains a unique combinatorial identity determined by the ordered pair(α, σ), independent of geometric overl...

    work page

  23. [23]

    Great circle arcs map to circles and lines in the plane

    work page

  24. [24]

    Disjoint arc families remain disjoint after projection

    work page

  25. [25]

    Each projected curve can be decomposed intoO(1)x-monotone arcs. Proof.Stereographic projection from the north pole (0,0,1) maps a point (θ, ϕ) onS 2 to (x, y) = sinϕcosθ 1−cosϕ , sinϕsinθ 1−cosϕ Great circles onS 2 are intersections with planes through the origin. Under stereographic projection, these map to circles in the plane (or lines if the plane pas...

    work page