HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912187011825664 |
|---|---|
| author | García-Castellanos, Alejandro Medbouhi, Aniss Aiman Marchetti, Giovanni Luca Bekkers, Erik J. Kragic, Danica |
| author_facet | García-Castellanos, Alejandro Medbouhi, Aniss Aiman Marchetti, Giovanni Luca Bekkers, Erik J. Kragic, Danica |
| contents | We propose HyperSteiner -- an efficient heuristic algorithm for computing Steiner minimal trees in the hyperbolic space. HyperSteiner extends the Euclidean Smith-Lee-Liebman algorithm, which is grounded in a divide-and-conquer approach involving the Delaunay triangulation. The central idea is rephrasing Steiner tree problems with three terminals as a system of equations in the Klein-Beltrami model. Motivated by the fact that hyperbolic geometry is well-suited for representing hierarchies, we explore applications to hierarchy discovery in data. Results show that HyperSteiner infers more realistic hierarchies than the Minimum Spanning Tree and is more scalable to large datasets than Neighbor Joining. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_05671 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees García-Castellanos, Alejandro Medbouhi, Aniss Aiman Marchetti, Giovanni Luca Bekkers, Erik J. Kragic, Danica Computational Geometry We propose HyperSteiner -- an efficient heuristic algorithm for computing Steiner minimal trees in the hyperbolic space. HyperSteiner extends the Euclidean Smith-Lee-Liebman algorithm, which is grounded in a divide-and-conquer approach involving the Delaunay triangulation. The central idea is rephrasing Steiner tree problems with three terminals as a system of equations in the Klein-Beltrami model. Motivated by the fact that hyperbolic geometry is well-suited for representing hierarchies, we explore applications to hierarchy discovery in data. Results show that HyperSteiner infers more realistic hierarchies than the Minimum Spanning Tree and is more scalable to large datasets than Neighbor Joining. |
| title | HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2409.05671 |