Sign up or sign in

Applied Topology

Elena Wang

Subevent of Applied Topology - Thurs. AM

Eastern Time (US & Canada)

Starts at: 2025-03-06 10:40AM

Ends at: 2025-03-06 11:00AM

Computing the Bottleneck Distance from Every Direction

Elena Wang ⟨wangx249@msu.edu⟩

Abstract:

One of the most common distances used to compare two persistence diagrams is the bottleneck distance. When the persistence diagrams of a shape in $\mathbb{R}^d$ are computed from every direction in $\mathbb{S}^{d-1}$, we obtain the persistent homology transform (PHT). An efficient way of comparing two PHTs remains unexplored. In this work, we develop a new kinetic data structure to compute the bottleneck distance between two PHTs obtained from shapes in $\mathbb{R}^2$ from every direction. We provide the events and necessary updates to maintain the distance between the diagrams using this structure. Our resulting algorithm runs in $O(n^2\log^2n)$. This is compared to the naive algorithm where $d_B$ is computed at a finite number of smartly chosen directions, which is $O(n^{7/2}\log n)$ complex. It is important to note that our algorithm provides an exact distance in every direction, while the latter is an approximation. Furthermore, we show that this data structure is not limited to the directional transform setting since the techniques apply to more general vineyard structures.

Back to events