Why are there only finitely many Steiner points?

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

  1. tchow

    tchow Guest

    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
    #1
    1. Advertisements

  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, Jun 26, 2006
    #2
    1. Advertisements


  3. ist the finiteness unconditional, i.E. for bounded and unbounded pointsets?
    Could yo give a link?
    regards
    Klaus
     
    klaus hoffmann, Jun 26, 2006
    #3
  4. 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
    #4
  5. tchow

    tchow Guest

    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
    #5
  6. 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
    #6
  7. tchow

    tchow Guest

    <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
    #7
  8. tchow

    tchow Guest

    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
    #8
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.