STEINER NETWORKS WITH A MOVING BOUNDARY: THE CASE OF A STRAIGHT LINE AND A PAIR OF POINTS
Abstract
The paper is devoted to the problem of constructing minimal networks spanning a discrete set of points and a smooth curve, or a surface in Euclidean space. The problem represents one of the generalizations of the Steiner problem. In the case of two points and a line in the Euclidean plane, we describe sets of points for all types of absolutely minimal graphs, as well as minimal spanning graphs and Steiner graphs; the lengths of all kinds of minimal graphs and ratio of the lengths of Steiner graphs to the lengths of the minimal spanning graphs are calculated: a set of such ratios coincides with the set of points in the interval.
References
1. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. Москва; Ижевск: Институт компьютерных исследований, 2003. С. 424.
2. R. Booth, D.A. Thomas, and J.F. Weng, Shortest Networks for One line and Two Points in Space // Advances in Steiner Trees edited by Ding-Zhu, J.M. Smith and J.H. Rubinstein, Kluwer Academic Publishers, Boston, London, 2000. P. 15-27.
Review
Views:
87
Email this article 