Length of a Full Steiner Tree as a Function of Terminal Coordinates

Alexei Yu. Uteshev, Elizaveta A.
<EMAIL_ADDRESS>
St. Petersburg State University, St. Petersburg, Russia

Given the coordinates of the terminals $\\{(x_{j},y_{j})\\}_{j=1}^{n}$ of the
full Euclidean Steiner tree, its length equals

$\left|\sum_{j=1}^{n}z_{j}U_{j}\right|\,,$

where $\\{z_{j}:=x_{j}+\mathbf{i}y_{j}\\}_{j=1}^{n}$ and
$\\{U_{j}\\}_{j=1}^{n}$ are suitably chosen $6$th roots of unity. We also
extend this result for the cost of the optimal Weber networks which are
topologically equivalent to some full Steiner trees.

##  1 Introduction

The problem of construction of the shortest possible network interconnecting
the set of points (further referred to as terminals)
$\mathbb{P}=\\{P_{j}\\}_{j=1}^{n}\subset\mathbb{R}^{d},n\geq 3,d\geq 2$ is
known as the Euclidean Steiner minimal tree problem (SMT problem). We will
treat here only the planar version of the problem, i.e. $d=2$. For this case,
some specializations of the set $\mathbb{P}$ guarantee the solution to the
problem in the form of a minimum spanning tree. However, for other
configurations of $\mathbb{P}$, the optimal network contains some extra
vertices (junctions) known as the Fermat-Torricelli or Steiner points. Every
such a point in the optimal network possesses the degree $3$, and has the
adjacent edges meeting at $2\pi/3$.

The SMT problem has a long and intriguing history [2]. It is known to be NP-
hard. Establishing the topology of the minimal tree or even estimation of its
length for the general set $\mathbb{P}$ is the subject of numerous and
inventive research efforts. In the variety of potential solutions, it is
possible to distinguish a type of subtrees with a relatively ordered
structure. A Steiner tree with $n$ terminals is called a full Steiner tree if
it contains $n-2$ Steiner points. In this case, each terminal has degree equal
to $1$. Every Steiner minimal tree can be (uniquely) represented as a union of
full Steiner trees constructed for the subsets of the set $\mathbb{P}$. Any
pair of these subtrees might have at most one common terminal.

The first aim of the present paper is express the length of a full Steiner
tree as an explicit function of the terminal coordinates. In [1] this length
is computed via the lengths of the segments $|P_{j}P_{j+1}|$ (for the
appropriate numeration of terminals). In [12] the expression for the length
was obtained in the so-called _hexagonal coordinates of terminals_ which are
claimed to be _more natural than the common Cartesian coordinate system_. We
intend to dispute this claim by presenting the formula for the length in terms
of Cartesian coordinates. For the aim of deducing the formula from the
Abstract, we will place the problem into the complex plane. In Section 3 we
present the proof of the length formula and discuss its relation to one
Maxwell’s result [6].

A natural generalization of the SMT problem is the (multifacility) Weber
problem. It is stated as that of location of the given number $\ell\geq 2$ of
points (named facilities) $\\{W_{r}\\}_{r=1}^{\ell}\subset\mathbb{R}^{d}$
connected to the terminals of the set $\mathbb{P}$ that solve the optimization
problem

$\displaystyle\min_{\\{W_{1},\dots,W_{\ell}\\}\subset\mathbb{R}^{d}}\left\\{\sum_{j=1}^{n}\sum_{r=1}^{\ell}m_{rj}|W_{r}P_{j}|+\sum_{k=1}^{\ell}\sum_{r=k+1}^{\ell-1}\widetilde{m}_{rk}|W_{r}W_{k}|\right\\}\,;$
(1.1)

here some of the weights $m_{ij}$ and $\widetilde{m}_{ik}$ might be zero. The
value (1.1) will be referred to as the minimal cost of the network. It can be
expected that this problem should be more complicated than the SMT one. It
really is even for the planar case, i.e. for $d=2$. In contrast with the SMT,
the optimal Weber network might contain facilities of degree greater than $3$.
However, we conjecture that in a restricted version of the planar Weber
problem, one may expect the existence of the counterpart for the Steiner tree
length formula expressing the minimal cost by radicals with respect to the
problem parameters of (terminal coordinates and weights). This relates to the
networks topologically equivalent to some full Steiner trees, i.e. the
networks where each terminal has degree equal to $1$ while the degree of each
facility equal to $3$. We discuss this issue in Section 5.

Notation. We set $z_{j}:=x_{j}+\mathbf{i}y_{j}$ and denote the $6$th roots of
unity

$\upsilon_{k}:=\cos\frac{\pi k}{3}+\mathbf{i}\sin\frac{\pi
k}{3}\quad\mbox{for}\ k\in\\{0,1,\dots,5\\}\,,$ (1.2)

while the third roots of unity as

$\varepsilon_{0}=1,\varepsilon_{1}=-\frac{1}{2}+\mathbf{i}\frac{\sqrt{3}}{2},\
\varepsilon_{2}=-\frac{1}{2}-\mathbf{i}\frac{\sqrt{3}}{2};$ (1.3)

Evidently,
$\upsilon_{0}=1=-\upsilon_{3},\upsilon_{1}=-\upsilon_{4}=-\varepsilon_{2},\upsilon_{2}=-\upsilon_{5}=\varepsilon_{1}$.

$\mathfrak{L}$ and $\mathfrak{C}$ stand for respectively minimal length of the
Steiner network and minimal cost of the Weber network.

For the convenience of the reader, we place here the Classical Geometry result
which we often refer to in what follows:

######  Theorem 1.1 (Ptolemy)

A quadrilateral is inscribable in a circle if and only if the product of the
lengths of its diagonals is equal to the sum of the products of the lengths of
the pairs of opposite sides.

##  2 Hints

Geometric conditions for the existence of a full Steiner tree for the case
$n=3$ and $n=4$ terminals are well known, and we assume them to be fulfilled
for the terminal sets treated in the present section. In [8] these conditions
are converted into analytical form, aside with formulas for Steiner point
coordinates and the tree length. This provides one with an opportunity to
verify directly the test examples of this and the next sections.

For the case of $3$ terminals, the Torricelli-Simpson construction of the
Steiner (Fermat-Torricelli) point is based on finding an extra point $Q_{1}$
in the plane yielding the equilateral triangle $P_{1}P_{2}Q_{1}$ (Fig.1).

(a)

(b)

Figure 1. Steiner tree construction for three terminals

The point of intersection of the segment $Q_{1}P_{3}$ with the circle
circumscribing this triangle is the Steiner point $S_{1}$. Due to Theorem 1.1,
one gets

