{"ID":2857550,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.09328","arxiv_id":"2510.09328","title":"Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree","abstract":"We study the problem of constructing Steiner Minimal Trees (SMTs) in hyperbolic space. Exact SMT computation is NP-hard, and existing hyperbolic heuristics such as HyperSteiner are deterministic and often get trapped in locally suboptimal configurations. We introduce Randomized HyperSteiner (RHS), a stochastic Delaunay triangulation heuristic that incorporates randomness into the expansion process and refines candidate trees via Riemannian gradient descent optimization. Experiments on synthetic data sets and a real-world single-cell transcriptomic data show that RHS outperforms Minimum Spanning Tree (MST), Neighbour Joining, and vanilla HyperSteiner (HS). In near-boundary configurations, RHS can achieve a 32% reduction in total length over HS, demonstrating its effectiveness and robustness in diverse data regimes.","short_abstract":"We study the problem of constructing Steiner Minimal Trees (SMTs) in hyperbolic space. Exact SMT computation is NP-hard, and existing hyperbolic heuristics such as HyperSteiner are deterministic and often get trapped in locally suboptimal configurations. We introduce Randomized HyperSteiner (RHS), a stochastic Delaunay...","url_abs":"https://arxiv.org/abs/2510.09328","url_pdf":"https://arxiv.org/pdf/2510.09328v2","authors":"[\"Aniss Aiman Medbouhi\",\"Alejandro García-Castellanos\",\"Giovanni Luca Marchetti\",\"Daniel Pelt\",\"Erik J Bekkers\",\"Danica Kragic\"]","published":"2025-10-10T12:31:55Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.AI\"]","methods":"[]","has_code":false}