Computing the Bottleneck Distance between Persistent Homology Transforms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917396161232896 |
|---|---|
| author | Kerber, Michael Wang, Elena Xinyi |
| author_facet | Kerber, Michael Wang, Elena Xinyi |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_00821 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing the Bottleneck Distance between Persistent Homology Transforms Kerber, Michael Wang, Elena Xinyi Computational Geometry 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$. |
| title | Computing the Bottleneck Distance between Persistent Homology Transforms |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2512.00821 |