$|Q_{1}S_{1}|=|P_{1}S_{1}|+|P_{2}S_{1}|\,,$

and therefore the length of the SMT connecting the terminals
$P_{1},P_{2},P_{3}$ equals $|Q_{1}P_{3}|$. The coordinates of the point
$Q_{1}$ can be easily determined. There are two possibilities for its location
(on each side of the line $P_{1}P_{2}$), and we need the variant opposite to
$P_{3}$. For a configuration similar to that displayed in Fig. 1 (i.e. the
triangle vertices are numbered counterclockwise), one gets:

$Q_{1}:=(q_{1x},q_{1y})=\left(\frac{1}{2}x_{1}+\frac{1}{2}x_{2}-\frac{\sqrt{3}}{2}y_{1}+\frac{\sqrt{3}}{2}y_{2}\,,\
\frac{\sqrt{3}}{2}x_{1}-\frac{\sqrt{3}}{2}x_{2}+\frac{1}{2}y_{1}+\frac{1}{2}y_{2}\right)\,.$
(2.1)

or, alternatively, in the complex plane

$\mathfrak{q}_{1}:=q_{1x}+\mathbf{i}q_{1y}=\left(\frac{1}{2}+\mathbf{i}\frac{\sqrt{3}}{2}\right)x_{1}+\left(\frac{1}{2}-\mathbf{i}\frac{\sqrt{3}}{2}\right)x_{2}+\left(-\frac{\sqrt{3}}{2}+\mathbf{i}\frac{1}{2}\right)y_{1}+\left(\frac{\sqrt{3}}{2}+\mathbf{i}\frac{1}{2}\right)y_{2}$
$=\left(\frac{1}{2}+\mathbf{i}\frac{\sqrt{3}}{2}\right)z_{1}+\left(\frac{1}{2}-\mathbf{i}\frac{\sqrt{3}}{2}\right)z_{2}=\upsilon_{1}z_{1}+\upsilon_{5}z_{2}=-\varepsilon_{2}z_{1}-\varepsilon_{1}z_{2}\,.$

For this case, the length of the (full) Steiner tree equals

$\mathfrak{L}=|Q_{1}P_{3}|=|z_{3}-\mathfrak{q}_{1}|=|\upsilon_{4}z_{1}+\upsilon_{2}z_{2}+z_{3}|=|z_{3}+\varepsilon_{2}z_{1}+\varepsilon_{1}z_{2}|\,.$
(2.2)

###### Example 2.1

For the terminals

$P_{1}=(4,4),\ P_{2}=(2,1),P_{3}=(7,1)\,,$

(Fig. 1), formula (2.2) yields

$\mathfrak{L}=|7+\mathbf{i}+\varepsilon_{2}(4+4\mathbf{i})+\varepsilon_{1}(2+\mathbf{i})|=|4+3\sqrt{3}/2-\mathbf{i}(3/2+\sqrt{3})|=\sqrt{28+15\sqrt{3}}\approx
7.347160\,.$

For the case of $4$ terminals $\\{P_{j}\\}_{j=1}^{4}$, the geometrical
algorithm for Steiner tree construction [3] with two Steiner points in the
topology $\begin{array}[]{c}P_{1}\\\
P_{2}\end{array}S_{1}S_{2}\begin{array}[]{c}P_{4}\\\ P_{3}\end{array}$, is
illuminated in Fig. 2.

Figure 2. Steiner tree construction for four terminals

Coordinates of $Q_{2}$ are computed similar to $Q_{1}$:

$Q_{2}:=(q_{2x},q_{2y})\mapsto\mathfrak{q}_{2}=q_{2x}+\mathbf{i}q_{2y}=\upsilon_{1}z_{3}+\upsilon_{5}z_{4}\,.$

The length of the tree equals

$\mathfrak{L}=|Q_{1}Q_{2}|=|\mathfrak{q}_{1}-\mathfrak{q}_{2}|=|\upsilon_{1}z_{1}+\upsilon_{5}z_{2}+\upsilon_{4}z_{3}+\upsilon_{2}z_{4}|\stackrel{{\scriptstyle(\ref{Roots_3})}}{{=}}|\varepsilon_{2}(z_{3}-z_{1})+\varepsilon_{1}(z_{4}-z_{2})|$

From this immediately follows equivalent equalities

$\mathfrak{L}=\mathfrak{L}\cdot|-\varepsilon_{1}|=|(z_{1}-z_{3})+(z_{2}-z_{4})\varepsilon_{2}|=|(z_{2}-z_{4})+(z_{1}-z_{3})\varepsilon_{1}|\,.$
(2.3)

In the case of existence a Steiner tree in the alternative topology
$\begin{array}[]{c}P_{4}\\\
P_{1}\end{array}\tilde{S}_{1}\tilde{S}_{2}\begin{array}[]{c}P_{3}\\\
P_{2}\end{array}$, its length is given by the formula

$\tilde{\mathfrak{L}}=|(z_{1}-z_{3})+(z_{4}-z_{2})\varepsilon_{1}|\,.$

###### Example 2.2

For the terminals

$P_{1}=(2,6),\ P_{2}=(1,1),P_{3}=(9,2),P_{4}=(6,7)\,,$

and the Steiner tree topology $\begin{array}[]{c}P_{1}\\\
P_{2}\end{array}S_{1}S_{2}\begin{array}[]{c}P_{4}\\\ P_{3}\end{array}$ (Fig.
2), formula (2.3) yields

$\mathfrak{L}=|-7+4\mathbf{i}+(-5-6\mathbf{i})\varepsilon_{2}|=|-9/2-3\sqrt{3}+\mathbf{i}(7+5\sqrt{3}/2)|=\sqrt{115+62\sqrt{3}}\approx
14.912651\,.$

Check. The Steiner points:

$S_{1}=\left(\frac{5587}{3386}+\frac{1743}{3386}\sqrt{3},\frac{11183}{3386}+\frac{12107}{10158}\sqrt{3}\right)\approx(2.541631,5.367094)\,,$
$S_{2}=\left(\frac{25479}{3386}-\frac{3711}{3386}\sqrt{3},\frac{16193}{3386}+\frac{2267}{3386}\sqrt{3}\right)\approx(5.626509,5.941984)\,.$

Our next aim is to discover the correlation between the sequences of terminals
$\\{z_{j}\\}$ and the roots of unity (1.2) in the general formula for the tree
length.

##  3 Length of Steiner tree

Consider a full Steiner tree $\mathbb{T}$ with $n\geq 3$ terminals. Let the
terminal $P_{j}$ be incident to the edge $SP_{j}$ linking it to the adjacent
Steiner point $S$ of the tree. We treat the edge $SP_{j}$ to be oriented from
$S$ to $P_{j}$ and denote by

