Gradient-constrained minimum networks. I: Fundamentals. (English) Zbl 1068.90605

Summary: In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value \(m\). A gradient-constrained minimum Steiner tree \(\tau\) is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than \(m\). We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in \(\tau\) is either three or four. If the edges in \(\tau\) are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to \(m\), then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in \(\tau\). Moreover, we prove that all four edges incident with a degree 4 Steiner point in \(\tau\) must have gradient \(m\) if \(m\) is less than 0.38. Finally, we use the variational argument to locate the Steiner points in \(\tau\) in terms of the positions of the neighbouring vertices.


90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
90B10 Deterministic network models in operations research
Full Text: DOI