×
Thomas, D. A.; Rubinstein, J. H.; Cole, T.

The Steiner minimal network for convex configurations. (English) Zbl 0774.05033

Discrete Comput. Geom. 9, No. 3, 323-333 (1993).
If \(X\) is a finite set of points in the Euclidean plane, the Steiner problem is to find a shortest network connecting the points. In general, this problem is NP-hard. In a former paper by D. A. Thomas and J. H. Rubinstein [ibid. 7, No. 1, 77-86 (1992; see the review above)] it is shown that the Steiner problem is much easier, if \(X\) lies on a circle. Generalizing this result the paper shows: Suppose \(X\) is a convex configuration with radius of maximum curvature \(r\) and at most one of the edges joining neighboring points has length strictly greater than \(r\), then the shortest network (the Steiner tree) consists of all the edges with a longest edge removed.
Reviewer: D.Cieslik (Greifswald)

Cited in 1 Document

MSC:

05C05 Trees
52A37 Other problems of combinatorial convexity

Keywords:

minimal spanning tree; Euclidean plane; Steiner problem; shortest network; convex configuration; Steiner tree

Citations:

Zbl 0774.05031
Cite Review PDF
Full Text: DOI EuDML

References:

[1] M. R. Garey, R. L. Graham, and D. S. Johnson, The Complexity of Computing Steiner Minimal Trees,SIAM J. Appl. Math.32 (1977), 835-859. · Zbl 0399.05023 · doi:10.1137/0132072
[2] R. L. Graham, Some Results on Steiner Minimal Trees, Unpublished manuscript, 11 May 1967.
[3] Z. A. Melzak, On the Problem of Steiner,Canad. Math. Bull.4 (1961), 143-148. · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[4] J. H. Rubinstein and D. A. Thomas, A Variational Approach to the Steiner Network Problem,Ann. Oper. Res.33 (1991), 481-499. · Zbl 0734.05040 · doi:10.1007/BF02071984
[5] J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Six Points,J. Combin. Theory Ser. A58 (1991), 54-77. · Zbl 0739.05034 · doi:10.1016/0097-3165(91)90073-P
[6] J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Cocircular Points,Discrete Comput. Geom.7 (1992), 77-86. · Zbl 0774.05031 · doi:10.1007/BF02187826
[7] J. H. Rubinstein and D. A. Thomas, Graham’s Problem on Shortest Networks for Points on a Circle,Algorithmica7 (1992), 193-218. · Zbl 0748.05051 · doi:10.1007/BF01758758
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.