$\overrightarrow{\ell_{j}}:=\overrightarrow{SP_{j}}/|SP_{j}|$ (3.1)

the direction of the terminal $P_{j}$ in the tree $\mathbb{T}$, i.e. a unit
vector with its starting point attached to the origin. It is known that for
the full Steiner tree, the angle between $\overrightarrow{\ell_{j}}$ and
$\overrightarrow{\ell_{k}}$ is an integer multiple of $\pi/3$. Therefore, all
the terminals can be sorted according to the $6$ possible directions. For our
purpose, we do not need the exact values of these directions, but only their
relative positions.

###### Theorem 3.1

For the full Steiner tree $\mathbb{T}$ with $n\geq 3$ terminals, assign to
each $P_{j}$ the value $U_{j}$ of $6$th root of unity (1.2) according to the
following rules:

  * (a)

$P_{1}\to U_{1}:=\upsilon_{0}=1$;

  * (b)

$P_{j}\to U_{j}:=\upsilon_{k}$ if the angle between
$\overrightarrow{\ell_{1}}$ and $\overrightarrow{\ell_{j}}$ counted clockwise
equals $k\pi/3$.

Then

$\mathfrak{L}(\mathbb{T})=\left|\sum_{j=1}^{n}z_{j}U_{j}\right|\,.$ (3.2)

Proof is by induction on $n$. For $n=3$ the statement holds as it is
demonstrated in Section 2. Assume the result to be true for an arbitrary full
Steiner tree with $n-1\geq 3$ terminals. Next, consider a given full Steiner
tree $\mathbb{T}_{n}$ with $n$ terminals, and number these terminals and
Steiner points somehow with the only requirement that the terminals $P_{n-1}$
and $P_{n}$ should be adjacent to the same Steiner point $S_{n-2}$ which, in
turn, should be adjacent to the Steiner point $S_{n-3}$.

Replace the pair $P_{n-1},P_{n}$ by a point defined by either of alternatives

