ON STEINER TREES OF THE REGULAR SIMPLEX
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
ON STEINER TREES OF THE REGULAR SIMPLEX
Original language description
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the ℓ<inf>2</inf>-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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Computational Geometry
ISSN
1920-180X
e-ISSN
1920-180X
Volume of the periodical
16
Issue of the periodical within the volume
1
Country of publishing house
CA - CANADA
Number of pages
34
Pages from-to
1-34
UT code for WoS article
001487105300001
EID of the result in the Scopus database
2-s2.0-85219284674