Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.00821 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |