Computing the Bottleneck Distance Between Persistent Homology Transforms

Let ${\omega }^{\ast }$ be the direction that attains $d_{\mathrm{\infty }}$. By Lemma 2, if the bottleneck distance at ${\omega }^{\ast }$ is realized by a unique difference curve in a neighborhood, then ${\omega }^{\ast }$ must be a local maximum of that difference curve, giving case (1). This includes both matched pairs (when $\alpha \in K,\sigma \in K^{\prime }$) and unmatched point persistence (when $\alpha ,\sigma$ are from the same complex). Otherwise, at least two curves achieve the same maximum value at ${\omega }^{\ast }$, giving case (2). Note that intersections of insertion curves (where the persistence diagram changes combinatorially) form a special case of (2), as when two insertion curves $I_{\alpha },I_{\beta }$ from the same complex coincide, all difference curves of the form ${\mathrm{\Delta }}_{\alpha ,\sigma }$ and ${\mathrm{\Delta }}_{\beta ,\sigma }$ are equal. $◀$

There are $O(n^2)$ difference curves: $O(n^2)$ from pairs $(\alpha ,\sigma )\in K\times K^{\prime }$, plus $O(n^2)$ from pairs within the same complex. Each has $O(1)$ local maxima (see the full version for the explicit bound), contributing $O(n^2)$ type-(1) candidates. For type-(2) candidates, each pair of difference curves intersects at $O(1)$ heights, giving $\left(\genfrac{}{}{0pt}{}{O(n^2)}{2}\right)=O(n^4)$ intersections total. Thus the total number of candidates is $O(n^4)$. $◀$

Given a threshold $\lambda \ge 0$, we decide whether $d_{\mathrm{\infty }}\le \lambda$ by sweeping $\omega$ around ${𝕊}^1$ and maintaining a bottleneck matching. As $\omega$ rotates, we update the persistence diagrams at $O(n^2)$ insertion-curve intersections and perform single augmenting-path updates whenever an edge weight crosses the threshold. This decision procedure runs in $\tilde{O}(n^3)$ time.

By Theorem 4, $d_{\mathrm{\infty }}$ is attained at one of $O(n^4)$ candidate values corresponding to intersections of difference curves and their local maxima. These candidates can be enumerated and sorted in $O(n^4\log n)$ time. Combined with binary search using our decision procedure, this yields an $O(n^4\log n+n^3\mathrm{polylog}(n))=\tilde{O}(n^4)$ algorithm.

By Theorem 4, there are $O(n^4)$ total candidates where $d_{\mathrm{\infty }}$ could be attained. To achieve $\tilde{O}(n^3)$ time, we avoid enumerating all candidates.

We call a candidate an $\alpha$-candidate if it arises from a difference curve ${\mathrm{\Delta }}_{\alpha ,\sigma }$ for some $\sigma$ (when $\alpha \in K$), from ${\mathrm{\Delta }}_{\tau ,\alpha }$ for some $\tau$ (when $\alpha \in K^{\prime }$), or from $|I_{\alpha }(\omega )-I_{\beta }(\omega )|/2$ for some $\beta$ in the same complex as $\alpha$.

We maintain a height band $({\lambda }_1,{\lambda }_2]$ satisfying $d_{\mathrm{\infty }}>{\lambda }_1$ and $d_{\mathrm{\infty }}\le {\lambda }_2$. We process simplices from both complexes in random order. For each simplex $\alpha$, we apply:

1. 1.

   Existence predicate: Tests if any $\alpha$-candidate lies in $({\lambda }_1,{\lambda }_2]$ in $O(n^2\mathrm{polylog}(n))$ time. If no candidate exists in the band, we skip to the next simplex.

2. 2.

   Band-refinement predicate: If the existence test is positive, we enumerate all $O(n^3)$ $\alpha$-candidates in the band and refine via binary search in $O(n^3\mathrm{polylog}(n))$ time.

The resulting total running time is $O(n\cdot n^2\mathrm{polylog}(n)+C\cdot n^3\mathrm{polylog}(n))$, where $C$ is the number of band-refinement calls. As we will show, processing the simplices in a random order ensures $𝔼[C]=O(\log n)$, yielding expected time $\tilde{O}(n^3)$.

We initialize at $\omega =0$ by computing a perfect matching in $G_{\lambda }(0)$ using Hopcroft-Karp in $O(n^{2.5})$ [15]; if none exists, $d_{\mathrm{\infty }}>\lambda$.

As $\omega$ increases from $0$ to $2\pi$, the bipartite graph $G_{\lambda }(\omega )$ changes only at discrete events:

• $\mathrm{■}$

  Diagram changes: At intersections of insertion curves, points move to or from the diagonal in the persistence diagrams, updating the bipartite graph structure.

