Steiner Minimal Tree Problem



Bob Bell
Scientific Programming Track
CSS Senior Seminar Project
January 16, 1999

Objectives

Investigate several approaches to solving an extension to the "Steiner" problem
Find a graph of minimum overall length which connects a given set of N points in a plan and any others which you wish to introduce
Add the optimum number of points to minimize the total length of arcs connecting all points

Background

Minimizing a network's length is one of the oldest optimization problems in mathematics. It has also seen the attention of many of the leading mathematicians in history. As far back as the mid-seventeenth century the following problem was suggested: Find the point P that minimizes the sum of the distances from P to each of three given points in the plane. Another way to state this problem is to find the point P in a triangle so that the total distance from P to each of the triangle's vertices is minimized. Fermat, Torricelli, and Cavalieri independently derived solutions to this problem.

The general solution is that either P is inside the triangle formed by the points, and the angles formed by the lines connecting P to each of the points/vertices are all 120°, or P is one of the three vertices and the angle formed by connecting P to the other vertices is greater than or equal to 120°.

Figure 1 illustrates the method used by mid-seventeenth century mathematicians to construct the point P. To calculate P for points A, B, and C, first construct an equilateral triangle (ACX) using the longest edge (AC) of the triangle formed by the three original points so that the third point (B) lies outside of the newly formed triangle. Circumscribe a circle about the equilateral triangle, and construct a line from the third point (B) to the far vertex (X) of the equilateral triangle. The point and which the line and the circle intersect is P.

Figure 1

In the nineteenth century Jakob Steiner, a mathematician at the University of Berlin, studied this problem and expanded it to include an arbitrarily large set of points in the plane. This involved only one point still, forming a star-like shape when P was joined to each of the points. In this problem, P would also be the two-dimensional center of mass.

In 1934, Jarník and Kössler extended the problem even further by allowing the addition of an arbitrarily number of points to find the shortest network connecting all points. Courant and Robbins popularized this problem in their book What is Mathematics in 1941, linking Steiner to problem, which eventually became known as the Steiner Minimal Tree problem. Each point added to create the minimal network is called a Steiner Point, and the end result is a tree, instead on Steiner's star.

The Steiner problem can be seen in nature. Place pins to represent points into a flat surface. Also place a flat surface on the other ends of the pins. Dip this apparatus into a soap solution and remove. The soap film formed between the pins (points) will act to minimize the overall surface area. Since the distance between the surfaces is constant, the film will also be minimizing the total distance, forming Steiner points in the process.

Much is known about the mathematical structure of the Steiner Minimal Tree (SMT). Some basic properties of the SMT are:

All of the original n points will be connected to 1, 2, or 3 other points
All Steiner Points will be connected to 3 other points
Any two edges meet at an angle of at least 120° (which implies that the edges at a Steiner Point are exactly 120°)
At most n - 2 Steiner Points need to be added to the network
The length of an SMT will never be any shorter than sqrt(3)/2 times (~86.6%) the length of a minimal spanning tree (MST)
The problem is NP-Hard, or NP-Complete when discrete points are used (which is the case here). That is, the problem cannot be solved in polynomial time.

Brute Force

The first algorithm I implemented is a so-called "brute force" algorithm. This algorithm tries all combinations of every potential Steiner Point within a certain range. I anticipated this algorithm to be extremely slow due to the enormous possibilities it would try. However, because it tries all possibilities, it should also come up with the best possible solution.

Custom Algorithm

The second algorithm is one that I designed on my own. It starts out by constructing an MST using an algorithm I designed that appears to basically be Prim's approach. It then computes Steiner points for each pair on contiguous lines on the MST. It next removes lines that should not be included because of the existance of the new Steiner points. It also looks for pairs of points being connected by two Steiner points, and then joins those two Steiner points in the most efficient manner. After completing this process, the process is repeated, but this time the Steiner points are included in the MST. In addition, after each "pass", the points are analyzed to look for Steiner points with less than three connections, and those points are removed. This process is repeated until a minimal solution is found.

