Forbidden subpaths for Steiner minimum networks in uniform orientation metrics

AbstractThe Steiner problem in the λ‐plane is the problem of constructing a minimum network connecting a given set of nodes (called terminals), with the constraint that all line segments have slopes chosen from the λ uniform orientation angles ω, 2ω, … , λω, where ω = π/λ. This problem appears to be substantially harder than either the Euclidean or rectilinear Steiner problem, as there can be many different λ‐networks that have the same topology and terminal set, but are locally minimal with respect to the perturbation of single Steiner points. In this paper, we show that there are large classes of such networks that cannot be minimum because they necessarily contain subpaths that can be perturbed to shorten the length of the network. These classes are defined in terms only of the angles between edges in the paths and not edge lengths. Using largely geometric methods, we give a complete classification of these “forbidden paths.” This classification will be a crucial element in devising a pruning process for future efficient exact algorithms for solving the Steiner problem in the λ‐plane. © 2002 Wiley Periodicals, Inc.