• $\mathrm{■}$

  Threshold crossings: When a difference curve ${\mathrm{\Delta }}_{\alpha ,\sigma }(\omega )$ crosses the threshold $\lambda$, the corresponding edge enters or leaves $G_{\lambda }(\omega )$.

A matching $M$ is maintained across the sweep. At each event:

• $\mathrm{■}$

  If a new edge enters $G_{\lambda }(\omega )$ (weight decreases below $\lambda$), $M$ remains valid.

• $\mathrm{■}$

  If an edge leaves $G_{\lambda }(\omega )$ (weight exceeds $\lambda$) and is not in $M$, then $M$ remains valid.

• $\mathrm{■}$

  If an edge $(u,v)\in M$ becomes invalid, Hall’s theorem guarantees that a new perfect matching exists if and only if there is an augmenting path from the newly exposed vertices. We search for such a path in $O(n\log n)$ time using the geometric structure [10]. If found, we augment along this path to restore a perfect matching. If no augmenting path exists, then $G_{\lambda }(\omega )$ has no perfect matching, so $d_B>\lambda$ at this $\omega$, implying $d_{\mathrm{\infty }}>\lambda$.

At diagram change events (insertion curve intersections), we update the persistence diagrams using the vineyard algorithm [4]. When two insertion curves $I_{\alpha }$ and $I_{\beta }$ from the same complex intersect, the relative order of exactly two simplices changes in the filtration. Following Bjerkevik and Kerber [1], this corresponds to a single transposition in the barcode pairing, which can be updated in $O(n)$ time.

If the sweep completes with a valid perfect matching at every $\omega$, then $d_{\mathrm{\infty }}\le \lambda$.

At each event, we either update the diagram structure in $O(n)$ time (vineyard update for insertion curve intersections) or search for a single augmenting path in $O(n\log n)$ time (for threshold crossings). With $O(n^2)$ total events from Lemma 3, the total time is $\tilde{O}(n^3)$. $◀$

Before processing individual simplices, we refine the band to exclude certain events from its interior: let $S$ be the set containing all local maxima of difference curves ${\mathrm{\Delta }}_{\alpha ,\sigma }$ for all pairs (including both different-complex and same-complex pairs), all intra-$\alpha$ intersections where ${\mathrm{\Delta }}_{\alpha ,{\sigma }_1}(\omega )={\mathrm{\Delta }}_{\alpha ,{\sigma }_2}(\omega )$ for some $\omega \in {𝕊}^1$ and distinct ${\sigma }_1,{\sigma }_2$, and all intra-$\tau$ intersections where ${\mathrm{\Delta }}_{{\beta }_1,\tau }(\omega )={\mathrm{\Delta }}_{{\beta }_2,\tau }(\omega )$ for distinct ${\beta }_1,{\beta }_2$.

Since there are $O(n^2)$ difference curves, each with $O(1)$ local maxima, we have $O(n^2)$ maxima total. For intra-intersections, each of the $O(n)$ simplices in $K$ contributes $\left(\genfrac{}{}{0pt}{}{O(n)}{2}\right)=O(n^2)$ pairs of curves that could intersect, with $O(1)$ intersection points each, giving $O(n^3)$ intra-$\alpha$ intersections. Similarly for intra-$\tau$ intersections. Thus $|S|=O(n^3)$.

We binary search with the decision procedure to find the largest value in $S$ below $d_{\mathrm{\infty }}$ and the smallest at or above it, setting these as ${\lambda }_1$ and ${\lambda }_2$. The resulting band $({\lambda }_1,{\lambda }_2]$ contains no intra-events in its interior. This takes $O(n^3\mathrm{polylog}n)$ time.

The bottleneck distance function $H(\omega )$ is continuous on $S^2$. At any ${\omega }^{\ast }\in S^2$ where $d_{\mathrm{\infty }}$ is attained, consider the difference surfaces achieving the maximum value $H({\omega }^{\ast })$.

If a unique surface ${\mathrm{\Delta }}_{\alpha ,\sigma }$ achieves this maximum in a neighborhood of ${\omega }^{\ast }$, then by continuity, ${\omega }^{\ast }$ must be a local maximum of that surface (case 1). This covers both matched pairs and unmatched persistence. If exactly two surfaces achieve the maximum at ${\omega }^{\ast }$ but no other surface does so nearby, then ${\omega }^{\ast }$ lies on their intersection curve on ${𝕊}^2$. Since $H$ is locally determined by these two surfaces along the curve, ${\omega }^{\ast }$ must be a local maximum along this curve (case 2). If three or more surfaces achieve the maximum at ${\omega }^{\ast }$, then generically three surfaces meet at isolated points, giving case 3. $◀$

We count candidates by type. Type 1 has $O(n^2)$ difference surfaces (including both between-complex and within-complex pairs), each having $O(1)$ maxima, contributing $O(n^2)$ candidates. Type 2 consists of $\left(\genfrac{}{}{0pt}{}{O(n^2)}{2}\right)=O(n^4)$ pairs with $O(1)$ maxima per intersection curve, giving $O(n^4)$ candidates. Type 3 is $\left(\genfrac{}{}{0pt}{}{O(n^2)}{3}\right)=O(n^6)$ triple intersection points. This gives us the total of $O(n^6)$ candidates. $◀$

Given threshold $\lambda$, we decide whether $d_{\mathrm{\infty }}\le \lambda$ by traversing an arrangement on ${𝕊}^2$. Similar to the 2D case, we track two types of events:

• $\mathrm{■}$

  Diagram changes: $O(n^2)$ intersection curves between insertion surfaces where the persistence diagrams change combinatorially;

• $\mathrm{■}$

  Threshold crossings: $O(n^2)$ curves on ${𝕊}^2$ where difference surfaces cross the threshold $\lambda$.

Overlaying these curves yields an arrangement of $O(n^4)$ complexity on ${𝕊}^2$. We traverse the dual of this arrangement via an Euler tour by traversing each edge twice, maintaining a bottleneck matching throughout. Each diagram change requires $O(n)$ time to update the barcode pairing using the vineyard algorithm, while each threshold crossing may require $O(n\log n)$ time for augmenting path search. The total complexity is $\tilde{O}(n^5)$.

We maintain a band $({\lambda }_1,{\lambda }_2]$ containing $d_{\mathrm{\infty }}$ and process simplices in random order. For each simplex $\alpha$:

1. 1.

   Existence predicate: Test if any $\alpha$-candidate lies in the band. Following the approach from 2D adapted to surfaces: for fixed $\alpha$ and $\sigma \in K^{\prime }$, consider the surface ${\mathrm{\Delta }}_{\alpha ,\sigma }$. For each $\beta \in K\setminus \{\alpha \}$, compute intersection curves with all ${\mathrm{\Delta }}_{\beta ,\tau }$ surfaces. Within the band, these $O(n)$ curves form disjoint arcs on ${𝕊}^2$ (no intra-$\beta$ intersections after pre-refinement). Similarly get $O(n)$ disjoint arcs from surfaces involving $\gamma \in K\setminus \{\alpha ,\beta \}$. Check for red-blue intersections in $O(n\log n)$ time. Testing all combinations takes $O(n^4\log n)$.

2. 2.

   Band refinement: If positive, enumerate all $\alpha$-candidates in the band: $O(n^5)$ triple intersections, $O(n^3)$ curve maxima, $O(n)$ surface maxima. Then refine via binary search in $\tilde{O}(n^5)$ time.

Using the same randomization analysis as 2D, we expect $O(\log n)$ refinements. This results in total expected complexity of $O(n\cdot n^4\log n+\log n\cdot n^5\mathrm{polylog}n)=\tilde{O}(n^5)$.

We construct the arrangement $𝒜$ and compute an Euler tour of its dual graph, treated as a planar graph embedded on ${𝕊}^2$. The tour visits each edge twice, once in each direction.

Starting from an arbitrary face with a perfect matching in $G_{\lambda }(\omega )$, we traverse the tour and maintain the matching throughout. At insertion curve crossings where the persistence diagram changes, we update the barcode pairing via a single transposition in $O(n)$ time using the vineyard algorithm. At threshold crossings where an edge weight exceeds $\lambda$, we search for an augmenting path in $O(n\log n)$ time. If no augmenting path exists, we conclude $d_{\mathrm{\infty }}>\lambda$ and terminate. If the tour completes with valid matchings maintained throughout, then $d_B(\omega )\le \lambda$ for all $\omega \in {𝕊}^2$, hence $d_{\mathrm{\infty }}\le \lambda$.

The arrangement has $O(n^4)$ edges in total. The $O(n^4)$ diagram changes contribute $O(n^5)$ total time at $O(n)$ each, while the $O(n^2)$ threshold crossings contribute $\tilde{O}(n^3)$ at $O(n\log n)$ each. However, the bottleneck arises from traversing all $O(n^4)$ edges of the arrangement, where at each edge crossing we may need to update the matching. Since each edge crossing potentially requires $O(n\log n)$ time for augmenting path search, the total complexity is $O(n^4\cdot n\log n)=\tilde{O}(n^5)$. $◀$

