Computing the Bottleneck Distance between Persistent Homology Transforms
This work addresses computational bottlenecks in topological data analysis for shape comparison, offering incremental algorithmic improvements.
The paper tackles the problem of efficiently computing the bottleneck distance between Persistent Homology Transforms (PHTs) for shape comparison, improving the time complexity from O(n^6) to O(n^5) for the integral objective and providing O(n^3) and O(n^5) algorithms for the max objective in 2D and 3D, respectively.
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$.