Input Format

The format for input to the program was given in the project specifications. Input files can be selected from a GUI that uses GTK+ for a file dialog. Files are collections of (x, y) points in an unstructured matter, separated only by whitespace. Each file is terminated with the sentinel 99999. As specified, the program has been tested with up to 1000 points, although more should be feasible, due to the dynamic allocation of memory. Also as speicified, the program assumes that the input files are correctly formatted, and improperly formatted files may result in unpredictable behavior.

Hardware & Software

I chose Linux on an Intel x86 CPU as my target platform, due to the technical superiority, availability, and familiarity of this combination, although the source code should be easily ported to other combinations. The entire program was coded in ANSI C, due to the performance advantages, portability, and familiarity of the language. GTK+ was chosen to create the GUI because it was available, native to C, executes quickly, and provided me with the chance to learn a toolkit that has received a lot of press coverage recently. Code was compiled with egcs 1.0.3. Software was tested on a dual Pentium II 400 MHz with 256 MB of RAM running Linux 2.1.131 and GTK+ 1.1.2.

Function & Procedures

Brute Force Method

gint brute_force (widget, event, client_data)

Called by GTK+ when the brute force method is selected from the menu. It sets the points up for processing, and well as initializing some data structures. When the process has completed, it cleans up memory and displays the graphical output.

void run_gamut (loc)

Called as run_gamut(0) in brute_force. This function calls itself recursively to iterate through all possible cominations of n-2 points with the bounding box containing all points. This procedure calls process_now() at each iteration.

void process_now ()

Processes the current configuration of points. Basically it computes the minimal spanning tree (MST) and holds on to the configuration if it is the best so far.

int **construct_mst (norig_pts, orig_pts)

Constructs a list of indices of connected points that comprise the MST. Apparently, the algorithm as implemented is quite faster that many other MST implementations used by others in this project. The algorithm takes the first point and makes a list of all points it to which it can connect, the distance to each point, and records that that distance is from the first point. That list is sorted and the point with the shortest distance is taken off. That point is added to the MST according to where it needed to be connected to make that minimal distance. The list of points is then updated to reflect any points that might be closer to the new point. This process is repeated recursive until the MST is built.

Custom Method

gint custom_alg (widget, event, client_data)

Called by GTK+ when the custom method is selected from the menu. It primarily handles the graphical output and leaves everything else up to rec_construct_smt.

void rec_construct_smt(norig_pts, orig_pts)

Primarily in charge of "recursively" (really iteratively) calling construct_smt. This procedure decides when to stop calling construct_smt. Each time it is called, all points generated (including Steiner points) are used in the MST. Also, old Steiner points that are no longer needed are discarded via remove_extras.

void construct_smt(norig_pts, orig_pts)

Calls a series of other procedures and takes care of some memory management. See description of functions below for more detail.

int **construct_mst(norig_pts, orig_pts)

This is the same procedure as in the brute force approach. The list of connected points is returned.

int **construct_adj_matrix(norig_pts, conn_matrix)

Takes the list of connected points and constructs an adjacency list where for each point the points it connects to is listed.

GdkPoint **create_steiner_pts(norig_pts, orig_pts, adj_matrix, nsp)

Takes the original points and the adjacency "matrix" and creates a list of Steiner points, including those that consist of no additional points. The real work is done by calc_steiner.

GdkPoint calc_steiner (points)

Uses the principal of an equilateral triangle, a circle, and a line to construct the Steiner point for a set of three points. This is fairly reliable, but due to the complexity of the geometry and equations involved may in some rare arrangements produce non-optimal results. Other solutions to find the Steiner point would be welcome.

void remove_extras(naps, all_points, nals, all_lines)

Looks for Steiner points that no longer connect to three other points and removes them.

void combine_graphs()
void combine_graph()

Both of the above functions perform some behind the scenes work of combining data structures.

Limitations