$Q\mapsto\mathfrak{q}=\left\\{\begin{array}[]{c}\upsilon_{1}z_{n-1}+\upsilon_{5}z_{n},\\\
\upsilon_{5}z_{n-1}+\upsilon_{1}z_{n}\end{array}\right.$ (3.3)

in accordance with its location on the side of the line $P_{n-1}P_{n}$ other
that of $S_{n-2}$ (Fig. 3).

(a)

(b)

Figure 3. Location of the point $Q$.

The new tree with terminals $P_{1},\dots,P_{n-2},Q$ and Steiner points
$S_{1},\dots,S_{n-3}$ is the full Steiner tree (the points $S_{n-3},S_{n-2}$
and $Q$ are collinear). Due to Theorem 1.1, one has:

$|S_{n-3}S_{n-2}|+|P_{n-1}S_{n-2}|+|P_{n}S_{n-2}|=|S_{n-3}S_{n-2}|+|S_{n-2}Q|=|S_{n-3}Q|\,.$

Therefore, the new $(n-1)$-terminal tree $\mathbb{T}_{n-1}$ has its length
equal to $\mathfrak{L}(\mathbb{T}_{n})$. The direction of the terminal $Q$ in
the tree $\mathbb{T}_{n-1}$ (i.e.
$\overrightarrow{\ell}=\overrightarrow{S_{n-3}Q}/|S_{n-3}Q|$) obeys the
assignment rule from the statement of the theorem, i.e. it differs from
$\overrightarrow{\ell_{1}}$ by an integer multiple of $\pi/3$. Based on the
inductive hypothesis, one may conclude that

$\mathfrak{L}(\mathbb{T}_{n-1})=\left|\sum_{j=1}^{n-2}z_{j}U_{j}+\mathfrak{q}U\right|$

where the sequence $U_{1},\dots,U_{n-2},U$ is computed in accordance with the
assignment rule. Assume, for definiteness, that

  * •

$\overrightarrow{\ell}$ coincides with $\overrightarrow{\ell_{1}}$, i.e.
$U=\upsilon_{0}=1$,

  * •

and $\mathfrak{q}$ be defined by the first alternative from (3.3).

Then

$\mathfrak{L}(\mathbb{T}_{n})=\mathfrak{L}(\mathbb{T}_{n-1})=\left|\sum_{j=1}^{n-2}z_{j}U_{j}+\upsilon_{1}z_{n-1}+\upsilon_{5}z_{n}\right|\,.$

In the obtained formula, the assignment rule for terminal directions is kept
fulfilled. The direction $\overrightarrow{\ell}_{n-1}$ is $\pi/3$ clockwise
while that of $\overrightarrow{\ell_{n}}$ is $\pi/3$ counterclockwise from
$\overrightarrow{\ell}$ (Fig. 3 (a)).  $\Box$

###### Corrolary 3.1

In the notation of Theorem 3.1, one has

$\sum_{j=1}^{n}U_{j}=0\,.$

The proof can be extracted from that of the theorem. From this statement and
from the homogeneity of (3.2) with respect to the terminal coordinates, the
following assertion holds

###### Corrolary 3.2

The value (3.2) is invariant under the affine transformation of the complex
plane

$z\mapsto w_{0}z+z_{0}\
,\forall\\{w_{0},z_{0}\\}\subset\mathbb{C},|w_{0}|=1\,.$

In particular, it is possible to choose such a rotation of the plane
$\mathbb{R}^{2}$ around the origin that, in the new coordinates, the
expression $\sum_{j=1}^{n}z_{j}U_{j}$ in (3.2) becomes a positive real number.
In this version, formula (3.2) transforms into the interpretation by Gilbert
and Pollak of Maxwell’s theorem on the equilibrium condition of the pin-
jointed rigid rods holding a prescribed system of external forces [3, 6].
However, generically, to find this rotation for an arbitrary given set
$\mathbb{P}$ is not a trivial task. For its evaluation, direction of at least
one terminal $P_{j}$ in the tree $\mathbb{T}$ should be established, i.e. the
coordinates of the adjacent Steiner point in (3.1). For Example 2.2, this
“good” rotation is given by

$w_{0}=\cos\varphi+\mathbf{i}\sin\varphi\ \quad\mbox{with}\
\varphi:=\pi+\arcsin\left(\frac{1}{3386}\sqrt{8676625-1188486\sqrt{3}}\right)\,.$

To complete the present section, we convert (3.2) into real numbers.

###### Corrolary 3.3

Let $\\{U_{jx}:=\mathfrak{Re}(U_{j}),\
U_{jy}:=\mathfrak{Im}(U_{j})\\}_{j=1}^{n}$. Then

$\\{U_{jx}\\}_{j=1}^{n}\subset\\{1,\pm 1/2\\},\
\\{U_{jy}\\}_{j=1}^{n}\subset\\{0,\pm\sqrt{3}/2\\},\
\\{U_{jx}^{2}+U_{jy}^{2}=1\\}_{j=1}^{n}\ .$

Set

$X:=(x_{1},\dots,x_{n}),\
Y:=(y_{1},\dots,y_{n}),\mathfrak{U}_{X}:=(U_{1x},\dots,U_{nx}),\
\mathfrak{U}_{Y}:=(U_{1y},\dots,U_{ny})\,.$

Then

$\mathfrak{L}(\mathbb{T})=\sqrt{\left(\langle\mathfrak{U}_{X},X\rangle-\langle\mathfrak{U}_{Y},Y\rangle\right)^{2}+\left(\langle\mathfrak{U}_{Y},X\rangle+\langle\mathfrak{U}_{X},Y\rangle\right)^{2}}$

where $\langle\cdot\rangle$ is the standard inner product in $\mathbb{R}^{n}$.

##  4 Examples

We present here two examples illuminating the usage of formula (3.2).

###### Example 4.1

For terminals

$P_{1}=(3,9),\ P_{2}=(1,6),\ P_{3}=(6,3),\ P_{4}=(10,7),\ P_{5}=(8,10)$

the Steiner tree is displayed in Fig. 4 (a). The assignment scheme from
Theorem 3.1 is given in Fig. 4 (b).

$\mathfrak{L}=|z_{1}+z_{5}+\upsilon_{2}z_{4}+\upsilon_{3}z_{3}+\upsilon_{4}z_{2}|=|(z_{1}-z_{3}+z_{5})+\varepsilon_{2}z_{2}+\varepsilon_{1}z_{4}|$
$=\left|-\frac{1+\sqrt{3}}{2}+\mathbf{i}\frac{19+9\sqrt{3}}{2}\right|=\sqrt{152+86\sqrt{3}}\approx
17.348094\,.$

Check. The Steiner points

$\begin{array}[]{c|c|c}S_{1}&S_{2}&S_{3}\\\
=\left(\frac{602}{229}+\frac{391}{1374}\sqrt{3},\frac{2847}{458}+\frac{493}{687}\sqrt{3}\right)&=\left(\frac{1430}{229}-\frac{395}{1374}\sqrt{3},\frac{2901}{458}-\frac{50}{687}\sqrt{3}\right)&=\left(\frac{1755}{229}+\frac{200}{687}\sqrt{3},\frac{1598}{229}+\frac{355}{687}\sqrt{3}\right)\\\
\approx(3.121712,7.459099)&\approx(5.746608,6.20800212)&\approx(8.167992,\,7.873185)\end{array}$

(a)

(b)

Figure 4. (a) The Steiner tree for $5$ terminals and (b) its assignment scheme
(Example 4.1).

###### Example 4.2

For terminals

$P_{1}=(2,-2\sqrt{3}),P_{2}=(8,0),P_{3}=(4,4\sqrt{3}),P_{4}=(-8/\sqrt{3},8),P_{5}=(-10,0),P_{6}=(-2,-2\sqrt{3})$

the Steiner tree is displayed in Fig. 5 (a). The assignment scheme is given in
Fig. 5 (b)

$\mathfrak{L}=|z_{1}+\upsilon_{1}z_{5}+\upsilon_{2}z_{4}+\upsilon_{3}z_{3}+\upsilon_{4}z_{2}+\upsilon_{5}z_{6}|=|(z_{1}-z_{3})+\varepsilon_{1}(z_{4}-z_{6})+\varepsilon_{2}(z_{2}-z_{5})|$
$=|(-15-8/\sqrt{3})-\mathbf{i}(8+15\sqrt{3})|=30+15/\sqrt{3}\approx
39.237604.$

Check. The Steiner points:

$S_{1}=(4,0),\ S_{2}=(2,2\sqrt{3}),S_{3}=(2,-2\sqrt{3}),\ S_{4}=(-4,0)\,.$

(a)

(b)

Figure 5. (a) The Steiner tree for $6$ terminals and (b) its assignment scheme
(Example 4.2).

##  5 Extension to the Weber problem

We now turn to the Weber problem mentioned in Introduction. In the present
section we assume the fulfillment of the conditions for the existence of the
networks in the prescribed topologies (some of them are presented in [9, 10]).
In particular, we suppose all the involved geometric constructions to be
feasible. Hereinafter all the weights $m_{j},m,\dots$ are positive real
numbers and the angles denoted by Greek letters $\alpha,\beta,\gamma$ are
assumed to be within the interval $[0,\pi]$.

We start with the three terminal problem (also known as the generalized
Fermat-Torricelli problem) as that of finding the facility $W$ providing

$\min_{W\in\mathbb{R}^{2}}\sum_{j=1}^{3}m_{j}|WP_{j}|\,.$ (5.1)

A geometric solution to the problem is given in the paper by Launhardt [4, 5];
it is just a counterpart of the Torricelli-Simpson construction for the
Steiner problem from Section 2.

###### Example 5.1

Find the optimal position of the facility $W$ to the problem (5.1) where

$\left\\{\begin{array}[]{c|c|c}P_{1}=(2,6)&P_{2}=(1,1)&P_{3}=(5,1)\\\
m_{1}=2&m_{2}=3&m_{3}=4\end{array}\right\\}.$

Solution. First find the point $Q_{1}$ lying on the opposite side of the line
$P_{1}P_{2}$ with respect to the point $P_{3}$ and such that

$|P_{1}Q_{1}|=\frac{m_{2}}{m_{3}}|P_{1}P_{2}|,\
|P_{2}Q_{1}|=\frac{m_{1}}{m_{3}}|P_{1}P_{2}|\,.$ (5.2)

These relations mean that the triangle $P_{1}P_{2}Q_{1}$ is similar to the so-
called weight triangle of the problem, i.e. the triangle containing the edges
formally coinciding with the values of the weights $m_{1},m_{2},m_{3}$. We
will further denote the angles of the weight triangle by
$\alpha_{1},\alpha_{2},\alpha_{3}$ as shown in Fig. 6 (a). Next, draw the
circle $C_{1}$ circumscribing $P_{1}P_{2}Q_{1}$. Finally draw the line through
$Q_{1}$ and $P_{3}$. The intersection point of this line with $C_{1}$ is the
position of the optimal facility $W$. It possesses the property that
directions of the terminals, i.e.
$\overrightarrow{\ell_{j}}:=\overrightarrow{WP_{j}}/|WP_{j}|$, make the
following angles (Fig. 6 (b))

$\widehat{\overrightarrow{\ell_{1}},\overrightarrow{\ell_{2}}}=\pi-\alpha_{3},\
\widehat{\overrightarrow{\ell_{1}},\overrightarrow{\ell_{3}}}=\pi-\alpha_{2},\
\widehat{\overrightarrow{\ell_{2}},\overrightarrow{\ell_{3}}}=\pi-\alpha_{1}\,.$

The corresponding (minimal) cost equals $m_{3}|P_{3}Q_{1}|$ (consequence of
(5.2) and Theorem 1.1).  $\Box$

(a)

(b)

Figure 6. (a) Weight triangle and (b) Weber point location (Example 5.1).

We now rewrite the analytics similar to that from Section 2. The coordinates
of the point $Q_{1}$ are as follows [9]

$\displaystyle Q_{1}$ $\displaystyle=$
$\displaystyle\Bigg{(}\frac{1}{2}(x_{1}+x_{2})+\frac{(m_{1}^{2}-m_{2}^{2})(x_{1}-x_{2})-\sqrt{\mathbf{k}}(y_{1}-y_{2})}{2m_{3}^{2}},$
(5.3) $\displaystyle\hskip
56.9055pt\frac{1}{2}(y_{1}+y_{2})+\frac{(m_{1}^{2}-m_{2}^{2})(y_{1}-y_{2})+\sqrt{\mathbf{k}}(x_{1}-x_{2})}{2m_{3}^{2}}\Bigg{)}\,,$

or, equivalently, in the complex plane:

$Q_{1}\mapsto\mathfrak{q}_{1}=\frac{1}{2m_{3}^{2}}\left[(m_{3}^{2}+m_{1}^{2}-m_{2}^{2}+\mathbf{i}\sqrt{\mathbf{k}})z_{1}+(m_{3}^{2}-m_{1}^{2}+m_{2}^{2}-\mathbf{i}\sqrt{\mathbf{k}})z_{2}\right]$
(5.4)

Here

$\mathbf{k}:=(m_{1}+m_{2}+m_{3})(-m_{1}+m_{2}+m_{3})(m_{1}-m_{2}+m_{3})(m_{1}+m_{2}-m_{3})\,,$
(5.5)

and, due to Heron’s formula, $\sqrt{\mathbf{k}}/4$ equals the square of the
weight triangle. As for the angles of this triangle, by cosine theorem, one
gets

$\frac{m_{3}^{2}+m_{1}^{2}-m_{2}^{2}}{2m_{3}m_{1}}=\cos\alpha_{2},\
\frac{m_{3}^{2}-m_{1}^{2}+m_{2}^{2}}{2m_{3}m_{2}}=\cos\alpha_{1},$ (5.6)

while222We recall the assumption made at the beginning of the present section:
all the angles denoted by Greek letters are assumed to lie within $[0,\pi]$.
Therefore all the sine values for such angles are nonnegative.

$\frac{\sqrt{\mathbf{k}}}{2m_{3}m_{1}}=\sin\alpha_{2},\
\frac{\sqrt{\mathbf{k}}}{2m_{3}m_{2}}=\sin\alpha_{1}\,.$ (5.7)

Finally, one has

$\mathfrak{q}_{1}=\frac{1}{m_{3}}\left[m_{1}(\cos\alpha_{2}+\mathbf{i}\sin\alpha_{2})z_{1}+m_{2}(\cos\alpha_{1}-\mathbf{i}\sin\alpha_{1})z_{2}\right]$

and

$\mathfrak{C}=m_{3}|P_{3}Q_{1}|=|m_{3}z_{3}-m_{3}\mathfrak{q}_{1}|$
$=|m_{3}z_{3}+m_{2}z_{2}\left\\{\cos(\pi-\alpha_{1})+\mathbf{i}\sin(\pi-\alpha_{1})\right\\}+m_{1}z_{1}\left\\{\cos(2\pi-\alpha_{1}-\alpha_{3})+\mathbf{i}\sin(2\pi-\alpha_{1}-\alpha_{3})\right\\}|\,.$

The obtained formula is the true counterpart of the formula (2.2) for the
length of the full Steiner tree for $3$ terminals.

Let us now turn to the bifacility Weber problem for $4$ terminals
$\\{P_{j}\\}_{j=1}^{4}$ as that of finding the points $W_{1}$ and $W_{2}$
which yield

$\displaystyle\displaystyle\min_{\\{W_{1},W_{2}\\}\subset\mathbb{R}^{2}}F(W_{1},W_{2})\quad\mbox{
where }$ $\displaystyle
F(W_{1},W_{2})=m_{1}|W_{1}P_{1}|+m_{2}|W_{1}P_{2}|+m_{3}|W_{2}P_{3}|+m_{4}|W_{2}P_{4}|+m|W_{1}W_{2}|\,.$
(5.8)

We first recall the geometric solution outlined by Georg Pick in the
Mathematical Appendix of Weber’s book [11]. We illustrate this algorithm with
the following example.

###### Example 5.2

Find the optimal position for the facilities $W_{1}$ and $W_{2}$ for the
problem (5.8) where

$\left\\{\begin{array}[]{c|c|c|c|}P_{1}=(1,5)&P_{2}=(2,1)&P_{3}=(7,2)&P_{4}=(6,7)\\\
m_{1}=3&m_{2}=2&m_{3}=3&m_{4}=4\end{array}\ m=4\right\\}\,.$

Solution. First find the point $Q_{1}$ lying on the opposite side of the line
$P_{1}P_{2}$ with respect to the point $P_{3}$ and such that

$|P_{1}Q_{1}|=\frac{m_{2}}{m}|P_{1}P_{2}|,\
|P_{2}Q_{1}|=\frac{m_{1}}{m}|P_{1}P_{2}|\,.$ (5.9)

The exact coordinates of this point are given by (5.3) where the substitution
$m_{3}\to m$ is made. Find then the second point $Q_{2}$ with the similar
property with respect to the points $P_{3}$ and $P_{4}$ (Fig. 7):

$|P_{3}Q_{2}|=\frac{m_{4}}{m}|P_{3}P_{4}|,\
|P_{4}Q_{2}|=\frac{m_{3}}{m}|P_{3}P_{4}|\,.$

Figure 7. Construction of the points $Q_{1}$ and $Q_{2}$.

It is evident that triangle $P_{1}P_{2}Q_{1}$ is similar to the weight
triangle with the edges $m,m_{1},m_{2}$, while $P_{3}P_{4}Q_{2}$ is similar to
the weight triangle with the edges $m,m_{3},m_{4}$ (Fig. 8) Next, draw the
circle $C_{1}$ circumscribing $P_{1}P_{2}Q_{1}$ and $C_{2}$ circumscribing
$P_{3}P_{4}Q_{2}$.

Figure 8. Weight triangles for the bifacility Weber problem

Finally draw the line through $Q_{1}$ and $Q_{2}$ (Fig. 9).

Figure 9. Pick’s construction for the Weber network (Example 5.2).

The intersection points of this line with $C_{1}$ and $C_{2}$ are the position
of the optimal facilities $W_{1}$ and $W_{2}$ for the network with the
corresponding (minimal) cost equal to $\mathfrak{C}=m|Q_{1}Q_{2}|$.

Remark. Pick’s solution can be interpreted as a counterpart of the algorithm
worked out by Gergonne in 1810 (and rediscovered by Melzak in 1961) for
solution of the SMT problem for four terminals. It should be noted that Pick
did not provide any reasons of validity for his construction (we also failed
to find any references to Pick’s solution in subsequent papers on the
subject). In [9, 10] we have verified the accuracy of Pick’s treatment via an
analytical representation of the coordinates of the optimal facilities
$W_{1},W_{2}$ and substitution them into the gradient of the function (5.8).
Some other qualitative conclusions have been deduced, such as, for instance,
that, in the case of existence, the bifacility network is less costly than any
unifacility one. All the computations for the examples below can be found in
the cited sources.

Thus, the coordinates for the facilities from the previous example are as
follows

$\displaystyle W_{1}$ $\displaystyle=$
$\displaystyle\Bigg{(}\frac{\scriptstyle{2266800+772027\sqrt{15}+453552\sqrt{33}+246177\sqrt{55}}}{\scriptstyle{48\left(22049+2085\sqrt{15}+945\sqrt{33}+2559\sqrt{55}\right)}},\frac{\scriptstyle{1379951+201984\sqrt{15}+97279\sqrt{33}+154368\sqrt{55}}}{\scriptstyle{16\left(22049+2085\sqrt{15}+945\sqrt{33}+2559\sqrt{55}\right)}}\Bigg{)}$
$\displaystyle\approx(3.701271,4.430843)\,;$ $\displaystyle W_{2}$
$\displaystyle=$
$\displaystyle\Bigg{(}\frac{\scriptstyle{188467345+18613485\sqrt{15}+7149825\sqrt{33}+20949207\sqrt{55}}}{\scriptstyle{1760\left(22049+2085\sqrt{15}+945\sqrt{33}+2559\sqrt{55}\right)}},\frac{\scriptstyle{188346565+19265895\sqrt{15}+20525157\sqrt{55}+7187445\
\sqrt{11}}}{\scriptstyle{1760\left(22049+2085\sqrt{15}+945\sqrt{33}+2559\sqrt{55}\right)}}\Bigg{)}$
$\displaystyle\approx(4.761622,4.756175)$

and the cost of the network

$\mathfrak{C}=\frac{1}{8}\sqrt{44098+4170\sqrt{15}+5118\sqrt{55}+1890\sqrt{33}}\approx
41.280608\,.$ (5.10)

Let us deduce the general formula for $\mathfrak{C}=m|Q_{1}Q_{2}|$ for the
networks which are topologically equivalent to the one dealt with in Example
5.2. The coordinates of the point $Q_{1}$ are determined by (5.4) where
substitution $m_{3}\to m$ is made. The coordinates of $Q_{2}$ are also
obtained from (5.4) by replacement $(m_{1},m_{2},m_{3})\to(m_{3},m_{4},m)$.
Thus

$\displaystyle\mathfrak{C}=m|Q_{1}Q_{2}|=m|\mathfrak{q}_{1}-\mathfrak{q}_{2}|$
$\displaystyle=$
$\displaystyle\big{|}m_{1}z_{1}(\cos\alpha_{2}+\mathbf{i}\sin\alpha_{2})+m_{2}z_{2}(\cos\alpha_{1}-\mathbf{i}\sin\alpha_{1})$
(5.11) $\displaystyle-
m_{3}z_{3}(\cos\alpha_{4}+\mathbf{i}\sin\alpha_{4})-m_{4}z_{4}(\cos\alpha_{3}-\mathbf{i}\sin\alpha_{3})\big{|}\,.$

Here $\alpha_{1},\alpha_{2}$ are the angles of the first weight triangle of
the problem, while $\alpha_{3},\alpha_{4}$ are those of the second (Fig. 8).
Cosine and sine functions of these angles are computed similar to (5.6) and
(5.7). For the network of Example 5.2 one gets the cost value

$\mathfrak{C}=\left|3(1+\mathbf{i}5)\left(\frac{7}{8}+\frac{1}{24}\mathbf{i}\sqrt{135}\right)+2(2+\mathbf{i})\left(\frac{11}{16}-\frac{1}{16}\mathbf{i}\sqrt{135}\right)-\dots\right|$
$=\left|-\frac{79}{4}-\frac{1}{2}\sqrt{135}-\frac{5}{8}\sqrt{495}-\mathbf{i}\left(\frac{63}{8}+\frac{1}{8}\sqrt{135}+\frac{1}{8}\sqrt{495}\right)\right|$

which coincides with (5.10).

(a)

(b)

Figure 10. Angles in the bifacility Weber network.

Let us rewrite (5.11) uniformizing representation of the arguments of
trigonometric functions:

$\displaystyle\mathfrak{C}$ $\displaystyle=$
$\displaystyle\big{|}m_{1}(\cos\alpha_{2}+\mathbf{i}\sin\alpha_{2})z_{1}+m_{4}z_{4}(\cos(\pi-\alpha_{3})+\mathbf{i}\sin(\pi-\alpha_{3}))$
(5.12)
$\displaystyle+m_{3}z_{3}(\cos(\pi+\alpha_{4})+\mathbf{i}\sin(\pi+\alpha_{4}))+m_{2}z_{2}(\cos(2\pi-\alpha_{1})+\mathbf{i}\sin(2\pi-\alpha_{1}))\big{|}\,.$

Here one can watch the generation rule for these arguments: they correspond to
the direction angles of the terminals $P_{j}$ in the network if we count them
clockwise starting from the line $W_{1}W_{2}$ (Fig. 10).

###### Theorem 5.1

Let the optimal Weber network $\mathbb{T}$ with $n\geq 3$ terminals
$\\{P_{j}\\}_{j=1}^{n}$ and $n-2$ facilities $\\{W_{k}\\}_{k=1}^{n-2}$ be
topologically equivalent to a full Steiner tree, i.e. each terminal from
$\mathbb{T}$ is of the degree $1$ while each facility is of the degree $3$.
Let $\overrightarrow{\ell_{j}}=(\cos\beta_{j},\sin\beta_{j})$ be the direction
of the terminal $P_{j}$ in the network counted clockwise starting from some
particular vector. The cost of the network $\mathbb{T}$ in the prescribed
topology is given by the formula

$\mathfrak{C}(\mathbb{T})=\left|\sum_{j=1}^{n}m_{j}z_{j}(\cos\beta_{j}+\mathbf{i}\sin\beta_{j})\right|\,.$
(5.13)

The results of Corollaries 3.1 and 3.2 from Section 3 can evidently be
upgraded to the “weighted” version. For instance, one has

$\sum_{j=1}^{n}m_{j}(\cos\beta_{j}+\mathbf{i}\sin\beta_{j})=0\,.$ (5.14)

To justify the result of the theorem, we suggest here some _plausible
reasonings_.

###### Example 5.3

Find the cost of the optimal network that minimize the function

$m_{1}|P_{1}W_{1}|+m_{2}|P_{2}W_{1}|+m_{3}|P_{3}W_{2}|+m_{4}|P_{4}W_{2}|+m_{5}|P_{5}W_{3}|+\widetilde{m}_{1,3}|W_{1}W_{3}|+\widetilde{m}_{2,3}|W_{2}W_{3}|$
(5.15)

for the following configuration:

$\left\\{\begin{array}[]{c|c|c|c|c|c}P_{1}=(1,6)&P_{2}=(5,1)&P_{3}=(11,1)&P_{4}=(15,3)&P_{5}=(7,11)&\widetilde{m}_{1,3}=10\\\
m_{1}=10&m_{2}=9&m_{3}=8&m_{4}=7&m_{5}=13&\widetilde{m}_{2,3}=12\end{array}\right\\}\,.$

Solution. Existence of the optimal network and coordinates of the
corresponding facilities $W_{1},\,W_{2},\,W_{3}$ are established in [9]. We
will discuss here only the minimal cost calculation.

Figure 11. Weber network construction for five terminals (Example 5.3).

Replace a pair of the terminals $P_{1}$ and $P_{2}$ by the _phantom terminal_
$Q_{1}$ defined by the formula (5.4) where the substitution
$m_{3}\to\widetilde{m}_{1,3}$ is made, and assign this weight to $Q_{1}$. The
minimal cost of the new $\left\\{4\right.$-terminals,
$2$-facilities$\left.\right\\}$-network minimizing the function

$\widetilde{m}_{1,3}|Q_{1}W_{3}|+m_{3}|P_{3}W_{2}|+m_{4}|P_{4}W_{2}|+m_{5}|P_{5}W_{3}|$

equals the minimal cost of the original network (and facilities $W_{2},W_{3}$
in both optimal networks coincide). By (5.12),

$\displaystyle\mathfrak{C}$ $\displaystyle=$
$\displaystyle\big{|}\widetilde{m}_{1,3}\mathfrak{q}_{1}(\cos(2\pi-\gamma_{1})+\mathbf{i}\sin(2\pi-\gamma_{1}))+m_{5}z_{5}(\cos\gamma_{2}+\mathbf{i}\sin\gamma_{2}))$
(5.16)
$\displaystyle+m_{4}z_{4}(\cos(\pi-\gamma_{3})+\mathbf{i}\sin(\pi-\gamma_{3}))+m_{3}z_{3}(\cos(\pi+\gamma_{4})+\mathbf{i}\sin(\pi+\gamma_{4}))\big{|}$

