|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/5585
|
| Title: | An O(k℗n)-time algorithm for constructing an optimal rectilinear steiner tree for extremal point sets |
| Authors: | Tang, Chi-keung |
| Issue Date: | 1994 |
| Abstract: | 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. |
| Description: | Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1994
60 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1994 Tang |
| URI: | http://hdl.handle.net/1783.1/5585 |
| Appears in Collections: | CSE Master Theses
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| th_redirect.html | | 0Kb | HTML | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
