Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5585

An O(k℗n)-time algorithm for constructing an optimal rectilinear steiner tree for extremal point sets

Authors Tang, Chi-keung
Issue Date 1994
Summary A point set is extremal if and only if the points lie on the boundary of a rectilinear convex hull of the point set [l0]. For an extremal point set of size n, the problem of constructing an optimal rectilinear Steiner tree was first shown to be solvable in ο(n[to the power of 6]) time by Provan [9]. Later, Bern [3], and Erickson [6] developed a faster algorithm that runs in ο(n[to the power of 5]) time. Richards and Salowe [l0] developed an improved algorithm and solves the problem in ο(k[to the power of 4]n), where k is the number of sides of the rectilinear convex hull. Cheng et al. [4] observed a common substructure which often appears in an optimal Steiner tree and developed a dynamic programming algorithm that runs in ο(n[to the power of 3]) [4]. In the worst-case scenario, an extremal point set can have θ(n) boundary edges. So the algorithm in [4] has a better asymptotic time complexity than the algorithm given by Richards and Salowe. In this thesis, we make use of some of the results in [4] and [l0] and redesign a dynamic programming algorithm that runs in ο(k2n) time. Thus our algorithm has the best asymptotic time complexity known for the problem.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1994
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML