ON STEINER TREES OF THE REGULAR SIMPLEX

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10501813" target="_blank" >RIV/00216208:11320/25:10501813 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=zqvuQRkKdt" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=zqvuQRkKdt</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.20382/jocg.v16i1a1" target="_blank" >10.20382/jocg.v16i1a1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

ON STEINER TREES OF THE REGULAR SIMPLEX

Popis výsledku v původním jazyce

In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the ℓ&lt;inf&gt;2&lt;/inf&gt;-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution. The seminal works of Arora [1] and Mitchell [28] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [38]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [34] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology.

Název v anglickém jazyce

ON STEINER TREES OF THE REGULAR SIMPLEX

Popis výsledku anglicky

In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the ℓ&lt;inf&gt;2&lt;/inf&gt;-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution. The seminal works of Arora [1] and Mitchell [28] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [38]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [34] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computational Geometry

ISSN

1920-180X

e-ISSN

1920-180X

Svazek periodika

16

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

34

Strana od-do

1-34

Kód UT WoS článku

001487105300001

EID výsledku v databázi Scopus

2-s2.0-85219284674