0
$\begingroup$

I have been looking at the wikipedia page for steiner trees, and I don't quite understand their 4-point solution. If the four vertices are arranged in a rectangle shape wouldn't there be only one steiner vertex required in the middle to create the shortest length graph? The solution shows two vertices S1 and S2, but it seems that it would be shorter if there was only one vertex S instead, in between S1 and S2 and all of the vertices A, B, C, and D connect to S.

$\endgroup$
  • 2
    $\begingroup$ There's an easy way to check: use a ruler :) $\endgroup$ – j_random_hacker May 21 '14 at 19:37
2
$\begingroup$

You are asking the question for Euclidean Steiner Trees. For Euclidean Steiner Tree problem one can show that "points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles". That's why you need two steiner vertices instead of just one for 4 point solution. If you take just one extra point the degree will be 4 and angles also will not remain 120 degree.

To prove the property of Euclidean Steiner Trees take help of your favorite search engine. A good reference. See section 3.

$\endgroup$
  • $\begingroup$ From the wiki page, "Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments." What I don't understand is how this is the minimum solution, because if I had just 1 steiner point at the center of the rectangle instead, with each of the initial vertices connecting directly to this point, then the total length would clearly be smaller than the length of the edges in the solution presented on the page. $\endgroup$ – hesson May 21 '14 at 19:59
2
$\begingroup$

Honestly, a ruler should be enough to convince you for this one case, though the difference may be quite small.

For the general 4-corners-of-a-tall-rectangle case, I suggest formulating an expression that computes the total distance of a 2-point Steiner tree in which the 4 points are the corners of a w by h rectangle, with w < h, and the two Steiner points are located x units either side of the vertical centre (and, of course, at the horizontal centre). Plug in x = 0 (your single-point solution -- i.e. a single point is the same as 2 overlapping points), and plug in x = h/2 - sqrt(1/3)*w/2 (the displacement for the optimal 2-point solution), and compare them. Even better, differentiate w.r.t. x and verify that the curve is 0 for the latter point.

$\endgroup$
  • $\begingroup$ If I draw two diagonals from A to D and from B to C, then the total length of these two diagonals is clearly smaller than the total length of the segments in the solution presented by virtue of the fact that any side of a triangle is always smaller than the sum of the other two sides. $\endgroup$ – hesson May 21 '14 at 19:53
  • 1
    $\begingroup$ Where are "the other two sides" used in the solution? I'm not writing anything further until you try it with a piece of paper and a ruler. $\endgroup$ – j_random_hacker May 21 '14 at 20:00
  • $\begingroup$ What I mean is, suppose P was the center point of the rectangle ABCD. Consider the triangle formed by A, P, and S1, the length of AP is shorter than AS1 + S1P by the triangle property. I can make the same argument for each of the 4 corners to show that (AP + PD + BP + PC) < (AS1 + BS1 + S1S2 + S2C + S2D). In other words, using one steiner point P is shorter than using two different points S1 and S2. $\endgroup$ – hesson May 21 '14 at 20:05
  • 1
    $\begingroup$ I know what you're overlooking, but because you're wasting my time by not doing the obvious thing that would immediately tell you what it is, I'm not going to tell you. $\endgroup$ – j_random_hacker May 21 '14 at 20:10
1
$\begingroup$

It seemed that using one steiner point at the center would be shorter because of the triangle property but the mistake I was making was double-counting the middle segment S1S2 in calculating the length of the graph which led me to believe that it was longer than it actually was. This was my (faulty) logic:

suppose P was the center point of the rectangle ABCD. Consider the triangle formed by A, P, and S1, the length of AP is shorter than AS1 + S1P by the triangle property. I can make the same argument for each of the 4 corners to show that (AP + PD + BP + PC) < (AS1 + BS1 + S1S2 + S2C + S2D). In other words, using one steiner point P is shorter than using two different points S1 and S2.

Although it's true that AP is shorter than AS1 + S1P, using this argument on all 4 corners, I implicitly counted the middle segment more than once.

$\endgroup$
  • $\begingroup$ I'm glad that you have understood what went wrong. $\endgroup$ – Sayan Bandyapadhyay May 21 '14 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.