IMPROVED COMPUTATION OF PLANE STEINER MINIMAL-TREES

A Steiner Minimal Tree (SMT) for a given set A = {a1,...,a(n)} in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches. is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besides a1,...,a(n). Various improvements are presented to an earlier computer program of the authors for plane SMTs. These changes have radically reduced machine times. The existing program was limited in application to about n = 30, while the innovations have facilitated solution of many randomly generated 100-point problems in reasonable processing times.