with the angles $\\{\gamma_{j}\\}_{j=1}^{4}$ displayed in Fig. 12 (a).

(a)

(b)

Figure 12. Angles of the trifacility Weber network (Example 5.3).

One has

$\cos\gamma_{1}=\frac{\widetilde{m}_{1,3}^{2}+\widetilde{m}_{2,3}^{2}-m_{5}^{2}}{2\widetilde{m}_{1,3}\widetilde{m}_{2,3}},\
\cos\gamma_{2}=\frac{\widetilde{m}_{2,3}^{2}+m_{5}^{2}-\widetilde{m}_{1,3}^{2}}{2m_{5}\widetilde{m}_{2,3}},$
$\cos\gamma_{3}=\frac{m_{4}^{2}+\widetilde{m}_{2,3}^{2}-m_{4}^{2}}{2\widetilde{m}_{2,3}m_{4}},\
\cos\gamma_{4}=\frac{m_{3}^{2}+\widetilde{m}_{2,3}^{2}-m_{3}^{2}}{2\widetilde{m}_{2,3}m_{3}}$

and the expressions for the corresponding sine values are represented, using
the involved weights, similarly to (5.7). Next we replace $\mathfrak{q}_{1}$
by the original terminals $z_{1}$ and $z_{2}$ via (5.4)
($m_{3}\to\widetilde{m}_{1,3}$):

