Concatenation-based greedy heuristics for the Euclidean Steiner tree problem

We present a class of O (n log n) heuristics for the Steiner tree problem i n the Euclidean plane. These heuristics identify a small number of subsets with few, geometrically close, terminals using minimum spanning trees and o ther well-known structures from computational geometry: Delaunay triangulat ions, Gabriel graphs, relative neighborhood graphs, and higher-order Vorono i diagrams. Full Steiner trees of all these subsets are sorted according to some appropriately chosen measure of quality. A tree spanning all terminal s is constructed using greedy concatenation. New heuristics are compared wi th each other and with heuristics from the literature by performing extensi ve computational experiments on both randomly generated and library problem instances.