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!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator García-Castellanos, Alejandro
Aniss Aiman Medbouhi
Marchetti, Giovanni Luca
Bekkers, Erik J
Kragic, Danica
description 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 article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_3102578242</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>3102578242</sourcerecordid><originalsourceid>FETCH-proquest_journals_31025782423</originalsourceid><addsrcrecordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mRw8qgsSC0KLknNzEstslJwzs8tKC3JzEtX8EgtLcosLslMVgCrSMrPATKh6hR8M_MycxNzFEKKUlOLeRhY0xJzilN5oTQ3g7Kba4izh25BUX5haWpxSXxWfmlRHlAq3tjQwMjU3MLIxMiYOFUA4Pk6Ag</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>3102578242</pqid></control><display><type>article</type><title>HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees</title><source>Publicly Available Content (ProQuest)</source><creator>García-Castellanos, Alejandro ; Aniss Aiman Medbouhi ; Marchetti, Giovanni Luca ; Bekkers, Erik J ; Kragic, Danica</creator><creatorcontrib>García-Castellanos, Alejandro ; Aniss Aiman Medbouhi ; Marchetti, Giovanni Luca ; Bekkers, Erik J ; Kragic, Danica</creatorcontrib><description>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.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Algorithms ; Computation ; Delaunay triangulation ; Euclidean geometry ; Graph theory ; Heuristic methods ; Hierarchies ; Hyperbolic coordinates</subject><ispartof>arXiv.org, 2024-09</ispartof><rights>2024. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/3102578242?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>776,780,25731,36989,44566</link.rule.ids></links><search><creatorcontrib>García-Castellanos, Alejandro</creatorcontrib><creatorcontrib>Aniss Aiman Medbouhi</creatorcontrib><creatorcontrib>Marchetti, Giovanni Luca</creatorcontrib><creatorcontrib>Bekkers, Erik J</creatorcontrib><creatorcontrib>Kragic, Danica</creatorcontrib><title>HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees</title><title>arXiv.org</title><description>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.</description><subject>Algorithms</subject><subject>Computation</subject><subject>Delaunay triangulation</subject><subject>Euclidean geometry</subject><subject>Graph theory</subject><subject>Heuristic methods</subject><subject>Hierarchies</subject><subject>Hyperbolic coordinates</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mRw8qgsSC0KLknNzEstslJwzs8tKC3JzEtX8EgtLcosLslMVgCrSMrPATKh6hR8M_MycxNzFEKKUlOLeRhY0xJzilN5oTQ3g7Kba4izh25BUX5haWpxSXxWfmlRHlAq3tjQwMjU3MLIxMiYOFUA4Pk6Ag</recordid><startdate>20240909</startdate><enddate>20240909</enddate><creator>García-Castellanos, Alejandro</creator><creator>Aniss Aiman Medbouhi</creator><creator>Marchetti, Giovanni Luca</creator><creator>Bekkers, Erik J</creator><creator>Kragic, Danica</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20240909</creationdate><title>HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees</title><author>García-Castellanos, Alejandro ; Aniss Aiman Medbouhi ; Marchetti, Giovanni Luca ; Bekkers, Erik J ; Kragic, Danica</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_31025782423</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Algorithms</topic><topic>Computation</topic><topic>Delaunay triangulation</topic><topic>Euclidean geometry</topic><topic>Graph theory</topic><topic>Heuristic methods</topic><topic>Hierarchies</topic><topic>Hyperbolic coordinates</topic><toplevel>online_resources</toplevel><creatorcontrib>García-Castellanos, Alejandro</creatorcontrib><creatorcontrib>Aniss Aiman Medbouhi</creatorcontrib><creatorcontrib>Marchetti, Giovanni Luca</creatorcontrib><creatorcontrib>Bekkers, Erik J</creatorcontrib><creatorcontrib>Kragic, Danica</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content (ProQuest)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>García-Castellanos, Alejandro</au><au>Aniss Aiman Medbouhi</au><au>Marchetti, Giovanni Luca</au><au>Bekkers, Erik J</au><au>Kragic, Danica</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees</atitle><jtitle>arXiv.org</jtitle><date>2024-09-09</date><risdate>2024</risdate><eissn>2331-8422</eissn><abstract>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.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2024-09
issn 2331-8422
language eng
recordid cdi_proquest_journals_3102578242
source Publicly Available Content (ProQuest)
subjects Algorithms
Computation
Delaunay triangulation
Euclidean geometry
Graph theory
Heuristic methods
Hierarchies
Hyperbolic coordinates
title HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-31T02%3A27%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=HyperSteiner:%20Computing%20Heuristic%20Hyperbolic%20Steiner%20Minimal%20Trees&rft.jtitle=arXiv.org&rft.au=Garc%C3%ADa-Castellanos,%20Alejandro&rft.date=2024-09-09&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E3102578242%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_31025782423%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=3102578242&rft_id=info:pmid/&rfr_iscdi=true