$\mathfrak{q}_{1}=\frac{1}{\widetilde{m}_{1,3}}\left[m_{1}(\cos\alpha_{2}+\mathbf{i}\sin\alpha_{2})+m_{2}(\cos(2\pi-\alpha_{1})+\mathbf{i}\sin(2\pi-\alpha_{1}))\right]$

with the angles $\alpha_{1},\alpha_{2}$ displayed in Fig. 12 (b) and with

$\cos\alpha_{1}=\frac{\widetilde{m}_{1,3}^{2}+m_{2}^{2}-m_{1}^{2}}{2m_{2}\widetilde{m}_{1,3}},\
\cos\alpha_{2}=\frac{\widetilde{m}_{1,3}^{2}+m_{1}^{2}-m_{2}^{2}}{2m_{1}\widetilde{m}_{1,3}}\,.$

Finally,

$\mathfrak{C}=\big{|}m_{1}z_{1}(\cos(\alpha_{2}-\gamma_{1})+\mathbf{i}\sin(\alpha_{2}-\gamma_{1}))+m_{2}z_{2}(\cos(2\pi-\alpha_{1}-\gamma_{1})+\mathbf{i}\sin(2\pi-\alpha_{1}-\gamma_{1}))+\dots\big{|}$

with the rest of the terms coinciding with those from (5.16). The terminal
direction assignment rule from Theorem 5.1 is fulfilled: these angles are
counted starting from the line $W_{2}W_{3}$. Substitution of the expressions
for sine and cosine functions in terms of all the involved weights yields the
cost representation by radicals. For our particular example,

