Fast heuristic algorithms for rectilinear Steiner trees (Q1118419)

Given n points P in the plane, a rectilinear minimum spanning tree is a tree whose vertices are the n points, and whose total edge length in the rectilinear metric is minimum over all spanning trees. A rectilinear Steiner tree is then a tree of minimum total edge length over all spanning trees for sets \(P'\) of points with \(P\leq P'\). Vertices of \(P'\setminus P\) are Steiner points. It is NP-hard to determine the minimum total edge length of a rectilinear Steiner tree for P. In this paper, the author first surveys heuristics for the problem, and then gives a dramatic improvement on one of the early heuristics due to Hanan. Empirical results on large problems are used to illustrate the improvements.