# On Steiner Trees of the Regular Simplex

Henry Fleischmann
University of Cambridge  Guillermo A. Gamboa Q.
Charles University  Karthik C. S.
Rutgers University  Josef Matějka
Charles University  Jakub Petr
Charles University

###### Abstract

In the Euclidean Steiner Tree problem, we are given as input a set of points
(called _terminals_) in the $\ell_{2}$-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 [JACM’98] and Mitchell [SICOMP’99] 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 [SICOMP’00]). 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 [Algorithmica’92] about their optimal
topology, and providing the first explicit, general construction of candidate
optimal Steiner trees for that topology.

##  1 Introduction

Given a set of points in space (called terminals), a Steiner tree of those
points is a tree connecting those points. In addition to the terminals, the
tree may contain additional points from the ambient space (called Steiner
points). Finding the minimum cost Steiner tree is one of the most fundamental
problems in Computer Science, Operations Research, and Combinatorial
Optimization [Lju21]. For example, Steiner trees arise naturally in network
design, the design of integrated circuits, location problems, machine
learning, computer vision, systems biology, and bioinformatics [CD13, Cho01,
HR92, Len12, RP08, NRRK17, BRK+12, IOSS02, RN10, TGK+16].

In this work, we focus on the Euclidean Steiner tree problem, perhaps the most
fabled setting of the problem, where the terminals lie in the Euclidean metric
space. It was first studied in full generality at least as far back as 1811
and has been discussed in letters of Gauss. For three points, the Fermat-
Toricelli problem, optimal Steiner trees were characterized completely as
early as the 1600s by Toricelli. The interested reader may see [BGTZ14] for
more details on the history of the Euclidean Steiner tree problem.

Jarník and Kössler [JK34] first derived most of the known fundamental
structural properties of Euclidean Steiner trees in 1934. The seminal work of
Gilbert and Pollak [GP68] gave additional proofs of these properties and
several others. Their structural results essentially remain the best existing
tools for analyzing high-dimensional Euclidean Steiner trees.

#### Computational Aspects.

Building on the work of Garey and Johnson [GJ77] wherein they proved that the
Rectilinear Steiner Tree problem (i.e., terminals are in $\ell_{1}$-metric
space) is $\mathsf{NP}$-hard, in a joint work with Graham [GGJ77], they proved
that the Euclidean Steiner Tree problem is also $\mathsf{NP}$-hard by a clever
planar gadget construction. In their seminal works, Arora [Aro98] and Mitchell
[Mit99] gave a polynomial-time approximation scheme ($\mathsf{PTAS}$) for the
Steiner Tree problem in all $\ell_{p}$-metric spaces, albeit in constant
dimensions. However, their work left open the hardness of approximation of the
Euclidean Steiner Tree problem in high dimensions (such as when the dimension
is at least logarithmic in the number of terminals). Trevisan [Tre00] showed
that the Rectilinear Steiner Tree problem is $\mathsf{APX}$-hard by a
reduction from the Steiner Tree problem in the Hamming metric (which was
previously shown to be $\mathsf{APX}$-hard [DJS86]). Trevisan’s reduction
appeals to the Hamming metric’s discrete combinatorial structure. In fact, an
even simpler proof can be derived from much earlier known structural results
about Hamming and Rectilinear Steiner trees (e.g., Lemma 1 of [DJS86] combined
with Theorem 4 of [Han66]).

Proving the $\mathsf{APX}$-hardness of the Steiner Tree problem in
$\ell_{p}$-metrics, for $p>1$, appears to require engaging with the delicate
structure of $\operatorname{\mathbb{R}}^{d}$ directly. Due to the
$\mathsf{PTAS}$ for the problem in fixed dimensions, any such argument
requires dealing with truly high-dimensional hard instances. Recently,
Fleischmann et al. [FGK24] recently showed that the Steiner Tree problem is
$\mathsf{APX}$-hard in the $\ell_{\infty}$-metric. They also showed that when
the set of candidate Steiner points is provided as part of the input (as a
special case of the graph Steiner Tree problem), then this discrete variant of
the Steiner Tree problem is $\mathsf{APX}$-hard in all $\ell_{p}$-metric
spaces. However, the hardness of approximation of the classical Euclidean
Steiner Tree problem remains unresolved.

######  Open Question 1.

Is the Euclidean Steiner Tree problem $\mathsf{APX}$-hard in high dimensions?

Existing techniques in the area paves the way for a simple approach to prove
the $\mathsf{APX}$-hardness of the Euclidean Steiner Tree problem in high
dimensions. Trevisan [Tre00] uses a simple gap-preserving reduction from the
Vertex Cover problem, and a similar reduction applies in the setting where the
candidate Steiner points are provided as input.

As motivation, we sketch a simple reduction framework for proving
$\mathsf{APX}$-hardness of the Euclidean Steiner Tree problem. We formalize
this in Appendix A. We reduce from the Vertex Cover problem on bounded degree
triangle-free graphs. Namely, there exists some $\rho>0$ such that it is
$\mathsf{NP}$-hard to decide whether a triangle-free graph $G=(V,E)$ has a
vertex cover of size $r|E|$ or all of its vertex covers are of size at least
$(1+\rho)\cdot r|E|$ (for some $r,\rho>0$). Now, we embed $G$ into
$\operatorname{\mathbb{R}}^{|V|}$ by embedding each edge $\\{u,v\\}\in E$ as
$\mathbf{e}_{u}+\mathbf{e}_{v}$, where $\mathbf{e}_{u}$ is the standard basis
vector with $1$ in coordinate indexed by $u$ and $0$ elsewhere. Thus, each
edge is embedded as its characteristic vector. The embedding of the set of
edges incident to a single vertex forms the regular simplex of side length
$\sqrt{2}$. The point configuration as a whole composes of the vertices of a
regular simplicial complex (where we take the union of the simplices
associated with each vertex).

Observe that a vertex cover of $G$ of size $r|E|$ induces a partition of the
embedded simplicial complex into $r|E|$ regular simplices. Moreover, any
partition of the simplicial complex into regular simplices induces a vertex
cover in $G$ of the same size (using that $G$ is triangle-free). Then, it
would suffice to show that there exists $s,\beta>0$ such that the following
holds:

  1. 1.

Any embedded point configuration forming the vertices of a regular simplicial
complex partitionable into $r|E|$ regular simplices has a Steiner tree of cost
at most $s|E|$.

  2. 2.

Any embedded point configuration forming the vertices of a regular simpicial
complex such that the minimum size of a partition into regular simplices is at
least $(1+\rho)r|E|$ has minimum Steiner tree of cost at least
$(1+\beta)s|E|$.

Namely, this would imply that the Euclidean Steiner Tree problem is
$\mathsf{NP}$-hard to approximate within a factor less than $(1+\beta)$. Why
might we expect this reduction to even be gap-preserving? On the one hand,
this reduction, interpreted instead in the $\ell_{1}$-metric _is_ used to show
$\mathsf{APX}$-hardness of the Rectilinear Steiner Tree problem (e.g., see
[Tre00]).

Additionally, heuristically, regular simplices have incredibly efficient
Steiner trees, so having a valid Steiner tree composed of few Steiner trees of
a regular simplex should result in especially low cost optimal Steiner trees.
To understand this, we consider the notion of Steiner ratios: the Steiner
ratio of a finite point configuration $P\subset\operatorname{\mathbb{R}}^{d}$
is the ratio of the cost of its optimal Steiner tree to the cost of its
minimum spanning tree. For example, the Steiner ratio of the vertices of an
equilateral triangle is $\sqrt{3}/2$—the optimal Steiner tree is formed by
connecting the three vertices to a Steiner point at the center of the
triangle. The Steiner ratio of a point configuration measures the efficiency
of its Steiner tree relative to trivially connecting the points in a minimum
spanning tree. Gilbert and Pollak famously conjectured that the vertices of an
equilateral triangle, i.e., the vertices of a $2$-dimensional regular simplex,
form the most efficient Steiner tree among all planar point configurations.

######  Conjecture 1.1 (Gilbert-Pollak Steiner Ratio Conjecture [GP68]).

The minimum Steiner ratio over planar point configurations is $\sqrt{3}/2$.

This important conjecture remains open after nearly 50 years (despite at least
one high-profile incorrect proof [IT12]). They further conjectured that the
vertices of a regular simplex have the minimum Steiner ratio in higher
dimensions. This is false: for example, many regular simplices overlapping on
a common vertex has a smaller Steiner ratio [DS96]. Nonetheless, the
constructions of all known counterexamples require increasing the number of
points in the configuration. We conjecture that this is necessary: the
vertices of a regular simplex have the minimum Steiner ratio over all point
configurations on at most that many terminals.

######  Conjecture 1.2 (Simplex is the Best).

The $d+1$ vertices of a $d$-dimensional regular simplex have the minimum
Steiner ratio over all point configurations of $d+1$ points in Euclidean
space.

While this is akin to the generalized Gilbert-Pollak conjecture in that it is
about point configurations minimizing the Steiner ratio, the key difference is
that we bound the number of terminals, not the number of dimensions. This is
much more natural from a computational perspective. The natural dimension
bound is then that any $d+1$ points can be embedded into $d$-dimensional
space. Importantly, regular simplices meet this bound.

This conjecture would have structural implications for our efforts to prove
$\mathsf{APX}$-hardness of Euclidean Steiner Tree. The following weaker
version of Conjecture 1.2 is also relevant to this reduction strategy.

######  Conjecture 1.3 (Simplex is the Best for Graph Embeddings).

Over all graphs with $m$ edges, the embedding111Here we allude to embedding
each edge by it’s characteristic vector, as detailed in the aforementioned
reduction from the Vertex Cover problem. of the star graph on $m$ edges has
the minimum cost Steiner tree.

Note that, since the graphs all have the same number of edges, their minimum
spanning tree costs are all the same. Hence, Conjecture 1.3 can also be viewed
as a conjecture about the point configuration with the minimum Steiner ratio.
In this sense, it is a restricted version of Conjecture 1.2. We have verified
the weaker Conjecture 1.3 computationally up to $m=10$ using the exact
algorithm of Smith [Smi92].

The aforementioned reduction strategy to Euclidean Steiner tree problem
appears deceptively simple to employ and either verify or reject. However,
there is a fundamental obstacle: we do not know how to construct the optimal
Steiner tree for any (non-trivial) high-dimensional Euclidean point
configuration. Perhaps the simplest possible point configuration in
$\operatorname{\mathbb{R}}^{d+1}$ is the collection of standard basis vectors.
These points are precisely the vertices of a $d$-dimensional regular simplex.
Even the optimal Steiner tree of the regular simplex is unknown, although
Gilbert and Chung [CG76] constructed candidate optimal trees in the special
case of the number of vertices being a sum of up to three powers of two. For
almost every other natural high-dimensional point configuration, we are
completely ignorant of the structure of the optimal Steiner tree.

The objective of this paper is to revitalize this important line of work in
the hope of ultimately resolving Open Question 1. To achieve this, we need to
extend our understanding of high-dimensional Euclidean Steiner trees beyond
the results of the previous century.

###  1.1 Organization of the paper

In Section 2, we define the terminology we will use in discussing the
Euclidean Steiner tree problem, establish notational conventions, and recall
several relevant classical structural properties of Steiner trees. In Section
3, we prove three new structural results about Euclidean Steiner trees: two of
them extend previous results of [GP68] and the third provides a simple
condition for restricting the topologies of optimal Steiner trees. In Section
4, we discuss a little-known conjecture of Smith [Smi92] about the topology of
optimal Steiner trees of the regular simplex, motivating it from a new
viewpoint and describing its interdisciplinary connections to existing work in
chemical graph theory and computational biology. In Section 5, we prove
several new structural results about the optimal Steiner trees of the regular
simplex and show how to explicitly construct Steiner trees of the conjectured
optimal topologies. In Section 6, we revisit Conjecture 1.3 from Section 1,
making partial progress toward the conjecture. Finally, in Appendix A, we
state an analytic conjecture about the the Steiner tree problem on regular
simplicial complexes, proving that it implies $\mathsf{APX}$-hardness of the
Euclidean Steiner Tree problem (Open Problem 1).

##  2 Preliminaries

In this paper, we consider the Euclidean Steiner Tree problem. The problem is
as follows. Given $P\subset\operatorname{\mathbb{R}}^{d}$ finite, find
$S\subset\operatorname{\mathbb{R}}^{d}$ such that the minimum cost spanning
tree $T$ of $P\cup S$ has the infimum cost of all trees over all choices of
$S$. The length of each edge in the tree is the Euclidean distance between its
endpoints. The elements of $P$ are terminals, the additional points in $S$ are
Steiner points, and any spanning tree of $P\cup S$ for any choice of $S$ is a
Steiner tree. An optimal Steiner tree for $P$ is a Steiner tree of minimum
cost for $P$.

For much of the paper, we will consider Steiner trees of the vertices of
regular simplices. Regular simplices are polytopes such that all vertices are
equidistant. In particular, the vertices of a $(d-1)$-dimensional regular
simplex can be embedded in $d$ dimensions as the set of $d$ standard basis
vectors in $\operatorname{\mathbb{R}}^{d}$. For $1\leq i\leq d$, we denote
these vectors by $\mathbf{e_{i}}$. For clarity with the number of terminals,
we use regular $d$-simplex to refer to regular simplices with $d$ vertices.
For simplicity, when we consider the Steiner trees of the regular $d$-simplex,
we mean the vertices of the regular simplex expressed as standard basis
vectors (unless otherwise specified).

We now recall several useful facts about optimal Steiner trees from [GP68].
Although it is always possible to trivially add Steiner points without
increasing the length of a Steiner tree (by subdividing an edge), we assume
that optimal Steiner trees do not contain such Steiner points.

######  Theorem 2.1 ([GP68, §3.2]).

Let $\mathbf{x}$ be a vertex in an optimal Steiner tree. Suppose there are two
edges incident to $\mathbf{x}$. Then the angle included by these edges is at
least $120\degree$.

######  Corollary 2.2 ([GP68, §3.3]).

In an optimal Steiner tree, there are exactly 3 edges incident to every
Steiner point. Moreover, these lines are co-planar.

