The Generation of Minimal Trees with a Steiner Topology

Abstract

An iterative method is described which generates a minimal tree with a Steiner topology in at most n - 2 steps, where n is the number of fixed vertices. The SI algorithm is formulated. When n < 4, the SI algorithm converges to a proper tree. Experimental studies indicate that this algorithm generates trees close to optimal Steiner minimal trees. hminimal tree for points Ai, A2, • • • , A~ in the plane is a spanning tree having these points as its vertices and having the sum of the lengths of all its lines as small as possible. There is a simple algorithm for generating minimal trees (13). However, one can often construct still shorter trees connecting A1, • • • , An by adding extra vertices in addition to Ai. For example, if A1, A2, As are three vertices at the cor- ners of an equilateral triangle, a shorter tree than the minimal tree for these vertices consists of three lines from A1, A2, A3 to an extra vertex S at the center of the tri- angle. An extra vertex S which is added to a tree to reduce its length is called a Steiner point (2). When any number of extra Steiner points can be added at will, the shortest possible tree is called the Steiner minimal tree. The problem of finding a Steiner minimal tree having n fixed points is called the Steiner problem (4, 6, 9). Melzak (11) first gave an algorithm for finding a Steiner minimal tree in a finite number of steps. The algorithm involves searching such a large number of different topologies that the computation is feasible only for very small values of n. Although a variety of geometric criteria have been discovered which are useful in reducing the number of possible alternatives (3, 5, 9), Melzak's algorithm is still impractical for n greater than 30. In this paper an iterative procedure is described which can be applied to a minimal tree to construct a better tree having certain desirable properties. Experimental studies indicate that this algorithm, called the SI algorithm in this paper, generates trees close to optimal Steiner minimal trees.