Improved computation of plane Steiner Minimal Trees

ASteiner Minimal Tree (SMT) for a given setA = {a ₁,...,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) besidesa ₁,...,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 aboutn = 30, while the innovations have facilitated solution of many randomly generated 100-point problems in reasonable processing times.This work was supported by the Canadian Natural Sciences and Engineering Council under Grant Numbers A-7544 and A-7558.