$\displaystyle\mathfrak{C}$ $\displaystyle=$
$\displaystyle\Big{|}-\frac{1331}{16}-\frac{281}{64}\sqrt{231}-\frac{45}{64}\sqrt{319}-\frac{3}{4}\sqrt{143}-\frac{9}{80}\sqrt{319}\sqrt{231}$
$\displaystyle+\mathbf{i}\left(\frac{5587}{64}+\frac{219}{80}\sqrt{231}-\frac{9}{16}\sqrt{319}+\frac{3}{2}\sqrt{143}+\frac{9}{64}\sqrt{319}\sqrt{231}\right)\Big{|}\approx
267.229644\,.$

$\Box$

The result of the theorem remains valid even for the networks without the
imposed restriction on their topologies. For instance, the unifacility Weber
problem (generalized Fermat-Torricelli problem) for $n\geq 4$ terminals as
that of finding

$\min_{W\in\mathbb{R}^{2}}\sum_{j=1}^{n}m_{j}|P_{j}W|\,,$ (5.17)

in the case of existence of solution
$W_{\ast}=(x_{\ast},y_{\ast})\not\in\\{P_{j}\\}_{j=1}^{n}$, has the value
(5.13) equal to

$\left|\sum_{j=1}^{n}m_{j}z_{j}(\cos\beta_{j}+\mathbf{i}\sin\beta_{j})\right|\stackrel{{\scriptstyle(\ref{WcostSum})}}{{=}}\left|\sum_{j=1}^{n}m_{j}(z_{j}-z_{\ast})(\cos\beta_{j}+\mathbf{i}\sin\beta_{j})\right|,\quad
z_{\ast}:=x_{\ast}+\mathbf{i}y_{\ast}\,.$