The co-planarity property was not explicitly stated in [GP68], but it is easy
to see from Theorem 2.1 and the first part of Corollary 2.2.

######  Theorem 2.3 ([GP68, §3.4]).

In an optimal Steiner tree of $n$ terminals, there are at most $n-2$ Steiner
points.

In particular, a Steiner tree with $n$ terminals and exactly $n-2$ Steiner
points is a full Steiner tree.

######  Theorem 2.4 ([GP68, §3.5]).

Let $P$ be the set of terminals of an optimal Steiner tree. Then all Steiner
points lie within the convex hull of $P$.

######  Theorem 2.5 ([GP68, §4, Uniqueness Theorem]).

For a given topology of a Steiner tree on the set of terminals in any
Euclidean space, there always exists a unique Steiner tree with this topology
of minimal length.

By topology we mean the choice of edges in the Steiner tree for a fixed number
of (unlabeled) Steiner points. For a fixed topology, the relatively minimal
tree refers to the unique tree from Theorem 2.5.

The easiest case to consider is the equilateral triangle, i.e. $2$-dimensional
regular simplex. For general triangles, it was solved as early as $17$th
century by Torricelli, Cavalieri and others and it was thoroughly analysed
from different points of view in the last century—see [CR41] or [Spa96]. The
conclusion is that the optimal Steiner tree contains a Steiner point (also
called _Fermat point_) if and only if all of the interior angles are strictly
less than $120\degree$. In [CG76], they provide a formula for computing all
distances to the Steiner point when a suitable triangle is given.

##  3 New structural properties of Steiner trees

In this section we introduce several structural results about Euclidean
Steiner trees that apply even in the high-dimensional setting. Garey, Graham,
and Johnson’s proof of $\mathsf{NP}$-hardness of Euclidean Steiner Tree proves
$\mathsf{NP}$-hardness in the plane using that edges do not cross in an
optimal tree [GGJ77]. This property is extremely powerful in analyzing planar
Steiner trees, but, while still true in higher dimensions, it is no longer
useful. We do not know how to prove even in $\mathsf{NP}$-hardness of
Euclidean Steiner Tree without proving it in the plane, partly for lack of
effective higher dimensional tools. The purpose of this section is to begin to
ameliorate this deficiency.

###  3.1 Edge lengths in optimal Steiner trees

In [GP68, §8.4], the authors presents a bound on the length of edges between
Steiner points in any optimal Steiner tree relative to the nearby edges in the
tree. The argument only applies to Steiner trees on the plane (e.g., see
[Len12, §9]). In this section we use the local planarity of optimal Steiner
trees to prove a similar result which holds in any Euclidean space.

######  Theorem 3.1.

Let $\mathbf{s_{1}}$ and $\mathbf{s_{2}}$ be two Steiner points connected by
an edge in an optimal Steiner tree $T$ in the Euclidean space of dimension
$d\geq 3$. Let $N(\mathbf{x})$ denote the neighbourhood of a vertex
$\mathbf{x}\in T$ and
$L_{0}=\min\limits_{\mathbf{s}\,\in\\{\mathbf{s_{1}},\mathbf{s_{2}}\\}}\min\limits_{\mathbf{v}\,\in
N(\mathbf{s})\setminus\\{\mathbf{s_{1}},\mathbf{s_{2}}\\}}||\mathbf{s}-\mathbf{v}||$.
Then
$||\mathbf{s_{1}}-\mathbf{s_{2}}||\geq\left(\frac{\sqrt{6}}{2}-1\right)L_{0}$.

###### Proof.

The proof is similar to the proof in [GP68, §8.4]. Without loss of generality,
assume there is a point $\mathbf{x_{1}}$ in $T$ adjacent to $\mathbf{s_{1}}$
and at distance $L_{0}$ and let $\mathbf{y_{1}}$ be a point at distance
$L_{0}$ from $\mathbf{s_{1}}$ in the line incident to $\mathbf{s_{1}}$ not
containing $\mathbf{s_{2}}$ or $\mathbf{x_{1}}$. Similarly, let
$\mathbf{x_{2}},\mathbf{y_{2}}$ be the two points at distance $L_{0}$ from
$\mathbf{s_{2}}$ on the lines of $T$ incident to $\mathbf{s_{2}}$ but not
containing $\mathbf{s_{1}}$. See Figure 1.

$\displaystyle\alpha$$\displaystyle\Pi_{1}$$\displaystyle\Pi_{2}$$\displaystyle\mathbf{s_{1}}$$\displaystyle\mathbf{s_{2}}$$\displaystyle\mathbf{x_{1}}$$\displaystyle\mathbf{x_{2}}$$\displaystyle\mathbf{y_{1}}$$\displaystyle\mathbf{y_{2}}$$\displaystyle\mathbf{o}$$\displaystyle\mathbf{c}$
Figure 1: $3$-dimensional space defined by the intersecting planes with key
points labeled.

From Corollary 2.2, we have that for the Euclidean space of dimension $d\geq
2$, the lines incident to a given Steiner point are co-planar. Thus, two
adjacent Steiner points define two planes that meet at a line, so we only need
to consider the 3-dimensional space defined by these two intersecting planes.
Let $\Pi_{1}$ and $\Pi_{2}$ denote such planes defined by the points
$\mathbf{x_{1}},\mathbf{y_{1}},\mathbf{s_{2}}$ and
$\mathbf{x_{2}},\mathbf{y_{2}},\mathbf{s_{1}}$, respectively. So either
$\Pi_{1}$ and $\Pi_{2}$ meets only in the line defined by $\mathbf{s_{1}}$ and
$\mathbf{s_{2}}$, or $\Pi_{1}=\Pi_{2}$. We only need to consider the former
case by [GP68, §8.4]. For this, let $\alpha$ denote the angle at which
$\Pi_{1}$ and $\Pi_{2}$ intersect ($\alpha$ is the acute angle between the
lines $\overleftrightarrow{\mathbf{x_{1}y_{1}}}$ and
$\overleftrightarrow{\mathbf{x_{2}y_{2}}}$ when both are translated to include
the origin).

Let us introduce a coordinate system with unit length $L_{0}$ and origin
$\mathbf{o}$ placed at the midpoint at of the segment $\mathbf{s_{1}s_{2}}$.
If $x=||\mathbf{x_{1}}-\mathbf{x_{2}}||$ and
$s=||\mathbf{s_{1}}-\mathbf{s_{2}}||$, then we have the following:

$\displaystyle\mathbf{o}=(0,0,0)$
$\displaystyle\mathbf{s_{1}}=\left(\frac{s}{2},0,0\right)$
$\displaystyle\mathbf{s_{2}}=\left(-\frac{s}{2},0,0\right)$
$\displaystyle\mathbf{x_{1}}=\left(\frac{1+s}{2},\frac{\sqrt{3}}{2}\cos\left(-\frac{\alpha}{2}\right),\frac{\sqrt{3}}{2}\sin\left(-\frac{\alpha}{2}\right)\right)$
$\displaystyle\mathbf{x_{2}}=\left(-\frac{1+s}{2},\frac{\sqrt{3}}{2}\cos\left(\frac{\alpha}{2}\right),\frac{\sqrt{3}}{2}\sin\left(\frac{\alpha}{2}\right)\right)$
$\displaystyle\mathbf{y_{1}}=\left(\frac{1+s}{2},\frac{-\sqrt{3}}{2}\cos\left(-\frac{\alpha}{2}\right),\frac{-\sqrt{3}}{2}\sin\left(-\frac{\alpha}{2}\right)\right)$
$\displaystyle\mathbf{y_{2}}=\left(-\frac{1+s}{2},\frac{-\sqrt{3}}{2}\cos\left(\frac{\alpha}{2}\right),\frac{-\sqrt{3}}{2}\sin\left(\frac{\alpha}{2}\right)\right)$
$\displaystyle\mathbf{c}=\left(0,\frac{\sqrt{3}}{2}\cos\left(\frac{\alpha}{2}\right),0\right)$

where $\mathbf{c}$ is the midpoint of the line segment
$\mathbf{x_{1}}\mathbf{x_{2}}$.

Now, we consider a second tree $T^{\prime}$ derived from $T$ by removing
$\mathbf{s_{1}},\mathbf{s_{2}}$ and instead adding
$\mathbf{x_{1}},\mathbf{x_{2}},\mathbf{y_{1}},$ and $\mathbf{y_{2}}$ as
Steiner points and joining $\mathbf{x_{1}},\mathbf{x_{2}}$ (respectively,
$\mathbf{y_{1}},\mathbf{y_{2}}$) to the Fermat point of triangle
$\triangle\mathbf{x_{1}}\mathbf{x_{2}}\mathbf{o}$ (respectively,
$\triangle\mathbf{y_{1}}\mathbf{y_{2}}\mathbf{o}$), respectively, and
connecting those Fermat points (via a line passing through $\mathbf{o}$). Call
these Fermat points $\mathbf{r_{1}}$ and $\mathbf{r_{2}}$, respectively. We
are interested in finding the coordinates of $\mathbf{r_{1}}$ and using the
optimality of $T$ to obtain a bound on
$\lvert\lvert\mathbf{s_{1}-s_{2}}\rvert\rvert$ (it suffices to consider
$\mathbf{r_{1}}$ by symmetry in this coordinate system).

Consider $\triangle\mathbf{c}\mathbf{x_{1}}\mathbf{r_{1}}$. By symmetry of
$\mathbf{x_{1}}$ and $\mathbf{x_{2}}$ about the line $\mathbf{o}\mathbf{c}$
and the definition of a Fermat point,
$\triangle\mathbf{c}\mathbf{x_{1}}\mathbf{r_{1}}$ is a 30-60-90 triangle.
Then, letting $x=\sqrt{(1+s)^{2}+3\sin^{2}(\frac{\alpha}{2})}$, we have that
$||\mathbf{c}-\mathbf{r_{1}}||=\frac{x}{2\sqrt{3}}$,
$\lvert\lvert\mathbf{c}-\mathbf{x_{1}}\rvert\rvert=x/2$, and
$\lvert\lvert\mathbf{x_{1}}-\mathbf{r_{1}}\rvert\rvert=x/\sqrt{3}$. Then, the
difference in the length of trees $T^{\prime}$ and $T$ is

$\displaystyle\underbrace{4||\mathbf{x_{1}}-\mathbf{r_{1}}||+2(||\mathbf{o}-\mathbf{c}||-||\mathbf{c}-\mathbf{r_{1}}||)}_{\text{from
}T}-\underbrace{(s+4)}_{\text{from
}T^{\prime}}=\sqrt{3}\left(x+\cos\left(\frac{\alpha}{2}\right)\right)-(s+4)\leq
0,$

with the $\leq 0$ inequality coming from optimality of $T$. Solving for $s$,
we get the inequality

$s\geq\sqrt{3}\cos\left(\frac{\alpha}{2}\right)-1.$

This is minimized for $\alpha=\frac{\pi}{2}$, where we get the inequality

$||\mathbf{s_{1}}-\mathbf{s_{2}}||\geq\left(\frac{\sqrt{6}}{2}-1\right)L_{0}.\qed$

###  3.2 Bounds on the coordinates of Steiner points

We prove that optimal Steiner trees in Euclidean spaces are not only contained
in the convex hull of the input terminals, but each of their coordinates are
also strictly contained in the interval formed by the maximum and minimum
value of the terminals in that coordinate. This is formalized in the next
lemma.

######  Lemma 3.2.

Let $P\subseteq\operatorname{\mathbb{R}}^{d}$ be a finite point-set such that
for all $1\leq i\leq d$, there are $\mathbf{p},\mathbf{q}\in P$ with
$p_{i}\neq q_{i}$. Let $\mathbf{s}=(s_{1},\ldots,s_{d})$ be a Steiner point in
an optimal Steiner tree of $P$. Then, for all $1\leq i\leq d$ it holds that

$\min_{\mathbf{p}\in P}p_{i}<s_{i}<\max_{\mathbf{p}\in P}p_{i}.$

###### Proof.

Assume not. Without loss of generality, we may assume that the statement does
not hold for $i=1$ and the bounds on the coordinate are $\min_{\mathbf{p}\in
P}p_{1}=0$ and $\max_{\mathbf{p}\in P}p_{1}=1$. We prove the lower bound and
the upper bound follows analogously.

Let $T$ be an optimal Steiner tree for $P$. Suppose some Steiner point has
first coordinate $0$. Observe that some neighbor of the Steiner point must
also have first coordinate $0$ or else increasing the first coordinate of the
Steiner point by an infinitesimal amount decreases the cost of the tree.

Now, since some terminal has nonzero first coordinate, there exists some
Steiner point $\mathbf{s}$ with first coordinate $0$ neighboring a point
$\mathbf{x}$ with positive first coordinate. This uses the fact that $T$ is
contained in the convex hull of $P$ by Theorem 2.4. By the above, $\mathbf{s}$
also has a neighbor $\mathbf{y}$ with first coordinate $0$. Now recall Theorem
2.1 and Corollary 2.2: there are exactly three coplanar lines incident to
$\mathbf{s}$. Any plane is defined by precisely two orthogonal lines. Using
$\overleftrightarrow{\mathbf{s}\mathbf{y}}$ as one of the two lines defining
the plane, the other line must have non-fixed first coordinate. But we claim
that the 120 degree angle property and coplanarity imply then that the 3rd
neighbor of $\mathbf{s}$, $\mathbf{z}$, has negative first coordinate. To see
this, note that $\overleftrightarrow{\mathbf{s}\mathbf{y}}$ cuts the plane
containing the lines incident to $\mathbf{s}$ into two parts. One side
strictly contains $\mathbf{x}$ and the other strictly contains $\mathbf{z}$.
Since the other line defining the plane has non-fixed first coordinate, this
yields the claim.

However, we know from Theorem 2.4 that optimal Euclidean Steiner trees are
contained in the convex hull of the terminal set, so this contradicts the
optimality of $T$. ∎

In fact, we can apply this lemma to prove that all Steiner points must be
strictly contained in the convex hull of the terminal configuration. Note
that, as usual, this result assumes that our optimal Steiner trees do not
contain trivial Steiner points (that is, Steiner points subdividing a line).

