Gradient-constrained minimum networks. I. Fundamentals

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

21 Citations (Scopus)

Abstract

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 T 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 T is either three or four. If the edges in T 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 T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices.

Original languageEnglish
Article number353664
Pages (from-to)139-155
Number of pages17
JournalJournal of Global Optimization
Volume21
Issue number2
DOIs
Publication statusPublished - 2001
Externally publishedYes

Keywords

  • Gradient constraint
  • Minimum networks
  • Steiner trees

Cite this