If the direction $(\cos\beta_{j},\sin\beta_{j})$ of the terminal $P_{j}$ is
counted starting from the $x$-axis, then $2\pi-\beta_{j}$ is just the argument
of the number $z_{j}-z_{\ast}$.

However, the posed restriction on the network topology is significant for the
constructive computation of the directions of the terminals in the network.
Indeed, in the case of networks possessing the claimed property, formulas for
the direction of any terminal can be represented by radicals via the weights
of the problem provided that these directions are counted starting from any
edge of the optimal network. Note that the coordinates of facilities are not
required for this aim, the only assurance of the existence of the network in
the prescribed topology matters.

This is not the case for the networks with facilities of the degree higher
than $3$. Even the problem (5.17) cannot be resolved by radicals for general
case of $n=4$ terminals. For instance, when the weight $m$ from Example 5.2
increases continuously from the initial value $m=4$, the facilities $W_{1}$
and $W_{2}$ of the corresponding optimal bifacility networks tend to a
collision point $W_{\ast}$ at the value $m=m_{\ast}$. The point $W_{\ast}$ is
the solution to the unifacility Weber problem (5.17) with $n=4$. Coordinates
of $W_{\ast}$ satisfy the $10$th degree algebraic equations over $\mathbb{Z}$;
so do the critical value $m_{\ast}\approx 4.326092$ [9].

##  6 Conclusions

1. Though the deduced formulas for the length or cost of optimal networks do not require the coordinates of any network facility, it is possible to generate them in the above exploited complexification ideology. For instance, in the complex plane, the Steiner point of the triangle $P_{1}P_{2}P_{3}$ (in the case of its existence and provided that the triangle vertices are numbered counterclockwise) is given as

$\frac{\mathbf{i}}{\sqrt{3}}\left(\varepsilon_{2}z_{2}-\varepsilon_{1}z_{1}+(\overline{z_{1}}-\overline{z_{2}})\mathcal{L}/\overline{\mathcal{L}}\right)$

where $\mathcal{L}:=z_{3}+\varepsilon_{2}z_{1}+\varepsilon_{1}z_{2}$ is the
expression from formula (2.2), i.e. $|\mathcal{L}|$ is the length of the full
Steiner tree. For the terminals of Example 2.1, this formula yields

$\frac{454+250\sqrt{3}+\mathbf{i}(262+150\sqrt{3})}{112+60\sqrt{3}}=\frac{731+95\sqrt{3}}{1703}+\mathbf{i}\frac{293+135\sqrt{3}}{1703}\approx
4.108004+\mathbf{i}\,2.416637\,.$

2. It looks challenging to find the minimum value for

$\left|\sum_{j=1}^{n}z_{j}\widetilde{U}_{j}\right|$

in the set of all vectors
$(\widetilde{U}_{1},\dots,\widetilde{U}_{n})\in\mathbb{C}^{n}$ such that

$\left\\{\widetilde{U}_{j}^{6}=1\right\\}_{j=1}^{n}\ ,\
\sum_{j=1}^{n}\widetilde{U_{j}}=0\,.$

It resembles a knapsack problem.

## References

  * [1] Booth R.S. Analytic formulas for full Steiner trees. _Discr. Comput. Geom/_ 1991\. V. 6, No 1, pp.69-82
  * [2] Brazil M., Graham R.I., Thomas D.A., Zachariasen M. On the history of the Euclidean Steiner tree problem. _Arch. Hist. Exact Sci._ 2014, V. 68, P.327–354
  * [3] Gilbert E.N., Pollak H.O. Steiner minimal trees. _SIAM J. Appl. Math._ 1968\. V. 16, pp. 1–29
  * [4] Dingeldey F. Sammlung von Aufgaben zur Anwendung der Differenzial- und Integralrechnung. Zweiter Teil. Aufgaben zur Anwendung der Integralrechnung. Teubner. Leipzig. 1923
  * [5] Launhardt W. Kommercielle Tracirung der Verkehrswege. Zeitschrift f. Architekten u.Ingenieur-Vereinis im Königreich Hannover. 1872. V. 18, pp. 516-534
  * [6] Maxwell J.C. On the calculation of the equilibrium and stiffness of frames. Philos. Mag., 1864, V. 27 , pp.294-299.
  * [7] Pollak H.O. Some remarks on the Steiner problem. _J. Combin. Theory Ser._ A. 1978. V. 24, pp.278–295
  * [8] Uteshev A.Yu. Some analytics for Steiner minimal tree problem for four terminals. 2015. arXiv:1505.03564 [math.CG]
  * [9] Uteshev A.Yu., Semenova E.A. Geometry and analytics of the multifacility Weber problem. 2020. arXiv:1912.12973v2 [math.CG]
  * [10] Uteshev A.Yu., Semenova E.A. Analytics of the multifacility Weber problem. _LNCS_ , Springer, 2020, V.12251, pp. 395–411.
  * [11] Weber A. Über den Standort der Industrien. Bd. 1: Reine Theorie des Standorts. 1909. Tübingen. English translation: Friedrich C.J. (Ed.). Alfred Weber’s theory of location of industries. Chicago: The University of Chicago Press, 1929.
  * [12] Weng J.F. Steiner trees, coordinate systems and NP-hardness. In _Advances in Steiner Trees._ D.-Z.Du, J.M.Smith, J.H.Rubinstein (eds.) Kluwer. Dordrecht, pp.63-80