×

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

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.

MSC:

05C05 Trees
52A37 Other problems of combinatorial convexity

Citations:

Zbl 0774.05031
PDF BibTeX XML Cite
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
[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
[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
[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
[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
[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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.