######  Corollary 3.3.

For every finite $P\subseteq\operatorname{\mathbb{R}}^{d}$, in any optimal
Steiner tree $T$ of $P$, all Steiner points in $T$ are strictly contained in
the convex hull of $P$.

###### Proof.

Suppose not. Suppose without loss of generality that the point configuration
$P$ cannot be embedded in fewer than $d$ dimensions. Then, the convex hull of
$P$ is the intersection of $(d-1)$-dimensional hyperplanes (and the Steiner
tree $T$ is contained in the intersection of half-spaces). For each hyperplane
composing part of the boundary of the convex hull, there is some terminal not
contained in that hyperplane (or else the point configuration is embeddable in
$\operatorname{\mathbb{R}}^{d-1}$). Now, by rotating and translating the point
configuration, we may assume that that hyperplane is a coordinate hyperplane
corresponding to the first coordinate and that the interior of the convex hull
is contained in the halfspace given by
$\\{\mathbf{x}\in\operatorname{\mathbb{R}}^{d}\,:\,x_{1}\geq 0\\}$. Namely,
$0$ is a lower bound on the first coordinate of each Steiner point and the
upper bound is strictly greater than $0$ (since some terminal is not contained
in the hyperplane). Then, by Lemma 3.2, no Steiner point can lie on this
coordinate hyperplane and, hence, no Steiner point could lie on the hyperplane
before translation and rotation either.

The same procedure applies to all hyperplanes making up the convex hull of $P$
and hence the result follows. ∎

###  3.3 Degree constraints on terminals

We give a coordinate-based sufficient condition for a terminal being a leaf
node in an optimal Steiner tree.

######  Lemma 3.4.

Let $P\subseteq\operatorname{\mathbb{R}}^{d}$. Suppose there is some point
$\mathbf{p}=(p_{1},\ldots,p_{d})\in P$ such that for each $i\in[d]$ we have
$p_{i}=\max\\{q_{i}\,:\,\mathbf{q}\in P\\}$ or
$p_{i}=\min\\{q_{i}\,:\,\mathbf{q}\in P\\}$. Then, $\mathbf{p}$ is a leaf node
in every optimal Steiner tree $T$ of $P$.

###### Proof.

Let $T$ be a relatively minimal Steiner tree of $P$. Suppose that $\mathbf{p}$
has two lines incident to it with direction vectors $\vec{u}$ and $\vec{v}$
from $\mathbf{p}$ to the other endpoint of the edges, respectively. From
Theorem 2.4, it follows that the other endpoints must be contained in the
convex hull of $P$ (whether the other endpoint be another terminal or a
Steiner point). Therefore, in each coordinate $\vec{u}$ and $\vec{v}$ are
either both non-negative or non-positive, depending on whether $\mathbf{p}$ is
maximal or minimal in that coordinate.

Every pair of edges in $T$ sharing a node intersect at an angle of at least
$120\degree$. But, $\vec{u}\cdot\vec{v}\geq 0$ and thus they form an angle of
at most $90\degree$, contradicting the optimality of $T$, as desired. ∎

##  4 The topology of Steiner trees of the regular simplex

In this section, we consider a conjecture of Smith about the topology of the
optimal Steiner tree of the regular simplex (Conjecture 2 of [Smi92]). This
conjecture extends the conjecture of [CG76] to regular simplices of all sizes.
Smith verified the conjecture up to the regular $11$-simplex (by running
Smith’s algorithm, we confirm that it holds for the regular $12$-simplex as
well). We provide new intuition for the conjecture and observe that trees with
the conjectured topology have important extremal combinatorial properties with
ties to chemical graph theory and the study of phylogenetic trees in
computational biology.

###  4.1 The conjectured topology

From Lemma 3.4, we know that in any optimal Steiner tree of (the vertices of)
a regular simplex, the leaf nodes are exactly the terminal nodes. Hence, there
are exactly $n-2$ Steiner points (since each Steiner point is of degree
precisely $3$).

Let $\mathbf{e_{i}}$ and $\mathbf{e_{j}}$ be a pair of terminals with a
topology-preserving coordinate permutation $\sigma:[d]\to[d]$ between them in
some optimal Steiner tree of the regular simplex, $T$. Consider rooting $T$ at
$\mathbf{e_{i}}$. Then, we apply $\sigma$ to each level of $T$ rooted at
$\mathbf{e_{i}}$ to get $T$ rooted at $\mathbf{e_{i}}$. Such topology-
preserving coordinate permutations are hence very restrictive and lead to
extensive symmetries in the Steiner trees.

When does a topology-preserving coordinate permutation exist? Suppose that
there exists an induced full binary subtree rooted at some Steiner point, with
all its leaf nodes terminals. Then, the two subtrees induced by the children
of the root can be interchanged by a permutation swapping the coordinates
corresponding to the terminals in each subtree. Indeed, this observation may
be repeated to yield a topology preserving coordinate permutation between any
pair of terminals in the full subtree. We revisit this idea more rigorously in
Section 5.

When $d=2^{k}$, it is even possible to have topology-preserving coordinate
permutation between every pair of terminals. One such topology permitting this
is two full binary trees with $2^{k-1}$ terminals leaves each with their
Steiner point root nodes connected by an edge (see Figure 2).

Figure 2: Two full binary trees on 16 terminals connected together.

Given the rigid structure induced by topology-preserving coordinate
permutations, it feels plausible that trees exhibiting large full binary
subtree structures are extremal. The topologies of the optimal Steiner trees
(derived computationally via Smith’s algorithm) are shown in Figure 3.

Figure 3: The optimal topology of the Euclidean Steiner tree of the regular
simplex with up to $12$ vertices, terminals marked red.

These topologies interpolate between the pair of full binary trees topologies
for number of terminals a power of $2$. We make this notion rigorous. We
define a good binary tree of height $k$ recursively. For height $0$, it is a
single node. For height $k>0$, at most one subtree of the children of the root
is a good binary tree of height $k-1$ and the remaining subtrees are full
binary trees of height $k-1$ or $k-2$. Observe that in any good binary tree of
height $k$ the shortest distance from a root to a leaf node must be at least
$k-1$ (this follows by a simple inductive argument). Hence, a good binary tree
of height $k$ contains strictly more than $2^{k-1}$ leaf nodes (and at most
$2^{k}$ leaf nodes).

######  Claim 4.1.

For $k\geq 1$ and $2^{k}<d\leq 2^{k+1}$ leaf nodes, there is a unique good
tree of height $k+1$ (up to isomorphism) with that number of leaf nodes.

###### Proof.

We prove this by induction. This is clear for $d=2$ leaves: the tree must be
height $1$ and hence must be a full binary tree of height $1$.

Now, assume this holds for all $d<r$ and assume $2^{k}<r\leq 2^{k+1}$. Then,
if $r\leq 2^{k}+2^{k-1}$, by definition of a good binary tree of height $k+1$
and the fact that any good tree of height $k$ contains strictly more than
$2^{k-1}$ leaf nodes, one of the subtrees of the children of the root must be
a full binary tree of height $k-1$. Then the other subtree must be a good
subtree of height $k-1$ on $r-2^{k-1}$ leaves, which, by induction, is unique
up to isomorphism.

If $r>2^{k}+2^{k-1}$, since a good tree of height $k$ contains at most $2^{k}$
leaf nodes, one of the subtrees of the children of the root must be a full
binary tree of height $k$. Then, the other subtree must be a good subtree of
height $k-1$ on $r-2^{k}$ leaves, yielding the desired via the inductive
hypothesis. ∎

Finally, we can state the conjecture, a reformulated version of a conjecture
of Smith [Smi92].

######  Conjecture 4.1 (Optimal Topology of Steiner Trees of the Regular
Simplex, Conjecture 2 of [Smi92]).

Let $2\leq 2^{k}<d\leq 2^{k+1}$. The topology of the optimal Steiner tree of a
regular $d$-simplex is formed by taking the good tree of height $k+1$ on $d$
leaf nodes, removing the root node, and reconnecting the tree via an edge
between the former children of the root.

In the next section we provide additional motivation for this topology,
remarking that these trees are extremal with respect to a well-studied index
of acyclic graphs from chemical graph theory.

###  4.2 Indices from chemical graph theory

Throughout this subsection, we will consider trees of the form of full Steiner
trees: that is, trees with all non-leaf nodes of degree exactly three. Our
connection to computational biology is simple: phylogenetic trees are
precisely trees with this structure. We begin by defining several notions from
chemical graph theory. The Wiener index [Wie47] of a tree is the sum of
pairwise hop-distances between nodes in the tree. I.e., for a tree $T$,

$W(T)=\sum_{u,v\in V(T)}d_{T}(u,v).$

Since its introduction in 1947, this has been one of the most widely used
metrics in the study of quantitative structure-activity relationships in
chemistry. See [DEG01] for a thorough survey.

A related, more recently introduced index is the terminal Wiener index [GFP09]
of a tree, the Wiener index restricted only to pairs of leaf nodes. This index
has garnered significant attention since its introduction [DZ12, CZ13, HW13,
ZME14, ZEME16, RBK21, RBK21, NR22a, NR22b, Sul22]. Formally, let $T$ be a tree
and $H$ an induced subgraph of $T$. Then, let $\ell(H)$ be the set of leaf
nodes from $T$ contained in $H$. For any edge $(u,v)\in E(T)$, let
$(C_{u},C_{v})$ be the cut induced by the edge. We have that

$\Gamma(T)=\sum_{u,v\in\ell(T)}d_{T}(u,v)=\sum_{(u,v)\in
E(T)}|\ell(C_{u})||\ell(C_{v})|.$

This brings us to our main connection to these indices.

######  Theorem 4.2 ([HW13, SWW11]).

The trees of the form described in Conjecture 4.1 are the unique full Steiner
trees minimizing the terminal Wiener index.

Indeed, [HW13] reveals several other interesting properties of this extremal
topology.

######  Definition 4.1 (Semi-regularity).

Given a full Steiner tree $T$ and some pair $u,v$ of Steiner points, let
$T_{u}^{1}$ and $T_{u}^{2}$ denote the subtrees rooted at the children of $u$
upon removing the path $u\leadsto v$. Similarly define $T_{v}^{1}$ and
$T_{v}^{2}$. For $H$ an induced subtree of $T$, let $P(H)$ denote set of
terminals in $H$. The pair $(u,v)$ is semi-regular if

$\min(|P(T_{v}^{1})|,|P(T_{v}^{2})|)\geq\max(|P(T_{u}^{1})|,|P(T_{u}^{2})|)$

or

$\min(|P(T_{u}^{1})|,|P(T_{u}^{2})|)\geq\max(|P(T_{v}^{1})|,|P(T_{v}^{2})|).$

The tree $T$ is semi-regular if every pair of Steiner points is semi-regular.

If a pair were not semi-regular, then swapping a larger and a smaller subtree
would result in a more balanced tree. Intuitively, this should not occur in
optimal Steiner trees of the regular simplex due to its myriad symmetries.
Indeed, we have the following.

######  Theorem 4.3 ([HW13]).

The unique semi-regular full Steiner trees are exactly the trees of the form
described in Conjecture 4.1.

##  5 Steiner trees of the regular simplex

In this section we explicitly compute Steiner trees of the regular simplex.
Our constructions are a stronger version of the results of [CG76]. In the
first subsection, we show several useful properties about Steiner trees of the
regular simplex. In the second subsection, we describe our candidate
construction for optimal Steiner trees. In the third subsection, we will apply
this construction to give explicit coordinates for the candidate-optimal
Steiner trees on $d=2^{k}$ terminals and use these explicit coordinates to
analyze the limiting Steiner ratio of the regular simplex.

###  5.1 Structural properties of Steiner trees of the regular simplex

The following definition will be useful.

######  Definition 5.1 (Extending Line).

Let $T$ be a tree in the Euclidean space. Let $\mathbf{x},\mathbf{y}\in V(T)$
be two adjacent points in $T$. The _extending line_ of the edge
$(\mathbf{x},\,\mathbf{y})$ is the line containing the segment corresponding
to the edge $(\mathbf{x},\,\mathbf{y})$.

Applying Theorem 2.5 for Steiner trees of the regular simplex, we give the
following lemma.

######  Lemma 5.1.

Let $T$ be a relatively minimal Steiner tree of the regular $n$-simplex. Let
$T^{\prime}$ be an induced full binary subtree of $T$, with all leaf nodes of
$T^{\prime}$ terminals. Let $P(T^{\prime})$ be the set of terminals in
$T^{\prime}$ and $\mathbf{r_{T^{\prime}}}$ the root Steiner point of
$T^{\prime}$. Let $e_{T^{\prime}}$ be the edge incident to
$\mathbf{r_{T^{\prime}}}$ that does not lie in $T^{\prime}$. Then the
following hold:

  1. 1.

For all Steiner points $\mathbf{s}$ in $(T\setminus
T^{\prime})\cup\\{\mathbf{r_{T^{\prime}}}\\}$, for all coordinates $i,j$ such
that terminals $\mathbf{e_{i}},\mathbf{e_{j}}\in P(T^{\prime})$, it holds that
$s_{i}=s_{j}$.

  2. 2.

Let $\ell_{T^{\prime}}$ be the line extending the edge $e_{T^{\prime}}$. Then
$\ell_{T^{\prime}}$ passes through the centroid of the terminals in
$P(T^{\prime})$.

The proof of this lemma uses permutations of the labels of the terminals, as
informally sketched in Section 4.1. We formalize that notion here using
labeled full binary trees.

######  Definition 5.2 (Labelling Full Binary Trees).

Let $T$ be a full binary tree (with a fixed choice of left and right children
for every non-leaf node). Then, labelling the tree with respect to (a binary
string) $g$ is defined as follows.

  * •

The root of $T$ is labeled as $g$.

  * •

Then, while there exists some labeled node $v$ with unlabeled children, label
the left child of $v$ by appending $0$ to the label of $v$ and label the right
child of $v$ by appending $1$ to the the label of $v$. E.g., if $v$ had binary
string $b$ as its label, its children will be labeled $b0$ and $b1$.