Before processing individual simplices, we refine the band to exclude all intra-events from its interior. We call a triple intersection point ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,\tau }\cap {\mathrm{\Delta }}_{\gamma ,\rho }$ an intra-event if any two of the six involved simplices are equal. Let $S$ be the set containing all $O(n^2)$ local maxima of difference surfaces, all $O(n^4)$ local maxima along surface intersection curves, and all intra-event triple intersections. Since there are $O(n^5)$ ways to choose 5 distinct simplices and $O(1)$ ways to make two of them equal, we have $|S|=O(n^5)$. We use binary search with the decision procedure to find the largest value in $S$ that is (setting ${\lambda }_1$) and the smallest value in $S$ that is $\ge d_{\mathrm{\infty }}$ (setting ${\lambda }_2$), yielding the band $({\lambda }_1,{\lambda }_2]$ that contains $d_{\mathrm{\infty }}$ but excludes all values of $S$ from its interior. This takes $O(n^5\mathrm{polylog}n)$ time.

Fix $\alpha \in K$ and $\sigma \in K^{\prime }$, giving the difference surface ${\mathrm{\Delta }}_{\alpha ,\sigma }$. We seek triple intersection points of the form ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,\tau }\cap {\mathrm{\Delta }}_{\gamma ,\rho }$ where $\beta ,\gamma \in K\setminus \{\alpha \}$ and $\tau ,\rho \in K^{\prime }$, with the intersection value lying in $({\lambda }_1,{\lambda }_2]$.

For fixed $\beta \in K\setminus \{\alpha \}$, compute the intersection curves between ${\mathrm{\Delta }}_{\alpha ,\sigma }$ and all surfaces ${\mathrm{\Delta }}_{\beta ,\tau }$ for $\tau \in K^{\prime }$. Each pair of surfaces intersects along great circle arcs on ${𝕊}^2$ where ${\mathrm{\Delta }}_{\alpha ,\sigma }(\omega )={\mathrm{\Delta }}_{\beta ,\tau }(\omega )$. We obtain $O(n)$ intersection curves on ${𝕊}^2$.

The crucial observation is that when we restrict to the band , these $O(n)$ curves become disjoint arcs. Any intersection between curves ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,{\tau }_1}$ and ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,{\tau }_2}$ would yield a triple point where ${\mathrm{\Delta }}_{\alpha ,\sigma }={\mathrm{\Delta }}_{\beta ,{\tau }_1}={\mathrm{\Delta }}_{\beta ,{\tau }_2}$. This is an intra-event (two surfaces share $\beta$), excluded from the band’s interior via pre-refinement.

Similarly, for fixed $\gamma \in K\setminus \{\alpha ,\beta \}$, the intersection curves between ${\mathrm{\Delta }}_{\alpha ,\sigma }$ and all ${\mathrm{\Delta }}_{\gamma ,\rho }$ surfaces yield another set of $O(n)$ disjoint arcs within the band. We now have two collections of arcs on the restricted domain of ${\mathrm{\Delta }}_{\alpha ,\sigma }$: the “red” arcs from $\beta$-surfaces and the “blue” arcs from $\gamma$-surfaces. A red-blue intersection corresponds to a triple point ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,\tau }\cap {\mathrm{\Delta }}_{\gamma ,\rho }$, which is an inter-intersection involving $\alpha$.

To detect red-blue intersections, we apply stereographic projection from the north pole of ${𝕊}^2$ to map the band region to a planar domain and use a sweep-line algorithm. As shown in the full version, the projection preserves the disjointness of red and blue arc families while mapping great circle arcs to well-behaved curves (circles and lines) that intersect $O(1)$ times. The sweep-line algorithm thus detects all red-blue intersections in $O(n\log n)$ time.

Iterating over all choices of $\sigma \in K^{\prime }$, $\beta \in K\setminus \{\alpha \}$, and $\gamma \in K\setminus \{\alpha ,\beta \}$ gives total complexity $O(n\cdot n\cdot n\cdot n\log n)=O(n^4\log n)$. $◀$

For each $\alpha$, the pre-refinement step excludes the $O(n)$ local maxima of difference surfaces and $O(n^2)$ local maxima of intersection curves. We only need to consider triple intersection points ${\mathrm{\Delta }}_{\alpha ,\sigma }\cap {\mathrm{\Delta }}_{\beta ,\tau }\cap {\mathrm{\Delta }}_{\gamma ,\rho }$: with $O(n)$ choices each for $\sigma ,\beta ,\tau ,\gamma ,\rho$, and $O(1)$ intersection points per triple, we get $O(n^5)$ candidates. Total enumeration takes $O(n^5)$ time. Binary search with the decision procedure then refines the band in $\tilde{O}(n^5)$ time. $◀$

We process $O(n)$ simplices from both complexes. For each simplex $\alpha$, we perform the existence test in $O(n^4\log n)$ time. If positive, we enumerate and refine in $\tilde{O}(n^5)$ time. We expect $O(\log n)$ refinements using the same analysis as in 2D. The total expected complexity is therefore $O(n\cdot n^4\log n+\log n\cdot n^5\mathrm{polylog}n)=\tilde{O}(n^5)$. $◀$