Search   Memberlist   Usergroups
 Page 1 of 1 [8 Posts]
Author Message
tchow@lsa.umich.edu

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 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
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@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)
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?
regards
Klaus
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@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
tchow@lsa.umich.edu

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 <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
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 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
tchow@lsa.umich.edu

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 wrote: <1. The finiteness of the steiner-candidate set if n is finite [...]
tchow@lsa.umich.edu

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@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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [8 Posts]
 The time now is Tue Dec 11, 2018 12:10 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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