HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees

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 rephra...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-09
Main Authors: García-Castellanos, Alejandro, Aniss Aiman Medbouhi, Marchetti, Giovanni Luca, Bekkers, Erik J, Kragic, Danica
Format: Article
Language:English
Subjects:
Algorithms
Computation
Delaunay triangulation
Euclidean geometry
Graph theory
Heuristic methods
Hierarchies
Hyperbolic coordinates
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422