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 ext...[ Read more ]

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 ο(k²n) time. Thus our algorithm has the best asymptotic time complexity known for the problem.