We denote $T_{g}$ as the result of labelling $T$ with respect to $g$.

Let $T$ be a Steiner tree of the regular simplex and let $T_{g}^{\prime}$ be a
labeled induced full binary subtree with terminal leaf nodes (with an
arbitrary choice of left and right children). Let $\mathbf{s}$ be a Steiner
point in $T_{g}^{\prime}$. Consider the subtree of $T_{g}^{\prime}$ rooted at
$\mathbf{s}$. Each node in the left subtree has its label prepended by
$b_{\mathbf{s}}0$ and each node in the right subtree has its label prepended
by $b_{\mathbf{s}}1$. Swapping the left and right children of $\mathbf{s}$
amounts to making the labels of the nodes in the left subtree prepended by
$b_{\mathbf{s}}1$ and the labels of the nodes in the right subtree instead
prepended by $b_{\mathbf{s}}0$ (via Definition 5.2).

######  Observation 5.2.

Let $T$ be a Steiner tree of the regular simplex and let $T_{g}^{\prime}$ be a
labeled induced full binary subtree with terminal leaf nodes. Let $\mathbf{s}$
be a Steiner point in $T_{g}^{\prime}$. Swapping the left and right children
of $\mathbf{s}$ corresponds to a topology-preserving coordinate permutation in
$T$.

###### Proof.

The coordinate permutation is precisely the composition of the involutions of
each pair of terminals whose labels are $b_{\mathbf{s}}0c$ and
$b_{\mathbf{s}}1c$. Namely, their labels differ exactly in the bit after the
label of $\mathbf{s}$.

Since each pair of swapped terminals is between terminals in the corresponding
position in the other subtree of $\mathbf{s}$ (and the subtrees have the same
overall structure since $T_{g}^{\prime}$ is an induced full binary subtree
with terminal leaf nodes), this permutation of the terminals preserves the
topology of $T$. ∎

Finally, we can return to Lemma 5.1.

###### Proof.

First, label $T^{\prime}$ with respect to the empty string $\varepsilon$ to
obtain $T^{\prime}_{\varepsilon}$. We claim that for every pair of terminals
$\mathbf{e_{i}},\mathbf{e_{j}}\in T^{\prime}$ there is a topology-preserving
coordinate permutation of $T$ that swaps $\mathbf{e_{i}}$ and
$\mathbf{e_{j}}$. Namely, it is the composition of topology-preserving
coordinate permutations induced by swapping the left and right children of
Steiner points in $T^{\prime}_{\varepsilon}$ (via Observation 5.2). Index the
bits of the labels of the nodes from last added to first (via Definition 5.2).
Suppose that the labels of $\mathbf{e_{i}}$ and $\mathbf{e_{j}}$ differ on
bits $a_{1},a_{2},\ldots,a_{r}$. Swapping the left and right children of each
of the $a_{1}$th, $a_{2}$th, …, $a_{r}$th ancestors of $\mathbf{e_{i}}$ and
$\mathbf{e_{j}}$ (where the first ancestor is the parent of $\mathbf{e_{i}}$,
the second ancestor is the grandparent, etc., and we only swap the children of
a node at most once) swaps the labels of $\mathbf{e_{i}}$ and $\mathbf{e_{j}}$
(for example see Figure 4). The composition of the corresponding topology-
preserving coordinate permutations is a topology-preserving coordinate
permutation swapping $\mathbf{e_{i}}$ and $\mathbf{e_{j}}$. But, by Theorem
2.5, $T$ must be fixed (up to isomorphism) under this map.

$0$$1$$00$$10$$01$$11$$000$$001$$010$$011$$100$$101$$110$$111$$1$$0$$00$$10$$01$$11$$000$$101$$110$$011$$100$$001$$010$$111$$1$$0$$01$$11$$00$$10$$010$$111$$100$$001$$110$$011$$000$$101$
Figure 4: A sequence of topology-preserving coordinate permutations swapping
the blue and the orange label. The purple vertices indicates the Steiner
points whose children are to be swapped in the next step.

The topology of $(T\setminus T^{\prime})\cup\\{\mathbf{r_{T^{\prime}}}\\}$ is
fixed under this topology-preserving coordinate permutation and each terminal
is fixed. Hence, the Steiner points in this part of the tree must be fixed (or
else we would violate Theorem 2.5). Hence, for each such Steiner point
$\mathbf{s}$, we must have $s_{i}=s_{j}$. This holds for all
$\mathbf{e_{i}},\mathbf{e_{j}}\in T^{\prime}$, yielding the first part of the
result.

Observe that $e_{T^{\prime}}$ is an edge between two Steiner points such that
the first property holds. Hence, for every point on the extending line
$\ell_{T^{\prime}}$, $s_{i}=s_{j}$ for all pairs of terminals
$\mathbf{e_{i}},\mathbf{e_{j}}\in T^{\prime}$. Using this observation, we
prove the second part of the result by induction on the number of levels in
the induced full binary subtree $T^{\prime}$. When there is only one level,
$T^{\prime}$ is a Steiner point $\mathbf{r_{T^{\prime}}}$ connected to two
terminals, $\mathbf{e_{i}}$ and $\mathbf{e_{j}}$. By Corollary 2.2, the edge
$e_{T^{\prime}}$ and the edges from $\mathbf{r_{T^{\prime}}}$ to
$\mathbf{e_{i}}$ and $\mathbf{e_{j}}$ are all coplanar. Consider
$\triangle\mathbf{r_{T^{\prime}}}\mathbf{e_{i}}\mathbf{e_{j}}$. By
coplanarity, $\ell_{T^{\prime}}$ lies in the same plane as this triangle. By
the observation about the extending line above, $\ell_{T^{\prime}}$ must be
coincident with the perpendicular bisector of the line segment joining
$\mathbf{e_{i}}$ and $\mathbf{e_{j}}$. Hence, $\ell_{T^{\prime}}$ passes
through the midpoint of this segment, the centroid of $\mathbf{e_{i}}$ and
$\mathbf{e_{j}}$.

The inductive step is similar: suppose the result holds for full binary
subtrees with at least $r$ levels. Then, consider the edges other than
$e_{T^{\prime}}$ incident to the root $\mathbf{r_{T^{\prime}}}$ of
$T^{\prime}$. Namely, with $T_{L}$ the left subtree of
$\mathbf{r_{T^{\prime}}}$ and $T_{R}$ similarly defined, these edges are
precisely $e_{T_{L}}$ and $e_{T_{R}}$. By the inductive hypothesis,
$\ell_{T_{L}}$ and $\ell_{T_{R}}$ pass through $\mathbf{c_{T_{R}}}$ and
$\mathbf{c_{T_{L}}}$, the centroids of $P(T_{R})$ and $P(T_{L})$,
respectively. Now, consider
$\triangle\mathbf{r_{T^{\prime}}}\mathbf{c_{T_{R}}}\mathbf{c_{T_{L}}}$. Again,
coplanarity and the observation about the extending line imply that
$\ell_{T^{\prime}}$ is coincident to the perpindicular bisector of the line
segment joining $\mathbf{c_{T_{R}}}$ and $\mathbf{c_{T_{L}}}$. Hence, it
passes through the midpoint of $\mathbf{c_{T_{R}}}$ and $\mathbf{c_{T_{L}}}$,
the centroid of $P(T^{\prime})$, yielding the desired result. ∎

We need to say that the terminals of an optimal Steiner tree for the
$n$-simplex have to be its leaf nodes. Luckily, this follows from a previous
structural lemma.

######  Corollary 5.3.

In any relatively minimal Steiner tree of the regular $n$-simplex, all
terminals are leaf nodes.

###### Proof.

Consider the regular $n$-simplex with terminals
$\mathbf{p_{i}}=\mathbf{e_{i}}$. The result then follows from Lemma 3.4. ∎

Next, we will restrict the intersection of the extending lines of edges
incident to Steiner points.

######  Lemma 5.4.

Let
$F_{i}=\\{\mathbf{x}\in\mathbb{R}^{n}:x_{i}=0,\lvert\lvert\mathbf{x}\rvert\rvert_{1}=1\\}$
be a face of the regular $n$-simplex. Let $T$ be a Steiner tree of the regular
$n$-simplex. Let $\mathbf{s}\in V(T)$ be a Steiner point. Let
$\mathbf{a},\mathbf{b},$ and $\mathbf{c}$ be the points of intersection
between the convex hull and the rays extending the edges incident to
$\mathbf{s}$, with the endpoint of the first ray the neighbor of $\mathbf{s}$
and the endpoints of the other rays $\mathbf{s}$. If $\mathbf{a}\not\in
F_{i}$, then at least one of $\mathbf{b}$ and $\mathbf{c}$ are also not
contained in $F_{i}$.

###### Proof.

For the sake of contradiction, suppose that both $\mathbf{b},\mathbf{c}\in
F_{i}$. Let $\mathbf{a}\in F_{j}$ for $i\neq j$. By Corollary 2.2
$\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{s}$ are coplanar. Hence, the lines
$\overleftrightarrow{\mathbf{b}\mathbf{c}}$ and
$\overleftrightarrow{\mathbf{s}\mathbf{a}}$ intersect at some point
$\mathbf{x}$. Note that $\mathbf{s}\mathbf{a}$ includes an angle of exactly
$60\degree$ with each of $\mathbf{s}\mathbf{b}$ and $\mathbf{s}\mathbf{c}$ (by
Theorem 2.1). So, in particular, coplanarity implies that
$\mathbf{b}\mathbf{c}$ intersects the ray
$\overrightarrow{\mathbf{s}\mathbf{a}}$. Finally, all the points on
$\mathbf{b}\mathbf{c}$ are contained in the convex hull of the simplex, so
$\mathbf{x}$ must be in the convex hull as well. By Theorem 2.4, $\mathbf{s}$
is in the convex hull of the simplex, so all the points in the convex hull on
the ray $\overrightarrow{\mathbf{s}\mathbf{a}}$ are contained in the segment
$\mathbf{s}\mathbf{a}$. Namely, $\mathbf{x}$ must be contained in the segments
$\mathbf{b}\mathbf{c}$ and $\mathbf{s}\mathbf{a}$ (see Figure 5).

Now, since $b_{i}=c_{i}=0$, we have $x_{i}=0$. But, $s_{i},a_{i}>0$ (using
Lemma 3.2), so we also have $x_{i}>0$, yielding the desired contradiction. ∎

$F_{i}$$F_{j}$$\mathbf{s}$$\mathbf{x}$$\mathbf{a}$$\mathbf{c}$$\mathbf{b}$
Figure 5: The intersection of the line segments $\mathbf{bc}$ and
$\mathbf{sa}$ is the point $\mathbf{x}$.

######  Corollary 5.5.

Let $T$ be an optimal Steiner tree of the regular simplex. Let $\mathbf{s}$ be
a Steiner point adjacent to a terminal $\mathbf{e_{i}}$ in $T$. Then, the rays
extending the other edges of $\mathbf{s}$, both with endpoints $\mathbf{s}$,
intersect the convex hull of the regular simplex at the face
$F_{i}=\\{\mathbf{x}\in\mathbb{R}^{n}:x_{i}=0,\lvert\lvert\mathbf{x}\rvert\rvert_{1}=1\\}$.

###### Proof.

It holds that in every full, optimal Steiner tree, there are exactly $n-2$
Steiner points. It will suffice to use Lemma 5.4 until we run out of possible
Steiner points. Let $\mathbf{a}$ be a point of intersection between a ray
extending an edge of $\mathbf{s}$ (not to $\mathbf{e_{i}}$) with endpoint
$\mathbf{s}$. For the sake of contradiction, assume that $\mathbf{a}\not\in
F_{i}$.

Let $\mathbf{s_{0}}=\mathbf{s}$ and let us proceed by induction on $k$. Let
$e_{k}=(\mathbf{s_{k-1}},\,\mathbf{s_{k}})$ be the edge such that the ray with
endpoint $\mathbf{s_{k-1}}$ extending the edge $e_{k}$ does not intersect
$F_{i}$ (e.g., $e_{1}$ is the edge whose extending ray has endpoint
$\mathbf{a}$). If $\mathbf{s_{k}}$ is a terminal, since the $i$th coordinate
is greater than $0$, $\mathbf{s_{i}}=\mathbf{e_{i}}$ and we found a cycle in
our tree $T$, a contradiction. Otherwise, we iterate using Lemma 5.4 over up
to all $n-2$ Steiner points in a path. Eventually then $\mathbf{s_{i}}$ must
be a terminal since there are finitely many Steiner points, yielding a
contradiction. ∎

Finally, we are prepared to prove the following theorem.

######  Theorem 5.6.

Let $n\in\mathbb{N}$ and let $T$ be an optimal Steiner tree for the regular
$n$-simplex. Consider a terminal $\mathbf{p}\in T$ and let $\mathbf{s}$ be the
Steiner point adjacent to $\mathbf{p}$. Then,
$\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert>\frac{1}{\sqrt{3}}$.

###### Proof.

Without loss of generality, suppose $\mathbf{p}=\mathbf{e_{1}}$. By Corollary
3.3, we may assume that $\mathbf{s}$ is strictly contained in the convex hull
of the $n$-simplex. Now consider the two other edges incident to $\mathbf{s}$.
The rays with endpoint at $\mathbf{s}$ extending these edges must intersect
the convex hull of the $n$-simplex in some points $\mathbf{a}$, $\mathbf{b}$.
Let
$F_{1}=\\{\mathbf{x}\in\mathbb{R}^{n}:x_{1}=0,\lvert\lvert\mathbf{x}\rvert\rvert_{1}=1\\}$.

By Corollary 5.5, we know that $\mathbf{a}$, $\mathbf{b}$ lie in $F_{1}$. We
will show that
$\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert>\frac{1}{\sqrt{3}}$. Since
$\mathbf{a},\mathbf{b}\in F_{1}$, it holds that

$\displaystyle\mathbf{a}$ $\displaystyle=\left(0,a_{2},\ldots,a_{n}\right),$
$\displaystyle\mathbf{b}$ $\displaystyle=\left(0,b_{2},\ldots,b_{n}\right),$

where $\sum_{i=2}^{n}a_{i}=\sum_{i=2}^{n}b_{i}=1$.

Now consider $\triangle\mathbf{p}\mathbf{a}\mathbf{b}$. It has a unique Fermat
point and that must be $\mathbf{s}$. We will use a calculation based on [CG76]
to determine the lower bound for
$\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert$. Let
$L_{\mathbf{s}}=\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert+\lvert\lvert\mathbf{s}-\mathbf{a}\rvert\rvert+\lvert\lvert\mathbf{s}-\mathbf{b}\rvert\rvert$.
Without loss of generality, suppose that
$\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert\geq\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert$.
We will now show that
$\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\leq\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert$.
It holds that

$\displaystyle\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}$
$\displaystyle=\sum_{i=2}^{n}(a_{i}-b_{i})^{2}$
$\displaystyle=\sum_{i=2}^{n}(a_{i}^{2}-2a_{i}b_{i}+b_{i}^{2})$
$\displaystyle=\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert^{2}-1+\sum_{i=2}^{n}(a_{i}^{2}-2a_{i}b_{i})$
$\displaystyle\leq\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert^{2},$

since
$\sum_{i=2}^{n}a_{i}^{2}=\left(\sum_{i=2}^{n}a_{i}\right)^{2}-\sum_{i\neq
j}2a_{i}a_{j}=1-\sum_{i\neq j}2a_{i}a_{j}\leq 1$. The third step uses that
$\mathbf{p}=\mathbf{e_{1}}$ and $\mathbf{b}\in F_{1}$, so $\mathbf{p}$ and
$\mathbf{b}$ are orthogonal.

From the proof of the Gilbert-Pollak Steiner ratio conjecture for 3 points
(§10 of [GP68]), it is known that for
$L=\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert$
it holds that

$L\geq L_{\mathbf{s}}\geq\frac{\sqrt{3}}{2}L,$

by considering $\mathbf{p}$, $\mathbf{a}$, $\mathbf{b}$ as a set of terminals
for the Steiner Tree problem. Next, it is important to note that
$\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert>1$ and $\mathbf{b}\in F_{1}$.
Finally, we can use formula (18) of [CG76] to compute a lower bound for
$\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert$:

$\displaystyle\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert$
$\displaystyle=\frac{L_{\mathbf{s}}+\frac{\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert^{2}+\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert^{2}-2\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}}{L_{\mathbf{s}}}}{3}$
$\displaystyle\geq\frac{\frac{\sqrt{3}}{2}L^{2}+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert^{2}+\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert^{2}-2\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}}{3L}.$

Then,

$\displaystyle\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert$
$\displaystyle\geq\frac{\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}\left(\frac{\sqrt{3}}{2}-2\right)+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert^{2}\left(\frac{\sqrt{3}}{2}+1\right)+\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert^{2}+\sqrt{3}\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert}{3\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\right)}$
$\displaystyle=\frac{\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert^{2}-\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}+\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\right)\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}-1\right)+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}+1\right)\right)}{3\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\right)}$
$\displaystyle=\underbrace{\frac{\lvert\lvert\mathbf{p}-\mathbf{a}\rvert\rvert^{2}-\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert^{2}}{3\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\right)}}_{\geq
0}+\frac{1}{3}\cdot\left(\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}-1\right)+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}+1\right)\right).$

Finally, since $\frac{\sqrt{3}}{2}-1<0$ and
$\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\leq\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert$,
it holds that

$\displaystyle\lvert\lvert\mathbf{a}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}-1\right)+\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}+1\right)$
$\displaystyle\geq\lvert\lvert\mathbf{p}-\mathbf{b}\rvert\rvert\left(\frac{\sqrt{3}}{2}-1+\frac{\sqrt{3}}{2}+1\right)$
$\displaystyle>\sqrt{3}.$

Therefore, $\lvert\lvert\mathbf{s}-\mathbf{p}\rvert\rvert>\frac{1}{\sqrt{3}}$.
∎

######  Remark 5.7.

From Lemma 5.1 we already know that the lengths for a pair of terminals
adjacent to the same Steiner point are the same and can hence compute the
lengths using Theorem 2.1. In contrast, we did not previously know how to
lower bound the length of an edge between a Steiner point and a terminal when
the Steiner point is adjacent to only one terminal. Theorem 5.6 now provides
such a bound.

###  5.2 Constructing Steiner trees for the regular simplex

To describe our construction of Steiner trees of the regular simplex, we need
one more definition.

######  Definition 5.3 (The Split of a Point).

For $\mathbf{x}\in\operatorname{\mathbb{R}}^{d}$, we define the split of
$\mathbf{x}$ to be $\mathbf{x^{\prime}}\in\operatorname{\mathbb{R}}^{2d}$ such
that
$\mathbf{x^{\prime}}=\left(\frac{x_{1}}{2},\frac{x_{1}}{2},\ldots,\frac{x_{d}}{2},\frac{x_{d}}{2}\right)$.

######  Lemma 5.8.

Let $\mathbf{x},\mathbf{y},\mathbf{z}\in\mathbb{R}^{d}$ such that the angle
included by $\mathbf{x}-\mathbf{y}$ and $\mathbf{z}-\mathbf{y}$ is $\alpha$.
Let $\mathbf{x^{\prime}},\mathbf{y^{\prime}},$ and $\mathbf{z^{\prime}}$
denote the splits of $\mathbf{x},\mathbf{y},$ and $\mathbf{z}$, respectively.
Then, the angle included by $\mathbf{x^{\prime}}-\mathbf{y^{\prime}}$ and
$\mathbf{z^{\prime}}-\mathbf{y^{\prime}}$ is $\alpha$.

###### Proof.

Let $\mathbf{u}=(\mathbf{x}-\mathbf{y})$,
$\mathbf{v}=(\mathbf{z}-\mathbf{y})$,
$\mathbf{u^{\prime}}=(\mathbf{x^{\prime}}-\mathbf{y^{\prime}})$ and
$\mathbf{v^{\prime}}=(\mathbf{z^{\prime}}-\mathbf{y^{\prime}})$. Now
$\mathbf{u}\cdot\mathbf{v}$ = $2\mathbf{u^{\prime}}\cdot\mathbf{v^{\prime}}$,
$\lvert\lvert\mathbf{u}\rvert\rvert=\sqrt{2}\lvert\lvert\mathbf{u^{\prime}}\rvert\rvert$
and the same with the norms of $\mathbf{v}$ and $\mathbf{v^{\prime}}$. Now it
is easy to see
$\frac{\mathbf{u}\cdot\mathbf{v}}{\lvert\lvert\mathbf{u}\rvert\rvert\lvert\lvert\mathbf{v}\rvert\rvert}=\frac{\mathbf{u^{\prime}}\cdot\mathbf{v^{\prime}}}{\lvert\lvert\mathbf{u^{\prime}}\rvert\rvert\lvert\lvert\mathbf{v^{\prime}}\rvert\rvert}$.
∎

We will show how to leverage this idea of split to explicitly construct
candidate-optimal Steiner trees of the regular simplex from optimal Steiner
trees of smaller regular simplices (which can be computed directly). We
formalize this in the following definition.

######  Definition 5.4 (Candidate-optimal Steiner tree).

A Steiner tree $T$ of a point configuration is called a candidate-optimal
Steiner tree if each pair of edges incident to a common vertex in $T$ include
an angle of at least 120 degrees and each Steiner point is of degree exactly
$3$.

Finally, we describe how to construct a candidate-optimal, full Steiner tree
of the regular $2d$-simplex from a candidate-optimal full Steiner tree of the
regular $d$-simplex. In the below, we will use the fact that all terminals are
leaf nodes in an optimal Steiner tree if and only if it is full. This is clear
by computing the degree sum of the tree in two ways: using that Steiner points
are all degree $3$ and that a full Steiner tree on $n$ terminals is a tree on
$2n-2$ total nodes.

######  Theorem 5.9 (Doubling the Tree).

Let $d\geq 3$ and let $T$ be an optimal Steiner tree of a regular $d$-simplex.
Let $S$ be the set of Steiner points in $T$. Then by the following procedure,
we obtain a full, candidate-optimal Steiner tree $T^{\prime}$ of the regular
$2d$-simplex:

  1. 1.

For each $\mathbf{s}\in S$, denote the split of $\mathbf{s}$ by
$\mathbf{s^{\prime}}$. The set $\\{\mathbf{s^{\prime}}\,:\,\mathbf{s}\in S\\}$
is a subset of the Steiner points $S^{\prime}$ in $T^{\prime}$.

  2. 2.

For all $\mathbf{r},\mathbf{s}\in S$ such that $(\mathbf{r},\,\mathbf{s})\in
E(T)$, let $(\mathbf{r^{\prime}},\,\mathbf{s^{\prime}})\in E(T^{\prime})$.

  3. 3.

For each terminal $\mathbf{e_{i}}\in V(T)$, let $\mathbf{s_{i}}$ be the
adjacent Steiner point. Then we obtain new Steiner points $\mathbf{x_{i}}$ in
$T^{\prime}$ by finding the Fermat points of the triangles formed by
$\mathbf{e_{2i-1}},\mathbf{e_{2i}},\mathbf{s^{\prime}_{i}}$.

  4. 4.

Add edges $(\mathbf{e_{2i-1}},\,\mathbf{x_{i}})$,
$(\mathbf{e_{2i}},\,\mathbf{x_{i}})$ and
$(\mathbf{x_{i}},\,\mathbf{s^{\prime}_{i}})$ to $T^{\prime}$.

###### Proof.

Note that, assuming that the Fermat points of the triangles of the form
$\triangle\mathbf{e_{2i-1}}\mathbf{e_{2i}}\mathbf{s^{\prime}_{i}}$ exist,
$T^{\prime}$ is a full Steiner tree of the regular $2d$-simplex. The set of
Steiner points $\\{\mathbf{s^{\prime}}\,:\,\mathbf{s}\in T\\}$ are connected
via the same tree topology as the Steiner points in $T$. Then, for each
$i\in[d]$, each terminal $\mathbf{e_{2i}}$ or $\mathbf{e_{2i-1}}$ is connected
to this tree via the Steiner tree of the triangle
$\triangle\mathbf{e_{2i-1}}\mathbf{e_{2i}}\mathbf{s^{\prime}_{i}}$ (via the
additional Steiner point $\mathbf{x_{i}}$). Since one Steiner point is added
to $T^{\prime}$ for each Steiner point and terminal in $T$ and $T$ is a full
Steiner tree of the regular $d$-simplex, $T^{\prime}$ has $2d-2$ total Steiner
points and is also full (this uses Corollary 5.3 and the discussion preceding
this theorem).

We need to verify two claims. First, we need to show that the Fermat points
always exist for the third step of the construction. Secondly, we need to
prove that every included angle between two adjacent edges is $120\degree$ (so
that $T^{\prime}$ is a candidate-optimal Steiner tree). First, consider the
terminal $\mathbf{e_{i}}$ in $T$.

To prove the first claim, we distinguish between two cases. First, suppose
that $\mathbf{e_{i}}$ shares its neighboring Steiner point with another
terminal in $T$. In our coordinate system, the distance between every two
terminals is exactly $\sqrt{2}$. By Theorem 2.5, it holds

$\lvert\lvert\mathbf{e_{i}}-\mathbf{s_{i}}\rvert\rvert=\lvert\lvert\mathbf{e_{j}}-\mathbf{s_{i}}\rvert\rvert=\sqrt{\frac{2}{3}},$

applying Lemma 5.1 and Theorem 2.1.

Now, we denote the center of the segment $\mathbf{e_{2i-1}}\mathbf{e_{2i}}$ by
$\mathbf{c_{i}}$. It holds that $\mathbf{c_{i}}$ is the split of
$\mathbf{e_{i}}$. Therefore (following from the proof of Lemma 5.8),

$\lvert\lvert\mathbf{c_{i}}-\mathbf{s^{\prime}_{i}}\rvert\rvert=\frac{1}{\sqrt{2}}\lvert\lvert\mathbf{e_{i}}-\mathbf{s_{i}}\rvert\rvert=\frac{1}{\sqrt{3}}.$

To get the Fermat point of
$\triangle\mathbf{e_{2i-1}}\mathbf{e_{2i}}\mathbf{s^{\prime}_{i}}$, basic
trigonometry tells us that we need to find a point at distance
$\frac{1}{\sqrt{6}}$ from $\mathbf{c_{i}}$ in the direction of
$\mathbf{s^{\prime}_{i}}$ (see Figure 6). Since
$\lvert\lvert\mathbf{c_{i}}-\mathbf{s^{\prime}_{i}}\rvert\rvert>\frac{1}{\sqrt{6}}$,
the Fermat point $\mathbf{x_{i}}$ does exist.

$\mathbf{s}^{\prime}_{\mathbf{i}}$$\mathbf{x}_{\mathbf{i}}$$\mathbf{c}_{\mathbf{i}}$$6\mathnormal{0\degree}$$\frac{1}{\sqrt{2}}$$\Biggl{\\{}$$\mathbf{e_{2i-1}}$$\mathbf{e_{2i}}$
Figure 6: Diagram showing the existence of the Fermat point $\mathbf{x_{i}}$.
Note that
$\lvert\lvert\mathbf{c_{i}}-\mathbf{s^{\prime}_{i}}\rvert\rvert>\frac{1}{\sqrt{2}}\cot(60^{\circ})=\frac{1}{\sqrt{6}}$.

In the case that $\mathbf{e_{i}}$ does not share its neighboring Steiner point
with another terminal in $T$, $\mathbf{c_{i}}$ is still well-defined as above.
Using
$\lvert\lvert\mathbf{c_{i}}-\mathbf{s^{\prime}_{i}}\rvert\rvert=\frac{1}{\sqrt{2}}\lvert\lvert\mathbf{e_{i}}-\mathbf{s_{i}}\rvert\rvert$
and that
$\lvert\lvert\mathbf{e_{2i-1}}-\mathbf{s_{i}^{\prime}}\rvert\rvert=\lvert\lvert\mathbf{e_{2i}}-\mathbf{s_{i}^{\prime}}\rvert\rvert$
by definition of split, we need to find a point at distance
$\frac{1}{\sqrt{6}}$ from $\mathbf{c_{i}}$ in the direction of
$\mathbf{s^{\prime}_{i}}$ to find a Fermat point of
$\triangle\mathbf{e_{2i-1}}\mathbf{e_{2i}}\mathbf{s^{\prime}_{i}}$. Hence, a
Fermat point of this triangle exists if and only if
$\lvert\lvert\mathbf{e_{i}}-\mathbf{s_{i}}\rvert\rvert>1/\sqrt{3}$ and a
Fermat point then exists by Theorem 5.6.

To prove the second claim, observe that all such the angles were equal to
$120\degree$ in $T$ (by Theorem 2.1). Lemma 5.8 then implies that the angles
stay the same size in the induced subtree on Steiner points in
$\\{\mathbf{s^{\prime}}\,:\,\mathbf{s}\in T\\}$. We already established that
$\mathbf{c_{i}}$ is the split of $\mathbf{e_{i}}$, so, $\mathbf{e_{i}}$ and
$\mathbf{e_{j}}$ share an adjacent Steiner point in $T$ and $\mathbf{c_{j}}$
is the center of the segment $\mathbf{e_{2j-1}}\mathbf{e_{2j}}$, then
$|\angle\mathbf{c_{i}}\mathbf{s^{\prime}_{i}}\mathbf{c_{j}}|$ in $T^{\prime}$
is equal to $|\angle\mathbf{e_{i}}\mathbf{s_{i}}\mathbf{p_{j}}|$ in $T$ which
is $120\degree$ by Theorem 2.1. Since the points
$\mathbf{c_{i}},\mathbf{x_{i}},\mathbf{s^{\prime}_{i}}$ and
$\mathbf{c_{j}},\mathbf{x_{j}},\mathbf{s^{\prime}_{i}}$ are colinear from the
second part of Lemma 5.1 we have that

$|\angle\mathbf{x_{i}}\mathbf{s^{\prime}_{i}}\mathbf{x_{j}}|=120\degree.$

Finally, the remaining angles involve the Steiner points added which were
computed as Fermat points of triangles. By definition of Fermat points, the
edges sharing an endpoint at these Steiner points include angles of exactly
$120\degree$. ∎

######  Corollary 5.10.

Let $d\geq 3,k\geq 0$ and let $T$ be an optimal Steiner tree of a regular
$d$-simplex. Repeating the procedure in Theorem 5.9, $k$ many times, yields a
full, candidate-optimal Steiner tree $T^{\prime}$ of a regular
$2^{k}d$-simplex.

###### Proof.

Optimality of $T$ handles $k=0$ (using that the optimal Steiner tree of the
regular simplex is full, using the discussion preceding Theorem 5.9 and Lemma
3.4). Theorem 5.9 handles the case of $k=1$. Assume the result holds for up to
some $r\geq 1$ and let $T$ be the optimal tree with Steiner points $S$. We
show the result for $k=r+1$. The same proof as in Theorem 5.9 shows that
$T^{\prime}$ computed from $T$ by the procedure in Theorem 5.9 is a full
Steiner tree of the regular simplex, assuming that the relevant Fermat points
exist.

It remains to show that the Fermat points exist in each subsequent iteration
and all the angles formed by edges at a common endpoint are $120\degree$.

First, note that, since we assumed $r\geq 1$, by the procedure in Theorem 5.9,
each terminal in $T$ shares an adjacent Steiner point with another terminal.
Namely, $\mathbf{e_{2i}}$ shares an adjacent Steiner point $\mathbf{s_{2i}}$
with $\mathbf{e_{2i-1}}$ for each $i\in[2^{r-1}d]$. The third neighbor
$\mathbf{r}$ of $\mathbf{s_{2i}}$ in $T$ is the split of the Steiner point
neighboring $\mathbf{e_{i}}$ in the tree preceding $T$. In particular, then
$\lvert\lvert\mathbf{r}-\mathbf{e_{2i}}\rvert\rvert=\lvert\lvert\mathbf{r}-\mathbf{e_{2i-1}}\rvert\rvert$,
so $\triangle\mathbf{r}\mathbf{e_{2i-1}}\mathbf{e_{2i}}$ is isosceles. Hence,
$\mathbf{s_{2i}}$, the Fermat point of this triangle must be equidistant to
$\mathbf{e_{2i-1}}$ and $\mathbf{e_{2i}}$. Then,

$\lvert\lvert\mathbf{e_{2i-1}}-\mathbf{s_{2i}}\rvert\rvert=\lvert\lvert\mathbf{e_{2i}}-\mathbf{s_{2i}}\rvert\rvert=\sqrt{\frac{2}{3}}$

using that the angles includes by the edges to $\mathbf{s_{2i}}$ must be
$120\degree$ (since it is a Fermat point) and the distance between terminals
is $\sqrt{2}$. Now, as in Theorem 5.9, for the Fermat point of
$\triangle{\mathbf{e_{4i}}\mathbf{e_{4i-1}}\mathbf{s_{2i}^{\prime}}}$ to exist
in $T^{\prime}$, we need that the center of
$\mathbf{e_{4i}}\mathbf{e_{4i-1}}$, $\mathbf{c_{2i}}$, is at least
$\frac{1}{\sqrt{6}}$ from $\mathbf{s_{2i}^{\prime}}$. But, $\mathbf{c_{2i}}$
is the split of $\mathbf{e_{2i}}$ and
$\lvert\lvert\mathbf{e_{2i}}-\mathbf{s_{2i}}\rvert\rvert$ is
$\sqrt{\frac{2}{3}}$ from the above. Hence, by Lemma 5.8, we have
$\lvert\lvert\mathbf{c_{2i}}-\mathbf{s_{2i}^{\prime}}\rvert\rvert=\frac{1}{\sqrt{3}}>\frac{1}{\sqrt{6}}$,
as necessary. So, the Fermat points exist in constructing $T^{\prime}$.

Finally, we need to show that all included angles between edges sharing an
endpoint are at least $120\degree$ in $T^{\prime}$. The argument here is
identical to the argument in Theorem 5.9 (after applying the inductive
hypothesis), completing the proof. ∎

Consider the Steiner trees of $d$-dimensional simplices for some small value
of $d$ where we can determine explicit coordinates for every Steiner point
(e.g., $d=3,4$). The construction described in Theorem 5.9 yields the same
Steiner points as the numerical algorithm in [Smi92] for $d=6,8,12$ (up to
small errors presumably caused by the approximate nature of Smith’s
algorithm). For higher values of $d$ it was not checked due to computational
limitations.

###  5.3 Explicit construction for $d=2^{k}$

Applying Corollary 5.10 starting from $d=4$ yields an explicit construction
for Steiner trees of regular simplices on $n=2^{k}$ terminals. We analyze that
construction in detail in this section. To start, find explicit coordinates
for the Steiner points of a Steiner tree of the simplex on $d=4$ terminals.
Then, apply Theorem 5.9, $(k-2)$ many times.

Our topology will be given by two full binary trees $T^{0},T^{1}$, each on
$2^{k-1}$ terminals, and an edge connecting both roots. Now recall Definition
5.2 and label $T^{0}$ with respect to $0$ and $T^{1}$ with respect to $1$.
This is the representation of our tree that we will work with (see Figure 7).
For simplicity, when we will talk about coordinates related to a terminal, we
will use their unique binary label instead. The labels $i$ will be in the
range from $0$ to $d-1$ (in binary). Therefore, the terminal with label $i$
will be $\mathbf{e_{i+1}}$.

For $k\in\mathbb{N}$, let $\\{T_{m}\\}^{k}_{m=2}$ denote the sequence of trees
from our construction. Each vertex has a superscript and a subscript—the
superscript $m$ refers to the vertex belonging to the vertex set of $T_{m}$
and the subscript refers to the assigned binary string label. Steiner points
obtained by splitting will retain the same binary string label. Those obtained
as a new Fermat point will adopt the binary string label of the terminal whose
binary label was appended to form the two terminal endpoints of the triangle.
E.g., the Steiner point obtained as the split of $\mathbf{s^{k}_{b}}$ will be
$\mathbf{s^{k+1}_{b}}$. The Steiner point obtained as the Fermat point of
$\triangle\mathbf{s^{k+1}_{b}}\mathbf{p^{k+1}_{b00}}\mathbf{p^{k+1}_{b01}}$
will be $\mathbf{s^{k+1}_{b0}}$.

$\mathbf{p}_{\mathbf{00...000}}$$\mathbf{p}_{\mathbf{00...001}}$$\mathbf{p}_{\mathbf{00...010}}$$\mathbf{p}_{\mathbf{00...011}}$$\mathbf{s}_{\mathbf{0}}$$\mathbf{s}_{\mathbf{1}}$$\mathbf{s}_{\mathbf{00}}$$\mathbf{s}_{\mathbf{01}}$$\mathbf{s}_{\mathbf{00...0}}$$\mathbf{s}_{\mathbf{00...01}}$$\mathbf{s}_{\mathbf{00...0}0}$
Figure 7: Binary representation of terminals and Steiner points for $n=2^{k}$.

For $k=1$, $T_{1}$ is just the line segment
$\mathbf{p^{1}_{0}}\mathbf{p^{1}_{1}}$ connecting two terminals. For $k=2$, we
need to find the Steiner points $\mathbf{s^{2}_{0}}$ and $\mathbf{s^{2}_{1}}$.
Lemma 5.1 gives us the following: the edge between $\mathbf{s^{2}_{0}}$ and
$\mathbf{s^{2}_{1}}$ passes through
$\mathbf{c}=\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$, the
centroid of the terminals. Then, it holds that $\mathbf{s^{2}_{0}}$ and
$\mathbf{s^{2}_{1}}$ are the Fermat points of
$\triangle\mathbf{p^{2}_{00}}\mathbf{p^{2}_{01}}\mathbf{c}$ and
$\triangle\mathbf{p^{2}_{10}}\mathbf{p^{2}_{11}}\mathbf{c}$, respectively.
Therefore, we get:

$\displaystyle\mathbf{s^{2}_{0}}$
$\displaystyle=\left(\frac{1}{2}-\frac{1}{2\sqrt{6}},\frac{1}{2}-\frac{1}{2\sqrt{6}},\frac{1}{2\sqrt{6}},\frac{1}{2\sqrt{6}}\right),$
$\displaystyle\mathbf{s^{2}_{1}}$
$\displaystyle=\left(\frac{1}{2\sqrt{6}},\frac{1}{2\sqrt{6}},\frac{1}{2}-\frac{1}{2\sqrt{6}},\frac{1}{2}-\frac{1}{2\sqrt{6}}\right).$

For $k\geq 3$, let $\\{b_{j}\\}^{k-1}_{j=1}$ be the sequence of binary strings
of $j$ zeros. For brevity, we will only show the coordinates of points
$\mathbf{s^{k}_{b_{j}}}$. To obtain explicit formulas for other Steiner
points, it suffices to apply suitable topology-preserving coordinate
permutations.

Firstly, based on Theorem 5.9, we know that we obtain $\mathbf{s^{k}_{0}}$ by
splitting $\mathbf{s^{k-1}_{0}}$. Repeatedly applying this, we have

$\mathbf{s^{k}_{0}}=\frac{1}{2^{k-2}}\left(\underbrace{\frac{1}{2}-\frac{1}{2\sqrt{6}},\cdots}_{2^{k-1}\,\text{times}},\frac{1}{2\sqrt{6}},\cdots,\frac{1}{2\sqrt{6}}\right).$

Now for each $2\leq j\leq k-1$, let us find the first tree in our sequence
that has a Steiner point with the binary representation of $b_{j}$. It is
$T_{j+1}$. In this tree, the point $\mathbf{s^{j+1}_{b_{j}}}$ was constructed
as the Fermat point of
$\triangle\mathbf{p^{j+1}_{b_{j}0}}\mathbf{p^{j+1}_{b_{j}1}}\mathbf{s^{j+1}_{b_{j-1}}}$.
If we denote the center of
$\mathbf{p^{j+1}_{b_{j}0}}\mathbf{p^{j+1}_{b_{j}1}}$ as $\mathbf{c}^{j+1}$, we
already know from the proof of Corollary 5.10 that

$\lvert\lvert\mathbf{c}^{j+1}\mathbf{s^{j+1}_{b_{j}}}\rvert\rvert=\frac{1}{\sqrt{2}}\lvert\lvert\mathbf{c}^{j+1}\mathbf{s^{j+1}_{b_{j-1}}}\rvert\rvert.$

From this it follows that

$\displaystyle\mathbf{s^{j+1}_{b_{j}}}$
$\displaystyle=\mathbf{c}^{j+1}+\frac{1}{\sqrt{2}}\left(\mathbf{s^{j+1}_{b_{j-1}}}-\mathbf{c}^{j+1}\right)$
$\displaystyle=\frac{1}{\sqrt{2}}\mathbf{s^{j+1}_{b_{j-1}}}+\left(1-\frac{1}{\sqrt{2}}\right)\left(\frac{1}{2},\frac{1}{2},0,\cdots,0\right)$
$\displaystyle=\frac{1}{\sqrt{2}}\mathbf{s^{j+1}_{b_{j-1}}}+\left(\frac{1}{2}-\frac{1}{2\sqrt{2}},\frac{1}{2}-\frac{1}{2\sqrt{2}},0,\cdots,0\right).$

After that, we need to split $\mathbf{s^{j+1}_{b_{j}}}$ a total of $(k-j-1)$
times to obtain $\mathbf{s^{k}_{b_{j}}}$. Splitting is linear and can be done
separately on both summands

$\mathbf{s^{k}_{b_{j}}}=\frac{1}{\sqrt{2}}\mathbf{s^{k}_{b_{j-1}}}+\frac{1}{2^{k-j-1}}\left(\underbrace{\frac{1}{2}-\frac{1}{2\sqrt{2}},\cdots}_{2^{k-j}\,\text{times}},0,\cdots,0\right).$

We can then repeat this step with $\mathbf{s^{k}_{b_{j-1}}}$ and so on until
we get to $\mathbf{s^{k}_{0}}$

$\displaystyle\mathbf{s^{k}_{b_{j}}}=\left(\frac{1}{\sqrt{2}}\right)^{j-1}\mathbf{s^{k}_{0}}$
$\displaystyle+\frac{1}{2^{k-j-1}}\left(\underbrace{\frac{1}{2}-\frac{1}{2\sqrt{2}},\cdots}_{2^{k-j}\,\text{times}},0,\cdots,0\right)$
$\displaystyle+\frac{1}{\sqrt{2}\cdot
2^{k-j}}\left(\underbrace{\frac{1}{2}-\frac{1}{2\sqrt{2}},\cdots}_{2^{k-j+1}\,\text{times}},0,\cdots,0\right)$
$\displaystyle\vdots$
$\displaystyle+\frac{1}{(\sqrt{2})^{j-1}2^{k-2}}\left(\underbrace{\frac{1}{2}-\frac{1}{2\sqrt{2}},\cdots}_{2^{k-1}\,\text{times}},0,\cdots,0\right).$

Note that this type of construction is not restricted to powers of two: the
same can be done for any initial known Steiner tree. For example we can
explicitly write down the coordinates for $d=3\cdot 2^{k}$, $k\in\mathbb{N}$,
where the only part of the expression that changes is the point
$\mathbf{s^{k}_{0}}$. Or, by running some exact algorithm, e.g., Smith’s
algorithm, we can compute numerical approximations for the Steiner points of
the optimal Steiner tree for $d=c$ for some some small constant $c$ and then
apply the same technique to write down the coordinates for $d=c\cdot 2^{k}$,
$k\in\mathbb{N}$.

######  Conjecture 5.11.

This construction yields an optimal Steiner tree for every regular
$d$-simplex, where $d=2^{k}$, $k\geq 1$. Moreover, the natural generalization
yields the optimal Steiner tree for every regular $d$-simplex, $d\geq 3$.

The construction is closely related to the construction in [CG76]. The outcome
in both cases is that, instead of considering every terminal, it is enough to
represent each full binary tree by the centroid of its terminals. In essence,
this is the second property of optimal Steiner trees of the regular simplex
that we formalize in Lemma 5.1. It is not surprising to notice that the
asymptotic length of our constructions are the same (although our
constructions match the conjecture of Smith for all $d$, unlike [CG76]):

######  Proposition 5.12.

Let $T_{0}$ be a Steiner tree of the regular $d$-simplex. Let
$\\{T_{k}\\}_{k=0}^{\infty}$ be the sequence of Steiner trees of the regular
simplex created by repeatedly applying Theorem 5.9 to $T_{0}$ and let
$\ell_{k}$ denote the Steiner ratio for $T_{k}$. If
$\lim_{k\to\infty}\ell_{k}$ exists, then
$\lim_{k\to\infty}\ell_{k}=\frac{\sqrt{3}}{\sqrt{2}(2\sqrt{2}-1)}$.

###### Proof.

Suppose that we know $\ell_{0}$. Then we can recursively write

$\ell_{k+1}=\frac{\ell_{k}\left(d2^{k}-1\right)-\frac{d2^{k}}{\sqrt{6}}+d2^{k+1}\sqrt{\frac{2}{3}}}{\left(d2^{k+1}-1\right)\sqrt{2}}.$
(*)

The distance between all pairs of terminals is $\sqrt{2}$, yielding the
denominator. The tree resultant from taking the split of every node in $T_{k}$
(and retaining the same topology) is nearly $T_{k+1}$ and has cost
$\sqrt{2}\cdot\frac{\ell_{k}(d2^{k}-1)}{\sqrt{2}}$ by Lemma 5.8. However, we
do not include the entirety of each edge to the split of terminal $\mathbf{p}$
in $T_{k}$; we only continue along the edge to $\mathbf{p}$ to the Fermat
point of the triangle with the two new terminals corresponding to
$\mathbf{p}$. As argued in Corollary 5.10, this removes a length of
$\frac{1}{\sqrt{6}}$ per terminal in $T_{k}$. Finally, for each terminal in
$T_{k+1}$ we connect it to the Fermat point of its respective triangle. Each
such edge is of length $\sqrt{\frac{2}{3}}$ as argued in Corollary 5.10.
Combining these quantities yields the numerator.

If we assume that there exists $\ell=\lim_{k\to\infty}\ell_{k}$, then by
taking limits of both sides of (* ‣ 5.3), we get

$\ell=\frac{\ell}{2\sqrt{2}}-\frac{1}{4\sqrt{3}}+\frac{1}{\sqrt{3}}.$

Therefore, by expressing $\ell$, we obtain

$\ell=\frac{\sqrt{3}}{\sqrt{2}\left(2\sqrt{2}-1\right)}.$

∎

To show that the limit exists, it is enough to show that
$\ell_{0}>\frac{\sqrt{3}}{\sqrt{2}(2\sqrt{2}-1)}$—it then follows from the
recursive formula that $\ell_{k}>\frac{\sqrt{3}}{\sqrt{2}(2\sqrt{2}-1)}$ and
that the sequence $\\{\ell_{k}\\}_{k=0}^{\infty}$ is strictly decreasing. This
holds for $T_{0}$ being the numerically computed optimal Steiner tree of the
regular $d$-simplex for all $3\leq d\leq 12$, for example.

##  6 Progress towards Conjecture 1.3

In this section, we consider Conjecture 1.3. For ease of notation throughout,
we use $f:G(V,E)\to\operatorname{\mathbb{R}}^{|V|}$ to denote the embedding of
each edge in $G$ as its characteristic vector (e.g., $(i,j)$ is mapped to
$\mathbf{e_{i}}+\mathbf{e_{j}}$). As evidence of the efficiency of the Steiner
trees of regular simplices, we observe the following lemma.

######  Lemma 6.1.

For any fixed $m\geq 1$, the graph of size $m$ whose embedding (as above) has
the minimum cost Steiner tree has diameter at most $2$.

That is, the only embeddings of graphs that might have more efficient Steiner
trees than the embedding of the star graph (which embeds as a regular simplex)
have diameter at most $2$. We actually prove an even stronger result.

######  Lemma 6.2.

Let $G=(V,E)$ be a graph with $|E|=m$ with two vertices with disjoint closed
neighborhoods. Then, there exists some $G^{\prime}(V^{\prime},E^{\prime})$
with $|E^{\prime}|=m$ with all closed neighborhoods of vertices pairwise
overlapping such that $f(G^{\prime})$ has a Steiner tree of total length less
than the total length of the optimal Steiner tree of $f(G)$.

###### Proof.

Without loss of generality, let $V=[n]$. Let $i$ and $j$ be two vertices with
disjoint neighborhoods. This implies that the two sets of endpoints of edges
incident to $i$ and $j$ are disjoint.

Now let $T$ be an optimum Steiner tree for $f(G)$ ($f$ is the embedding
function described at the beginning of this section and in Section 1). We
transform $T$ into a lower total length Steiner tree on $f(G^{\prime})$ for
$G^{\prime}$ a graph with the neighborhoods of any pair of vertices
overlapping.

For each point $\mathbf{x}=(x_{1},x_{2},\ldots x_{n})$ in $T$, set the $i$th
coordinate equal to $\max(x_{i},x_{j})$ and then set the $j$th coordinate
equal to $0$. First, note that this operation maps each embedding of an edge
incident to $j$, $f(k,j)$, to a distinct embedding of an edge incident to $i$
(namely, the embedding of the edge $(k,i)$). The resultant collection of
embedded edges is the result of embedding $G$ after contracting the vertices
$i$ and $j$ (call the contraction of $i$ and $j$ the graph $G^{\prime}$):
there are no lost or repeated edges exactly because $i$ and $j$ have disjoint
closed neighborhoods. Second, this fixes all the other embedded edges in the
configuration.

Now, consider two points $\mathbf{x}=(x_{1},x_{2},\ldots x_{n})$ and
$\mathbf{y}=(y_{1},y_{2},\ldots y_{n})$ in $T$ with an edge between them. We
want to show that the distance between them has not increased as a result of
this map. The difference in each coordinate other than the $i$th and $j$th
coordinates is fixed. So, it suffices to show that

$(x_{i}-y_{i})^{2}+(x_{j}-y_{j})^{2}\geq(\max(x_{i},x_{j})-\max(y_{i},y_{j}))^{2}.$

Expanding both sides, we have to show that

$x_{i}^{2}+x_{j}^{2}+y_{i}^{2}+y_{j}^{2}-2x_{i}y_{i}-2x_{j}y_{j}\geq\max(x_{i},x_{j})^{2}+\max(y_{i},y_{j})^{2}-2\max(x_{i},x_{j})\max(y_{i},y_{j}).$

We have two cases to consider. First, suppose $\max(x_{i},x_{j})=x_{i}$ and
$\max(y_{i},y_{j})=y_{i}$. Then we have

$\displaystyle(x_{i}-y_{i})^{2}+(x_{j}-y_{j})^{2}$
$\displaystyle=(\max(x_{i},x_{j})-\max(y_{i},y_{j}))^{2}+(x_{j}-y_{j})^{2}$
$\displaystyle\geq(\max(x_{i},x_{j})-\max(y_{i},y_{j}))^{2}.$

Notably, we have an equality in the second line only if $x_{j}=y_{j}$. The
case of the maxima in the $j$th coordinates follows symmetrically (with
equality only if $x_{i}=y_{i}$).

Now suppose $\max(x_{i},x_{j})=x_{i}$ and $\max(y_{i},y_{j})=y_{j}$. First
note that we have

$(x_{i}-x_{j})y_{j}\geq(x_{i}-x_{j})y_{i}$

since $x_{i}\geq x_{j}$ and $y_{j}\geq y_{i}\geq 0$ (since $\mathbf{x}$ and
$\mathbf{y}$ are in the convex hull of $f(G)$ by Theorem 2.4). This implies

$2x_{i}y_{j}+2x_{j}y_{i}\geq 2x_{i}y_{i}+2x_{j}y_{j}.$ (1)

Now,

$\displaystyle
x_{i}^{2}+x_{j}^{2}+y_{i}^{2}+y_{j}^{2}-2x_{i}y_{i}-2x_{j}y_{j}$
$\displaystyle=\max(x_{i},x_{j})^{2}+\max(y_{i},y_{j})^{2}+x_{j}^{2}+y_{i}^{2}-2x_{i}y_{i}-2x_{j}y_{j}$
$\displaystyle=\max(x_{i},x_{j})^{2}+\max(y_{i},y_{j})^{2}+(x_{j}-y_{i})^{2}+2x_{j}y_{i}-2x_{i}y_{i}-2x_{j}y_{j}.$

Then, (1) implies that

$(x_{i}-y_{i})^{2}+(x_{j}-y_{j})^{2}\geq(\max(x_{i},x_{j})-\max(y_{i},y_{j}))^{2},$

with equality exactly when $x_{i}=y_{i}=x_{j}$ or $x_{j}=y_{j}=y_{i}$. The
case of $\max(x_{i},x_{j})=x_{j}$ and $\max(y_{i},y_{j})=y_{i}$ follows by
symmetry.

Finally, note that equality holds in either case only when the smaller of the
$i$th and $j$th coordinates of the two points are of equal magnitude. But,
consider a Steiner point $\mathbf{s}$ adjacent to terminal node $\mathbf{p}$.
Such an incidence must occur by Lemma 3.4. Since $i$ and $j$ are non-adjacent
in $G$, either $p_{i}$ or $p_{j}$ are $0$. But then in particular
$\min(p_{i},p_{j})=0$, so, in order to have equality in the above, $s_{i}$ or
$s_{j}$ must equal $0$, contradicting optimality as a result of Lemma 3.2. ∎

## Acknowledgments

This work was carried out while the authors Guillermo A. Gamboa Q., Josef
Matějka, and Jakub Petr were participants in the 2023 DIMACS REU program at
Rutgers University, supported by CoSP, a project funded by European Union’s
Horizon 2020 research and innovation programme, grant agreement No. 823748.
Karthik C. S. is supported by the National Science Foundation under Grant
CCF-2313372 and by the Simons Foundation, Grant Number 825876, Awardee Thu D.
Nguyen.

## References

  * [Aro98] Sanjeev Arora.  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  Journal of the ACM, 45(5):753–782, Sep 1998.
  * [BGTZ14] Marcus Brazil, Ronald L. Graham, Doreen A. Thomas, and Martin Zachariasen.  On the history of the Euclidean Steiner tree problem.  Archive for history of exact sciences, 68(3):327–354, 2014.
  * [BRK+12] Christina Backes, Alexander Rurainski, Gunnar W. Klau, Oliver Müller, Daniel Stöckel, Andreas Gerasch, Jan Küntzer, Daniela Maisel, Nicole Ludwig, Matthias Hein, et al.  An integer linear programming approach for finding deregulated subgraphs in regulatory networks.  Nucleic acids research, 40(6):e43–e43, 2012.
  * [CD13] Xiuzhen Cheng and Ding-Zhu Du.  Steiner trees in industry, volume 11.  Springer Science & Business Media, 2013.
  * [CG76] F. R. K. Chung and E. N. Gilbert.  Steiner trees for the regular simplex.  Bulletin of the Institute of Mathematics Academia Sinica, 4:312–325, 1976.
  * [Cho01] Jun-Dong Cho.  Steiner tree problems in VLSI layout designs.  In Steiner Trees in Industry, pages 101–173. Springer, 2001.
  * [CR41] R. Courant and H. Robbins.  What is Mathematics? Oxford University Press, 1941.
  * [CZ13] Ya-Hong Cheng and Xiao-Dong Zhang.  The Wiener and terminal Wiener indices of trees.  MATCH Communications in Mathematical and Computer Chemistry, 70(2):591–602, 2013.
  * [DEG01] Andrey A Dobrynin, Roger Entringer, and Ivan Gutman.  Wiener index of trees: theory and applications.  Acta Applicandae Mathematica, 66:211–249, 2001.
  * [DJS86] William H. E. Day, David S. Johnson, and David Sankoff.  The computational complexity of inferring rooted phylogenies by parsimony.  Mathematical Biosciences, 81(1):33–42, 1986.
  * [DS96] Ding-Zhu Du and Warren D. Smith.  Disproofs of generalized Gilbert–Pollak conjecture on the Steiner ratio in three or more dimensions.  Journal of Combinatorial Theory, Series A, 74(1):115–130, Apr 1996\.
  * [DZ12] Xiaotie Deng and Jie Zhang.  Equiseparability on terminal Wiener index.  Applied Mathematics Letters, 25(3):580–585, Mar 2012.
  * [FGK24] Henry Fleischmann, Surya Teja Gavva, and Karthik C. S.  On approximability of Steiner tree in $\ell_{p}$-metrics.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024.
  * [GFP09] Ivan Gutman, Boris Furtula, and Miroslav Petrović.  Terminal Wiener index.  Journal of Mathematical Chemistry, 46(2):522–531, Aug 2009.
  * [GGJ77] Michael R. Garey, Ronald L. Graham, and David S. Johnson.  The complexity of computing Steiner minimal trees.  SIAM Journal on Applied Mathematics, 32(4):835–859, 1977.
  * [GJ77] Michael R. Garey and David S. Johnson.  The rectilinear Steiner tree problem is $np$-complete.  SIAM Journal on Applied Mathematics, 32(4):826–834, 1977.
  * [GP68] E. N. Gilbert and H. O. Pollak.  Steiner minimal trees.  SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
  * [Han66] Maurice Hanan.  On Steiner’s problem with rectilinear distance.  SIAM Journal on Applied Mathematics, 14(2):255–265, 1966.
  * [HR92] Frank K. Hwang and Dana S. Richards.  Steiner tree problems.  Networks, 22(1):55–89, 1992.
  * [HW13] Peter J. Humphries and Taoyang Wu.  On the neighborhoods of trees.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10(3):721–728, May 2013.
  * [IOSS02] Trey Ideker, Owen Ozier, Benno Schwikowski, and Andrew F Siegel.  Discovering regulatory and signalling circuits in molecular interaction networks.  Bioinformatics, 18(suppl_1):S233–S240, 2002.
  * [IT12] A. O. Ivanov and A. A. Tuzhilin.  The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement.  Algorithmica, 62(1–2):630–632, Feb 2012.
  * [JK34] Vojtěch Jarník and Miloš Kössler.  O minimálních grafech, obsahujících $n$ daných bodů.  Časopis pro pěstování matematiky a fysiky, 063(8):223–235, 1934.
  * [Len12] Thomas Lengauer.  Combinatorial algorithms for integrated circuit layout.  Springer Science & Business Media, 2012.
  * [Lju21] Ivana Ljubić.  Solving Steiner trees: Recent advances, challenges, and perspectives.  Networks, 77(2):177–204, 2021.
  * [LSW17] Euiwoong Lee, Melanie Schmidt, and John Wright.  Improved and simplified inapproximability for k-means.  Information Processing Letters, 120:40–43, 2017.
  * [Mit99] Joseph S. B. Mitchell.  Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems.  SIAM Journal on Computing, 28(4):1298–1309, 1999.
  * [NR22a] M Puruchothama Nayaki and F. Simon Raj.  Diagrammatic representation between topological indices and alkanes.  Journal of Algebraic Statistics, 13(2):3536–3545, 2022.
  * [NR22b] M Puruchothama Nayaki and F. Simon Raj.  The physical-chemical characteristics of alkanes and Wiener indices.  Journal of Algebraic Statistics, 13(2):3338–3345, 2022.
  * [NRRK17] Mohammad Noormohammadpour, Cauligi S. Raghavendra, Sriram Rao, and Srikanth Kandula.  DCCast: Efficient point to multipoint transfers across datacenters.  In 9th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 17), 2017.
  * [RBK21] Harishchandra Ramane, Kavita Bhajantri, and Deepa Kitturmath.  Terminal status of vertices and terminal status connectivity indices of graphs with its applications to properties of cycloalkanes.  Communications in Combinatorics and Optimization, (Online First), Aug 2021.
  * [RN10] Olga Russakovsky and Andrew Y. Ng.  A Steiner tree approach to efficient object detection.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1070–1077. IEEE, 2010.
  * [RP08] Mauricio G. C. Resende and Panos M. Pardalos.  Handbook of optimization in telecommunications.  Springer Science & Business Media, 2008.
  * [Smi92] W. D. Smith.  How to find Steiner minimal trees in Euclidean $d$-space.  Algorithmica, 7:137–177, 1992.
  * [Spa96] P. G. Spain.  The Fermat point of a triangle.  Mathematics Magazine, 69(2):131–133, 1996.
  * [Sul22] A Sulphikar.  Computation of terminal Wiener index from subtrees.  International Journal of Information Technology, 14(6):3175–3181, Oct 2022.
  * [SWW11] L.A. Székely, Hua Wang, and Taoyang Wu.  The sum of the distances between the leaves of a tree and the ‘semi-regular’ property.  Discrete Mathematics, 311(13):1197–1203, 2011.  Selected Papers from the 22nd British Combinatorial Conference.
  * [TGK+16] Nurcan Tuncbag, Sara J. C. Gosline, Amanda Kedaigle, Anthony R. Soltis, Anthony Gitter, and Ernest Fraenkel.  Network-based interpretation of diverse high-throughput datasets through the omics integrator software package.  PLoS computational biology, 12(4):e1004879, 2016.
  * [Tre00] Luca Trevisan.  When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree.  SIAM J. Comput., 30(2):475–485, 2000.
  * [Wie47] Harry Wiener.  Structural determination of paraffin boiling points.  Journal of the American Chemical Society, 69(1):17–20, Jan 1947\.
  * [ZEME16] Meryam Zeryouh, Mohamed El Marraki, and Mohamed Essalih.  On the terminal Wiener index of networks.  In 2016 5th International Conference on Multimedia Computing and Systems (ICMCS), page 533–536, Marrakech, Morocco, Sep 2016. IEEE.
  * [ZME14] Meryam Zeryouh, Mohamed El Marraki, and Mohamed Essalih.  Wiener and terminal Wiener indices of some rooted trees.  Applied Mathematical Sciences, 8:4995–5002, 2014.

