Abstract
In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to β√N for some constant β (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants β. In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN.
Similar content being viewed by others
References
A. V. Aho, M. R. Garey, and F. K. Hwang, Rectilinear Steiner trees: efficient special case algorithms,Networks,7 (1977), 37–58.
M. W. Bern and M. de Carvalho. A greedy heuristic for the rectilinear Steiner tree problem, Technical Report UCB/CSD 87/306, University of California at Berkeley, 1986.
F. R. K. Chung and R. L. Graham, On Steiner trees for bounded point sets,Geom. Dedicata,11 (1981), 353–361.
F. R. K. Chung and F. K. Hwang, The largest minimal rectilinear Steiner trees for a set ofn points enclosed in a rectangle with given perimeter,Networks,9 (1979), 19–36.
M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete,SIAM J. Appl. Math.,32 (1977), 826–834.
M. Haimovich and A. H. G. Rinnooy Kan, Personal communication with A. H. G. Rinnooy Kan.
F. K. Hwang, On Steiner minimal trees with rectilinear distance,SIAM J. Appl. Math.,30 (1976), 104–114.
F. K. Hwang, The rectilinear Steiner problem,Design Automat. Fault-Tolerant Comput.,2 (1978), 303–310.
F. K. Hwang, AnO(N logN) algorithm for suboptimal rectilinear Steiner trees,IEEE Trans. Circuits and Systems,26 (1979), 75–77.
R. M. Karp and J. M. Steele, Probabilistic analysis of heuristics, inThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds.), Wiley, New York, 1985, Chapter 6.
J. Komlós and M. T. Shing, Probabilistic partitioning algorithms for the rectilinear Steiner problem,Networks,15 (1985), 413–424.
J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proc. Amer. Math. Soc.,7 (1956), 48–50.
E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976, p. 290.
J. H. Lee, N. K. Bose, and F. K. Hwang, Use of Steiner's problem in suboptimal routing in rectilinear metric,IEEE Trans. Circuits and Systems,23 (1976), 470–476.
J. MacGregor-Smith and J. S. Liebman, Steiner trees, Steiner circuits, and the interference problem in building design,Engrg. Optim.,4 (1979), 15–36.
J. MacGregor-Smith, D. T. Lee, and J. S. Liebman, AnO(N logN) heuristic algorithm for the rectilinear Steiner problem,Engrg. Optim.,4 (1980), 179–192.
A. Ng, Personal communication, University of California at Berkeley.
C. H. Papadimitriou, The probabilistic analysis of matching heuristics,Proceedings of the 15th Annual Allerton Conference on Communication, Control, and Computing, 1977, pp. 368–378.
H. R. Pitt,Tauberian Theorems, Oxford University Press, Oxford, 1958, pp. 37–42.
R. C. Prim, Shortest connecting networks and some generalizations,Bell System Tech. J.,36 (1957), 1389–1401.
M. Servit, Heuristic algorithms for rectilinear Steiner trees,Digital Process.,7 (1981), 21–32.
J. M. Steele, Subadditive Euclidean functionals and nonlinear growth in geometric probability,Ann. Probab.,9 (1982), 365–376.
C. D. Thomborson, Personal communications, University of Minnesota at Duluth.
Y. Y. Yang and O. Wing, Suboptimal algorithm for a wire routing problem,IEEE Trans. Circuit Theory,19 (1972), 508–511.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
Research supported in part by NSF Grant MCS-8311422. A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986.
Rights and permissions
About this article
Cite this article
Bern, M.W. Two probabilistic results on rectilinear steiner trees. Algorithmica 3, 191–204 (1988). https://doi.org/10.1007/BF01762114
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01762114