This page gives a practical O(nlog2n)
batched greedy triple contraction
for computing near-optimal rectilinear and octilinear Steiner trees.
II. Experimental Comparison
See the paper below for solution quality and runtime comparison of the
batched greedy algorithm with
Guibas-Stolfi MST code,
Rohe's Prim-based heuristic,
the edge-based heuristic of Borah, Owens, and Irwin,
III. Source code
The source code below is an updated
by Jarrod Alexander Roy from the University of Michigan. This version
removes a bug that caused the original code to crash for inputs containing
duplicated points or for which an added Steiner point duplicates an existing
terminal. For a full list of modification see the README file below.