Author 
Message 
tchow@lsa.umich.edu science forum addict
Joined: 15 Sep 2005
Posts: 53

Posted: Sat Jun 24, 2006 5:54 pm Post subject:
Why are there only finitely many Steiner points?



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.)

Tim Chow tchowatalumdotmitdotedu
The range of our projectileseven ... the artilleryhowever great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. Galileo, Dialogues Concerning Two New Sciences 

Back to top 


Gerry Myerson science forum Guru
Joined: 28 Apr 2005
Posts: 871

Posted: Mon Jun 26, 2006 12:26 am Post subject:
Re: Why are there only finitely many Steiner points?



In article <449d7c41$0$580$b45e6eb0@senatorbedfellow.mit.edu>,
tchow@lsa.umich.edu wrote:
Quote:  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.)

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 (gerry@maths.mq.edi.ai) (i > u for email) 

Back to top 


klaus hoffmann science forum beginner
Joined: 31 Jan 2006
Posts: 12

Posted: Mon Jun 26, 2006 5:56 am Post subject:
Re: Why are there only finitely many Steiner points?



tchow@lsa.umich.edu wrote:
Quote:  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.)

ist the finiteness unconditional, i.E. for bounded and unbounded pointsets?
Could yo give a link?
regards
Klaus 

Back to top 


klaus hoffmann science forum beginner
Joined: 31 Jan 2006
Posts: 12

Posted: Mon Jun 26, 2006 7:00 pm Post subject:
Re: Why are there only finitely many Steiner points?



Gerry Myerson wrote:
Quote:  In article <449d7c41$0$580$b45e6eb0@senatorbedfellow.mit.edu>,
tchow@lsa.umich.edu wrote:
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.)
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?

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 

Back to top 


tchow@lsa.umich.edu science forum addict
Joined: 15 Sep 2005
Posts: 53

Posted: Tue Jun 27, 2006 8:03 pm Post subject:
Re: Why are there only finitely many Steiner points?



In article <gerryB7C636.10264226062006@sunb.ocs.mq.edu.au>,
Gerry Myerson <gerry@maths.mq.edi.ai.i2u4email> wrote:
Quote:  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?

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.

Tim Chow tchowatalumdotmitdotedu
The range of our projectileseven ... the artilleryhowever great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. Galileo, Dialogues Concerning Two New Sciences 

Back to top 


klaus hoffmann science forum beginner
Joined: 31 Jan 2006
Posts: 12

Posted: Wed Jun 28, 2006 5:35 am Post subject:
Re: Why are there only finitely many Steiner points?



tchow@lsa.umich.edu wrote:
Quote:  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.)

There are two questions:
1. The finiteness of the steinercandidate 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 n2
internal points [1]. There are f(n)=(2n4)!/2^(n2)/(n2)! nonisomorphic trees;
for each the minimum length, and the set of nonterminal points is unique [2].
There are at most
(n2) 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 

Back to top 


tchow@lsa.umich.edu science forum addict
Joined: 15 Sep 2005
Posts: 53

Posted: Thu Jun 29, 2006 11:19 pm Post subject:
Re: Why are there only finitely many Steiner points?



In article <44A2153A.9040505@hoffmannk.de>,
klaus hoffmann <nospam@hoffmannk.de> wrote:
<1. The finiteness of the steinercandidate set if n is finite
[...]
<Consider a fixed set of n terminal points. Build a connecting tree with n2
<internal points [1]. There are f(n)=(2n4)!/2^(n2)/(n2)!
<nonisomorphic trees;
<for each the minimum length, and the set of nonterminal points is unique [2].
<There are at most
<(n2) 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.

Tim Chow tchowatalumdotmitdotedu
The range of our projectileseven ... the artilleryhowever great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. Galileo, Dialogues Concerning Two New Sciences 

Back to top 


tchow@lsa.umich.edu science forum addict
Joined: 15 Sep 2005
Posts: 53

Posted: Sun Jul 02, 2006 7:55 pm Post subject:
Re: Why are there only finitely many Steiner points?



In article <44a18f0f$0$573$b45e6eb0@senatorbedfellow.mit.edu>, I wrote:
Quote:  "Obviously," such fractal monstrosities are ridiculous in the context of
Euclidean Steiner trees, but it seems annoying to prove.

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.

Tim Chow tchowatalumdotmitdotedu
The range of our projectileseven ... the artilleryhowever great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. Galileo, Dialogues Concerning Two New Sciences 

Back to top 


Google


Back to top 



The time now is Tue Jun 27, 2017 3:34 am  All times are GMT

