Gradient‐Constrained Minimum Networks. III. Fixed Topology

The gradient‐constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3‐space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).