Graphs, Steiner Points and Trees

Steiner Points and Trees

This is a bit tangential to graph theory, but I wasn't sure where else to put it.

The problem of determining a minimal spanning tree has interesting spinoffs when the vertices of the graph are points in a metric space (usualy Rⁿ), and the resource being minimized is distance. As always, the greedy algorithm provides a minimal spanning tree in polynomial time. However, additional points, strategically placed, sometimes allow the original set of points to be connected using less overall edge length. Example: the minimal spanning tree connecting the three vertices of a unit equilateral triangle has length 2. By adding a point in the middle (equidistant from the original three), we can connect the three vertices using only sqrt(3) units of edge length. This is obviously less than 2; an improvement.

An additional point that reduces the length of the spanning tree is called a steiner point. The resulting tree is called a steiner tree. A minimal steiner tree minimizes total edge length. The minimum steiner tree is the best possible steiner tree. Finding such a tree can be very difficult.

A steiner point cannot be an endpoint, else we could simply delete it and its associated edge, reducing the length of the spanning tree. By the triangular inequality, a steiner point cannot have degree two.

Let the steiner point have degree 3, while the graph lives in normal space. If the point is "out of plane", move the steiner point into the plane determined by the three adjacent points, reducing the lengths of all the incident edges. Then suppose one of the three angles is less than 120°. Move the point a distance δ down the angle bisector, thus opening the angle up. The two lines supporting this angle each decrease by at least half of δ, while the third line increases by at most δ. The sum of the three lengths has decreased. In a minimal steiner tree, the steiner points of degree 3 all have angles of 120°, and are "in plane". Note that a steiner point cannot meaningfully connect three points that form a triangle whose obtuse angle exceeds 120°.

If a vertex has degree 4 or more, find to edges that form an angle less than 120°, and slide a new steiner point away from the high degree vertex, down the angle bisector. As before, the angle lines shorten while the new steiner line lengthens. The other lines coming into the vertex do not move or change. Continue spawning new steiner points until each steiner point has degree 3, and each of the original vertices has degree 3 or less.

Let's connect the corners of a unit square. Without steiner points, the spanning tree has length 3, with 3 of the 4 sides drawn in. Your next impulse is to connect the four corners to the center, introducing one steiner point. This gives an edge length of 2.828, a definite improvement over 3. Next, split the steiner point in two and pull the two points apart, towards the left and right sides of the square, until the angles are 120°. This gives an edge length of 2.732. This is the best steiner tree for the square.

3 Dimensions

The steiner point generalizes to higher dimensions, continuing the 120° theme. Let's analyze the regular tetrahedron with edge length 1. The base is an equilateral triangle whose side has length 1. Let u be the center of this base; it is sqrt(3)/3 distance from the 3 corners. Let a be the apex. The distance from u to a is sqrt(6)/3. Let c be the center of the tetrahedron. The distance from u up to c is sqrt(6)/12, and the distance from c up to a, or to any of the four corners, is sqrt(6)/4. The length of the one point steiner network is sqrt(6). The angles at c are 109 degrees, like a methane molecule. Pull c apart into two points, traveling along a path joining the midpoints of two opposite edges. The distance between these midpoints is sqrt(2)/2. The first point connects to the ends of the first edge, and the second point connects to the ends of the second edge, making 120° angles as usual. These angles are in plane; we have a minimal steiner tree. The new steiner distance is sqrt(3) + sqrt(2)/2. This is 2.439, which is better than 2.449.

We can always do this because four lines imply at least one angle of 109° or less, and more incident edges can only introduce smaller angles. So a new point can always pull away, and open up the angle to 120°.

Higher Dimensions

Let c lie in the center of a generalized tetrahedron in 4 dimensions. Thus 5 lines meet at c. Prove that the angles are bounded below 120°, and the above reasoning holds. One can find the length from center to corner by induction on n. The previous center b sits in the middle of the floor of the new tetrahedron, with distance d to the corners of the floor. The distance from b up to the new center c is x, and the distance all the way up to a is sqrt(1-d²). Write sqrt(d²+x²) = sqrt(1-d²)-x. Square both sides and solve for x, giving x = (1-2d²) over 2×sqrt(1-d²). Square this, add d², and take the square root, giving 1 over 2×sqrt(1-d²). For d less than sqrt(½), this is a contraction map. The lengtth from center to corner approaches sqrt(½) as n approaches infinity. the central angle approaches 90°, and we're in good shape.

Noneuclidean

A noneuclidean surface is still euclidean at the local level, so we can expect each steiner point to follow the 120° rule. However, the minimum steiner tree might not be what you expect. Consider the sphere with a circumference of 1. Let an equilateral triangle run around the equator. Place a steiner point at the north pole, giving a network distance of 3/4. This is a minimal tree, but a better tree consists of two of the three edges from the original triangle, with network length 2/3.