Forbidden Subpaths for Steiner Minimum Networks in Uniform Orientation Metrics

Abstract

The 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 t..