##  Appendix A Inapproximability of the Euclidean Steiner Tree problem

In this section we formalize the reduction strategy for showing
$\mathsf{APX}$-hardness of the Euclidean Steiner tree sketched in Section 1.

Informally, we conjecture that regular simplicial complexes admit more
efficient Steiner trees when they are composed of fewer simplices. Formally,
we conjecture the following.

######  Conjecture A.1 (Euclidean Steiner Tree for Regular Simplicial
Complexes).

For all constants $r\in(0,1)$ and $\alpha\in(0,1/r-1)$, there exist constants
$s,\beta>0$ and $M\in\mathbb{Z}^{+}$ sufficiently large so that, for all
$m\geq M$, given a regular, unit, simplicial complex on $m$ vertices:

  1. 1.

Completeness: If the vertices can be partitioned into the vertices of at most
$rm$ unit, regular simplices, then the point configuration of the $m$ vertices
admits an Euclidean Steiner tree of cost at most $sm$.

  2. 2.

Soundness: If the vertices cannot be partitioned into the vertices of fewer
than $(1+\alpha)rm$ unit, regular simplices, then the point configuration of
the $m$ vertices does not admit an Euclidean Steiner tree of cost less than
$(1+\beta)sm$.

In the above, for simplicity, we consider a single point to be a regular, unit
simplex with one vertex. Conjecture A.1 is entirely analytical; it does not
directly involve any computation. Nonetheless, we show that if Conjecture A.1
holds (or indeed a somewhat weaker conjecture holds), then the Euclidean
Steiner tree problem is $\mathsf{APX}$-hard.

