1
$\begingroup$

I am looking for a reference proving the existence of the minimal Steiner tree in the Euclidean Steiner tree problem:

Given N points in the d-dimensional Euclidean space, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments (it may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree called the Steiner minimal tree).

$\endgroup$
1
  • 2
    $\begingroup$ If you fix the number $K$ of added Steiner nodes, then the existence of an optimal position for these added nodes follows from standard optimization arguments (since sending at least one of these nodes to infinity makes the total length arbitrarily large). So the existence of a minimal Steiner tree stems from an a priori bound on $K$. Standard geometric arguments seem to imply that $0 \leq K \leq N-2$, even in $\mathbb{R}^d$ (see e.g. Smith, "How to find Steiner minimal trees in Euclidean d-space." Algorithmica 1992). However, uniqueness doesn't always hold. $\endgroup$ Commented Feb 27, 2023 at 14:06

1 Answer 1

3
$\begingroup$

The existence theorem for a finite number of points is more-or-less obvious, so classical sources do not give it as a statement. But you can extract them from the very classical paper Gilbert E. N., Pollak H. O. Steiner minimal trees //SIAM Journal on Applied Mathematics. – 1968. – Т. 16. – №. 1. – С. 1-29, or from any paper with an algorithm.

If you need just a statement, then I know only the paper Paolini E., Stepanov E. Existence and regularity results for the Steiner problem //Calculus of Variations and Partial Differential Equations. – 2013. – Т. 46. – №. 3-4. – С. 837-860, which contains an existance theorem in a very general setting (infinite number of vertices, mild conditions on a metric space).

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.