Project specifications limit the maximum number of original points to 1000. The program has been shown to run with more points, but has not been thoroughly tested at such configurations (e.g. the picture on the cover page is of 1600 data points).
Both algorithms only find Steiner points at integer values on the Cartesian plane
The "Brute force" technique is extremely inefficiently and is worthless to use with anything besides just a few densely spaced points (the custom approach can handle 1000 data points in just over two minutes)
Some trivial cases are not handled properly, as they would require special treatment. For instance, the case of only two points will return a distance of zero using the custom algorithm. This was not considered to be worthwhile improving since there is not a good reason to be examining this case in the first place.

Approach

In order to examine the two algorithms implemented, it would be best to generate multiple data sets for a varying number of points, and run each algorithm on each data set in turn. However, this proved to be problematic to implement. The key reason is time. The brute force algorithm is very extensive, but also takes an incredible amount of time. The time increases whenever the bounding box containing all points increases or the number of points increases. For only six points in a mere 6 x 7 grid takes over 3 minutes to compute. In comparison, the custom approach implemented in virtual instantaneous and results in exactly the same total distance. Therefore, the brute force method was not tested further. The custom algorithm was tested, but due to time restrictions, only one data set was used for each number of points (100, 200, 400, 800).

Results

Number of Points	Time (seconds)	Minimal Spanning Tree	Steiner Minimal Tree	Size Reduction	Number of Added Points
100	0.42	4377.38	4265.74	2.55%	42 (29.58%)
200	2.59	5897.82	5771.87	2.14%	79 (28.32%)
400	19.07	8166.43	7936.11	2.82%	172 (30.07%)
800	99.69	11179.04	10915.90	2.35%	291 (26.67%)

Figure 1

Analysis

The time to process points using the custom algorithm was much more manageable. Data sets with fewer points than 100 finished almost instantaneously. Subjectively, the networks produced by the custom algorithm appeared to be reasonable. Noting Table 1, the algorithm produced a consist 2-3% reduction in size over the MST with these random data sets, adding new points numbering 26-30% of the original points. A few non-random data sets were tried, and the algorithm typically performed admirably, only occasionally falling subject to geometric anomalies. An informal comparison to the algorithms implemented by others noticed my custom algorithm to be significantly quicker and produce slight shorter networks. It is also interesting to look at the time as a function of the number of data points. A graph of time versus number of points has been produced in Figure 2. The trendline shown is second-degree polynomial with a correlation of nearly 100%. It can therefore be said that for the data measured, the algorithm performed in a fairly quick implementation of O(n²) time. This is significant, because the Steiner problem cannot truly be solved in polynomial time. This is only possible because the algorithm implemented is an approximation algorithm, albeit a very good one, particularly with random data, but not guaranteed to find the absolute best SMT.
Figure 2

The brute force algorithm used is a natural way to solve the problem. By trying all the possibilities, you are guaranteed to find the optimal Steiner tree. While it could potentially be improved, its primary drawback is the enormous amount of possibilities that need to be checked. The algorithm is nearly useless in all practical applications.

The custom algorithm I design proved to be quite effective. It can solve problems with fairly large numbers of points quickly. It scales well, as observed by its O(n²) performance during experimentation. The key features to its success are most likely the minimal spanning tree algorithm and implementation and the ability to calculate the Steiner point for sets of three points exactly.

While the algorithm designed enjoyed success, it could still use some improvement. Of immediate interest would be some optimization in the areas of reusing information, better sorting, and combining multiple operations into a minimal number of passes. Also, the procedure to calculate the Steiner point should be examined for reliability, possibly by implementing another method to calculate the Steiner point. It would also be good to explore the possibility of adjusting the algorithm to perform better in certain geometric structures. Lastly, exploration parallelization of the algorithm could lead to some intriguing possibilities for improvements.

Page URL: /~bbell/steiner/index.shtml Author: Bob Bell Last modified: Wednesday, January 20, 1999 at 04:12 PM