The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917521093820416 |
|---|---|
| author | Munch, Elizabeth Wang, Elena Xinyi Wenk, Carola |
| author_facet | Munch, Elizabeth Wang, Elena Xinyi Wenk, Carola |
| contents | The kinetic data structure (KDS) framework is a powerful tool for maintaining various geometric configurations of continuously moving objects. In this work, we introduce the kinetic hourglass, a novel KDS implementation designed to compute the bottleneck distance for geometric matching problems. We detail the events and updates required for handling general graphs, accompanied by a complexity analysis. Furthermore, we demonstrate the utility of the kinetic hourglass by applying it to compute the bottleneck distance between two persistent homology transforms (PHTs) derived from shapes in $\mathbb{R}^2$, which are topological summaries obtained by computing persistent homology from every direction in $\mathbb{S}^1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04048 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data Munch, Elizabeth Wang, Elena Xinyi Wenk, Carola Data Structures and Algorithms The kinetic data structure (KDS) framework is a powerful tool for maintaining various geometric configurations of continuously moving objects. In this work, we introduce the kinetic hourglass, a novel KDS implementation designed to compute the bottleneck distance for geometric matching problems. We detail the events and updates required for handling general graphs, accompanied by a complexity analysis. Furthermore, we demonstrate the utility of the kinetic hourglass by applying it to compute the bottleneck distance between two persistent homology transforms (PHTs) derived from shapes in $\mathbb{R}^2$, which are topological summaries obtained by computing persistent homology from every direction in $\mathbb{S}^1$. |
| title | The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04048 |