FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Research
Why are there only finitely many Steiner points?
Post new topic   Reply to topic Page 1 of 1 [8 Posts] View previous topic :: View next topic
Author Message
tchow@lsa.umich.edu
science forum addict


Joined: 15 Sep 2005
Posts: 53

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

In article <44a18f0f$0$573$b45e6eb0@senator-bedfellow.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 tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however 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

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

In article <44A2153A.9040505@hoffmannk.de>,
klaus hoffmann <nospam@hoffmannk.de> wrote:
<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.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however 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

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

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 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
Back to top
tchow@lsa.umich.edu
science forum addict


Joined: 15 Sep 2005
Posts: 53

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

In article <gerry-B7C636.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 tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however 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

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

Gerry Myerson wrote:
Quote:
In article <449d7c41$0$580$b45e6eb0@senator-bedfellow.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
klaus hoffmann
science forum beginner


Joined: 31 Jan 2006
Posts: 12

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

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
Gerry Myerson
science forum Guru


Joined: 28 Apr 2005
Posts: 871

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

In article <449d7c41$0$580$b45e6eb0@senator-bedfellow.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
tchow@lsa.umich.edu
science forum addict


Joined: 15 Sep 2005
Posts: 53

PostPosted: Sat Jun 24, 2006 5:54 pm    Post subject: Why are there only finitely many Steiner points? Reply with 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.)
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however 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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [8 Posts] View previous topic :: View next topic
The time now is Tue Jun 27, 2017 3:28 am | All times are GMT
Forum index » Science and Technology » Math » Research
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Fixed points of a weakly continuous map f:H->H satisfying... Jack Stone Research 2 Mon Jul 10, 2006 3:12 pm
No new posts Rational Points deepkdeb@yahoo.com Math 9 Fri Jul 07, 2006 1:40 am
No new posts Linking points on algebraic curves with class numbers Dave Rusin Math 5 Wed Jun 28, 2006 8:30 pm
No new posts Ellipse through 2 points in a circle. bandasanders@gmail.com Math 2 Sat Jun 24, 2006 4:10 am
No new posts fractional part of the function at integer points+concave eugene Math 4 Fri Jun 23, 2006 9:35 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0229s ][ Queries: 20 (0.0037s) ][ GZIP on - Debug on ]