######  Theorem A.2.

Conjecture A.1 implies that the Euclidean Steiner tree problem is
$\mathsf{APX}$-hard.

###### Proof.

We reduce from the Vertex Cover problem on triangle-free graphs. From [LSW17],
there exists $r\in(0,1)$ and $\alpha\in(0,1/r-1)$, and a family of $m$-edge,
$n$-node graphs such that the following decision problem is $\mathsf{NP}$-hard
(where $n$ is a fixed function of $m$). Given an input graph $G$, decide which
of the following cases holds.

  * •

Completeness: There exists a vertex cover of $G$ of size $rm$.

  * •

Soundness: All vertex covers of $G$ are of size at least $(1+\alpha)rm$.

We will now describe a reduction from the Vertex Cover problem on triangle-
free graphs to the Euclidean Steiner tree problem. Define
$f_{n}:[n]^{2}\to\operatorname{\mathbb{R}}^{n}$ where
$f_{n}(i,j)=\frac{1}{\sqrt{2}}\cdot(\mathbf{e_{i}}+\mathbf{e_{j}})$, the sum
of the $i$th and $j$th standard basis vectors. Since the choice of domain will
always be clear from context, we will abuse notation and denote $f_{n}$ by
$f$. For a graph $G$ of order $n$, let

$f(G)=f(E(G))=\\{f(i,j)\,:\,(i,j)\in E(G)\\}.$

Now, given an input graph $G$ to the Vertex Cover problem on triangle-free
graphs described above, our corresponding instance of the Euclidean Steiner
Tree problem will be the instance on the terminal set $f(G)$. This mapping
takes $O(\operatorname{poly}(m))$ time. Observe that $f(G)$ is exactly the
collection of vertices of a regular, unit simplicial complex on $m$ vertices.
Let $s$ and $\beta$ be as in Conjecture A.1 for $r$ and $\alpha$ as in
Conjecture A.1 and $m$ sufficiently large.

#### Completeness.

If the completeness case holds, i.e., $G$ admits a vertex cover $C$ of size
$rm$, then the points in $f(G)$ can be partitioned into the vertices of at
most $rm$ regular, unit simplices. Namely, if vertex $i\in C$, then the
collection of points $S_{i}=\\{f(i,j)\,:\,(i,j)\in E\\}\subseteq f(G)$ (the
embeddings of each edge incident to vertex $i$) forms the vertices of a
regular, unit simplex. Since $C$ is a vertex cover of $G$, every edge in $G$
is incident to some vertex in $C$. Namely, $f(G)\subset\cup_{i\in C}S_{i}$.
Since any subset of the vertices of a regular, unit simplex also forms the
vertices of a regular, unit simplex (using the convention that a single vertex
is the vertex of a regular, unit simplex on one vertex), any arbitrary
partition of $f(G)$ among the $S_{i}$’s is a partitioning of $f(G)$ into the
vertices of at most $rm$ unit, regular simplices. Hence, by the completeness
case of Conjecture A.1, $f(G)$ admits an Euclidean Steiner tree of cost at
most $sm$.

#### Soundness.

Now suppose that the soundness case holds, i.e., all vertex covers of $G$ are
of size at least $(1+\alpha)m$. We need to show that the points in $f(G)$
cannot be partitioned into the vertices of fewer than $(1+\alpha)rm$ regular,
unit simplices (and, hence, the soundness case of Conjecture A.1 applies). To
do this, we make a series of claims.

######  Claim A.1.

For $\\{i,j\\},\\{k,\ell\\}\in E(G)$ such that
$\\{i,j\\}\cap\\{k,\ell\\}=\emptyset$, $f(i,j)$ and $f(k,\ell)$ cannot belong
to the same regular, unit simplex in any partition of $f(G)$ into the vertices
of regular, unit simplices.

###### Proof.

Note that $\lvert\lvert f(i,j)-f(k,\ell)\rvert\rvert_{2}=\sqrt{2}\neq 1$. ∎

######  Claim A.2.

For $S\subset E(G)$ with $|S|\neq\emptyset$ such that $\cap_{e\in
S}e=\emptyset$, the points in $f(S)$ cannot all belong to the same regular,
unit simplex in any partition of $f(G)$ into the vertices of regular, unit
simplices.

###### Proof.

The case of $|S|=1$ is trivial and the case of $|S|=2$ follows immediately
from Claim A.1.

Now assume that $|S|\geq 3$. Suppose that $e_{1}=\\{i,j\\}\in S$. By Claim
A.1, for all $e\in S$, either $i\in e$ or $j\in e$. Since $\cap_{e\in
S}e=\emptyset$, there exists $e_{2}\in S$ such that $i\in e_{2}$ and $j\not\in
e_{2}$ and $e_{3}\in S$ such that $i\not\in e_{3}$ and $j\in e_{3}$. Now, by
Claim A.1 again, $e_{2}$ and $e_{3}$ must share a vertex, so $e_{2}=\\{i,k\\}$
and $e_{3}=\\{j,k\\}$. But, $G$ is triangle-free and $e_{1},e_{2},$ and
$e_{3}$ form a triangle, yielding a contradiction. ∎

Now, Claim A.2 implies that in any partition $E_{1}\sqcup E_{2}\cdots$ of
$E(G)$ corresponding to a partition of $f(G)$ into the vertices of regular,
unit simplices, for each part $E_{i}$, there exists $v_{i}\in V$ such that
$v_{i}\in\cap_{e\in E_{i}}e$. Indeed, the $v_{i}$’s form a vertex cover of
$G$, implying that $G$ has a vertex cover of size at most the size of the
partition of $f(G)$ into the vertices of regular, unit simplices. Hence, by
our assumption in the soundness case of our hard instance of the Vertex Cover
problem, the vertices in $f(G)$ cannot be partitioned into the vertices of
fewer than $(1+\alpha)rm$ unit, regular simplices. Then, by the soundness case
of Conjecture A.1, $f(G)$ does not admit an Euclidean Steiner Tree of cost
less than $(1+\beta)sm$ in this case.

Combining the analysis of the completeness and soundness cases, the Euclidean
Steiner Tree problem is $\mathsf{NP}$-hard to approximate within a factor of
less than $(1+\beta)$, yielding the desired result. ∎ Note that we only used a
weaker version of Conjecture A.1 to prove Theorem A.2. Indeed, we really only
need that $s$ and $\beta$ exist for $r$ and $\alpha$ induced by the
inapproximability of Vertex Cover on triangle-free graphs.