## 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.

### MSC:

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