Premium
A probably fast, provably optimal algorithm for rectilinear Steiner trees
Author(s) -
Deneen Linda L.,
Shute Gary M.,
Thomborson Clark D.
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050405
Subject(s) - steiner tree problem , combinatorics , mathematics , time complexity , subdivision , base (topology) , rectangle , binary logarithm , set (abstract data type) , tree (set theory) , algorithm , discrete mathematics , degree (music) , computer science , mathematical analysis , physics , geometry , archaeology , acoustics , history , programming language
We use the technique of divide‐and‐conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well‐known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ϵ > 0, there exists b > 0 such that Prob[ T ( n ) > 2 b √ n log n ]>1–ϵ, for n log n > 1 – ϵ, for n sites uniformly distributed on a rectangle. The key fact in the run‐time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low‐degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.