# Why are there only finitely many Steiner points?

Discussion in 'Math Research' started by tchow, Jun 24, 2006.

1. ### tchowGuest

A few years back, I posted here asking why the maximum number of
Steiner points in a minimum (Euclidean) Steiner tree is n - 2, where n
is the number of initial points. Gerry Myerson gave a helpful response,
pointing me to the work of Melzak. However, I was just looking at this
again, and one point that was never quite settled to my satisfaction
was the question of why the maximum number of Steiner points is finite.
(I buy that *if* the number of points is finite, then it's at most n - 2.)

tchow, Jun 24, 2006

2. ### Gerry MyersonGuest

Steiner points have degree 3. I don't know much about infinite trees;
is it possible to have one with all but finitely many of its vertices
of degree 3?

Gerry Myerson, Jun 26, 2006

3. ### klaus hoffmannGuest

ist the finiteness unconditional, i.E. for bounded and unbounded pointsets?
regards
Klaus

klaus hoffmann, Jun 26, 2006
4. ### klaus hoffmannGuest

If the shortest tree has mostly angles >120 degrees then there is no need for
many steiner points. This is the only explanation I can think of - perhaps we
get mostly those configurations if we consider the limit to an infinite pointset.
I'm very curious to see the reference for the finiteness
Klaus Hoffmann

klaus hoffmann, Jun 26, 2006
5. ### tchowGuest

In principle, yes; e.g., take the tree whose vertices *all* have degree 3.

"Obviously," such fractal monstrosities are ridiculous in the context of
Euclidean Steiner trees, but it seems annoying to prove.

tchow, Jun 27, 2006
6. ### klaus hoffmannGuest

There are two questions:
1. The finiteness of the steiner-candidate set if n is finite
2. The finiteness of the steiner set if n is infinite

1.
Consider a fixed set of n terminal points. Build a connecting tree with n-2
internal points [1]. There are f(n)=(2n-4)!/2^(n-2)/(n-2)! nonisomorphic trees;
for each the minimum length, and the set of nonterminal points is unique [2].
There are at most
(n-2) f(n) interior points.
q.e.d.

[1] the degree of a (interior=) Steiner point is 3.
[2] if the tree topology is fixed, the optimization w.r.t. length is convex; in
general innterior points will coincide.

2. infinite n
assuming we have some useful definition of total tree length
a) Consider (x_n,y_n)=(4*n,0). There is no need for steiner points.

b) attach the unit square to each of the points in a). "obviously" we need
steiner points in each square, so seem to need an infinite number of s.p. .

Regards
Klaus

klaus hoffmann, Jun 28, 2006
7. ### tchowGuest

<1. The finiteness of the steiner-candidate set if n is finite
[...]
<Consider a fixed set of n terminal points. Build a connecting tree with n-2
<internal points [1]. There are f(n)=(2n-4)!/2^(n-2)/(n-2)!
<nonisomorphic trees;
<for each the minimum length, and the set of nonterminal points is unique [2].
<There are at most
<(n-2) f(n) interior points.
<q.e.d.
<
<[1] the degree of a (interior=) Steiner point is 3.
<[2] if the tree topology is fixed, the optimization w.r.t. length is
<convex; in general innterior points will coincide.

I don't follow how this rules out infinite trees. All it seems to show
that *if* the number of points is finite, then you can get a bound on them.

tchow, Jun 30, 2006
8. ### tchowGuest

I managed to come up with enough of an argument to satisfy myself.

The usual definition of a Euclidean Steiner tree is a tree of minimum
Euclidean distance that connects a given set of points in the plane.
The tree is allowed to contain vertices (Steiner points) other than
the original set of points. My question was, if the initial set of
points is finite, must the set of Steiner points be finite?

I'm pretty comfortable now with the following approach, which more or
less "defines away" any potential problems. We simply insist that for
any pair of initial points to be "connected" by the tree, it must be the
case that there is a *finite* sequence of Steiner points, each adjacent
to its neighbors in the sequence, that joins the two.

Given this, we can restrict our attention to the case of finitely many
Steiner points as follows. Suppose we have an infinite Steiner tree.
For each pair of initial points there is some path connecting them.
As we range over all pairs of initial points, these paths will involve
at most finitely many vertices in all. This finite set of vertices will
induce a finite subtree of the total tree. Throwing away the rest of
the tree cannot disconnect the tree or increase its total length. Thus
it suffices to consider the case of finitely many Steiner points.

The loophole in this argument is that perhaps there is some intelligible
sense in which two initial points are "connected" by means of infinitely
many Steiner points, other than by a finite sequence of them as stipulated
above. However, I guess I don't mind excluding such possibilities by fiat.

tchow, Jul 2, 2006