×

How to find Steiner minimal trees in Euclidean \(d\)-space. (English) Zbl 0751.05028

Author’s abstract: This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connecting \(N\) sites in \(d\)- space, \(d\geq 2\). We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees in \(d\)-space for \(d>2\), and also the first one which fits naturally into the framework of “backtracking” and “branch- and-bound”. Finding SMTs of up to \(N=12\) general sites in \(d\)-space (for any \(d\)) now appears feasible.
We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedean \(d\)-polytopes with \(\leq 16\) vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3-9. (The conjecture remains open in other dimensions; it is probably false in all dimensions \(d\) with \(d\geq 3\), but is probably true when \(d=2\).)
The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision \(\varepsilon\). We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time \(O(C^ N)\) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision \(\varepsilon\), then there is an \((N/\varepsilon)^{O(\sqrt N)}\)-time algorithm, which is subexponential if \(1/\varepsilon\) grows only polynomially with \(N\). Also, the rectilinear Steiner minimal tree of \(N\) points in the plane may be found in \(N^{O(\sqrt N)}\) time.
J. S. Provan devised an \(O(N^ 6/\varepsilon^ 4)\)-time algorithm for finding the SMT of a convex \(N\)-point set in the plane. (Also the rectilinear SMT of such a set may be found in \(O(N^ 6)\) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true — if a certain conjecture about the size of “Steiner sensitivity diagrams” is correct. All of these algorithms are for a “real RAM” model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding the exact optimum SMT, or trees with lengths \(\leq (1+\varepsilon)\times\) optimum, where \(\varepsilon\) is arbitrarily small, are considered here.
Reviewer: K.Engel (Rostock)

MSC:

05C05 Trees
90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)

Software:

FindSteinerTree
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Garey, M. R.; Hwang, F. K., Rectilinear Steiner trees: Efficient special case algorithms, Networks, 7, 37-58 (1977) · Zbl 0351.05102 · doi:10.1002/net.3230070104
[2] Ajtai, M.; Chvatal, V.; Newborn, M. M.; Szemeredi, E., Crossing free subgraphs, Ann. Discrete Math., 12, 9-12 (1982) · Zbl 0502.05021
[3] Chang, S. K., The generation of minimal trees with a Steiner topology, J. Assoc. Comput. Math., 19, 699-711 (1972) · Zbl 0251.94031
[4] Chung, F. R. K.; Gilbert, E. N., Steiner trees for the regular simplex, Bull. Inst. Math. Acad. Sinica, 4, 313-325 (1976) · Zbl 0351.05103
[5] Chung, F. R. K.; Graham, R. L., A new bound for Euclidean Steiner trees, Ann. N. Y. Acad. Sci, 440, 328-346 (1985) · Zbl 0572.05022 · doi:10.1111/j.1749-6632.1985.tb14564.x
[6] Cockayne, E. J., On Fermat’s problem on the surface of a sphere, Math. Mag., 45, 216-219 (1972) · Zbl 0257.52013 · doi:10.2307/2688662
[7] Cockayne, E. J.; Hewgill, D. E., Exact computation of Steiner minimal trees in the plane, Inform. Process. Lett., 22, 151-156 (1986) · Zbl 0593.05022 · doi:10.1016/0020-0190(86)90062-1
[8] Derigs, U., A shortest augmenting path method for solving minimum perfect matching problems, Networks, 11, 379-390 (1981) · Zbl 0475.05069 · doi:10.1002/net.3230110407
[9] Du, D. Z., On Steiner ratio conjectures, manuscript (1989), Beijing, China: Inst. Appl. Math. Academia Sinica, Beijing, China
[10] D. Z. Du: The Steiner ratio conjecture is true for six points, to be published. · Zbl 0576.05015
[11] Du, D. Z.; Hwang, F. K.; Weng, J. F., Steiner minimal trees for regular polygons, Discrete Comput. Geom., 2, 1, 65-87 (1987) · Zbl 0607.05022 · doi:10.1007/BF02187871
[12] Edelsbrunner, H., Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science (1987), Berlin: Springer-Verlag, Berlin · Zbl 0634.52001
[13] Friedman, J. H.; Bentley, J. L.; Finkel, R. A., An algorithm for performing best matches in logarithmic expected time, ACMTOMS, 3, 3, 209-226 (1977) · Zbl 0364.68037
[14] Garey, M. R.; Johnson, D. S., The complexity of computing Steiner minimum trees, SIAM J. Algebraic Discrete Methods, 32, 835-859 (1977) · Zbl 0399.05023
[15] Garey, M. R.; Johnson, D. S., The rectilinear Steiner minimum tree problem is NP-complete, SIAM J. Algebraic Discrete Methods, 32, 826-834 (1977) · Zbl 0396.05009
[16] Gekeler, E., On the solution of systems of equations by the epsilon algorithm of Wynn, Math. Comp., 26, 118, 427-436 (1972) · Zbl 0239.65050 · doi:10.2307/2005169
[17] Georgakopoulos, G.; Papadimitriou, C. H., The 1-Steiner tree problem, J. Algorithms, 8, 122-130 (1987) · Zbl 0642.68131 · doi:10.1016/0196-6774(87)90032-0
[18] Gilbert, E. N.; Pollak, H. O., Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29 (1968) · Zbl 0159.22001 · doi:10.1137/0116001
[19] Graham, R. L.; Hwang, F. K., Remarks on Steiner minimal trees I, Bull. Inst. Math. Acad. Sinica, 4, 177-182 (1976) · Zbl 0333.05101
[20] Hanan, M., On Steiner’s problem with rectilinear distance, SIAM J. Appl. Math., 14, 255-265 (1966) · Zbl 0151.33205 · doi:10.1137/0114025
[21] Heibig-Hansen, K.; Krarup, J., Improvements of the Held-Karp algorithm for the symmetric TSP, Math. Programming, 7, 87-96 (1974) · Zbl 0285.90055 · doi:10.1007/BF01585505
[22] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees, Oper. Res., 18, 1138-1162 (1970) · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[23] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees, part II, Math. Programming, 1, 6-25 (1971) · Zbl 0232.90038 · doi:10.1007/BF01584070
[24] Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. Assoc. Comput. Math., 21, 549-558 (1974) · Zbl 0307.68025
[25] Hwang, F. K., A linear time algorithm for full Steiner trees, Oper. Res. Lett., 5, 235-237 (1986) · Zbl 0582.05022 · doi:10.1016/0167-6377(86)90008-8
[26] Hwang, F. K.; Richards, D. S., Steiner tree problems (1989), Murray Hill, NJ: Bell Laboratories, Murray Hill, NJ
[27] Hwang, F. K.; Song, G. D.; Ting, G. Y.; Du, D. Z., A decomposition theorem on Euclidean Steiner minimal trees, Discrete Comput. Geom., 3, 4, 367-392 (1988) · Zbl 0659.05042 · doi:10.1007/BF02187919
[28] Hwang, F. K.; Weng, J. F., Hexagonal coordinate systems and Steiner minimal trees, Discrete Math., 62, 49-57 (1986) · Zbl 0601.05016 · doi:10.1016/0012-365X(86)90040-3
[29] Hwang, F. K.; Weng, J. F., The shortest network with a given topology (1988), Murray Hill, NJ: Bell Laboratories, Murray Hill, NJ
[30] Kang, A. N. C.; Ault, D. A., Some properties of the centroid of a free tree, Inform. Process. Lett, 4, 1, 18-20 (1975) · Zbl 0313.68032 · doi:10.1016/0020-0190(75)90055-1
[31] Kernighan, B.; Ritchie, D., The C Programming Language (1978), Englewood Cliffs, NJ: Prentice-Hall, Englewood Cliffs, NJ
[32] Kruskal, J. R. Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 1, 48-50 (1956) · Zbl 0070.18404 · doi:10.2307/2033241
[33] Kuhn, H. W.; Abadie, J., On a pair of dual nonlinear programs, Methods of Nonlinear Programming, 38-54 (1967), Amsterdam: North-Holland, Amsterdam · Zbl 0153.30601
[34] Kuhn, H. W., A note on Fermat’s problem, Math. Programming, 4, 98-107 (1973) · Zbl 0255.90063 · doi:10.1007/BF01584648
[35] Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy; Schmoys, D. B., The TST, A Guided Tour of Combinatoral Optimization (1985), New York: Wiley-Interscience, New York · Zbl 0562.00014
[36] Melzak, Z. A., On the problem of Steiner, Canad. Math. Bull., 4, 143-148 (1961) · Zbl 0101.13201
[37] Miller, G. L., Finding small simple cycle separators for 2-connected planar graphs, J. Comput. System Sci., 32, 265-179 (1986) · Zbl 0607.05028 · doi:10.1016/0022-0000(86)90030-9
[38] Milnor, J., On the Betti numbers of real algebraic varieties, Amer. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302 · doi:10.2307/2034050
[39] C. Monma, M. Paterson, S. Suri, and F. Yao: Computing Euclidean maximum spanning trees, ACM Computational Geometry Conference 1988, pp. 241-251. · Zbl 0696.68066
[40] Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), New York: Springer-Verlag, New York · Zbl 0759.68037
[41] Prim, R. C., Shortest Connection Networks and Some Generalizations, Bell System Tech. J., 36, 1389-1401 (1957)
[42] Provan, J. S., Convexity and the Steiner tree problem, Networks, 18, 55-72 (1988) · Zbl 0645.90091 · doi:10.1002/net.3230180108
[43] P. W. Shor and W. D. Smith: Steiner hulls and θ-hulls, manuscript, 1989.
[44] W. D. Smith: Studies in Discrete and Computational Geometry, Ph.D. Thesis, Program in Applied and Computational Mathematics, Princeton University, September 1988.
[45] D. Smith: Finding the optimum traveling salesman tour forN sites in the Euclidean plane in subexponential time and polynomial space,SIAM J. Comput., submitted.
[46] Smith, J. M.; Lee, D. T.; Liebman, J. S., A O(N 1gN) algorithm for Steiner minimal tree problems in the Euclidean metric, Networks, 11, 23-29 (1981) · Zbl 0459.68032 · doi:10.1002/net.3230110104
[47] Soukup, J., Minimum Steiner trees, roots of a polynomial, and other magic, ACM SIGMAP Newsletter, 22, 37-51 (1977)
[48] R. P. Stanley: The number of faces of simplicial poly topes and spheres, in: Discrete Geometry and Convexity,Proc. N. Y. Acad. Sci., (1986).
[49] Tarjan, R. E., Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44 (1983), Philadelphia, PA: Society of Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0584.68077
[50] Uspensky, J. V., Theory of Equations (1948), New York: McGraw-Hill, New York
[51] van der Waerden, B. L., Algebra (1970), New York: Ungar, New York
[52] Warren, H. E., Lower Bounds for approximation by nonlinear manifolds, Trans. Amer. Math. Soc., 133, 167-178 (1968) · Zbl 0174.35403 · doi:10.2307/1994937
[53] Winter, P., An algorithm for the Steiner problem in the Euclidean Plane, Networks, 15, 323-345 (1985) · Zbl 0586.90087 · doi:10.1002/net.3230150305
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.