A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets |
| |
| Authors: | D S Richards and J S Salowe |
| |
| Affiliation: | (1) Department of Computer Science, University of Virginia, 22903 Charlottesville, VA, USA |
| |
| Abstract: | Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k
4
n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem. |
| |
| Keywords: | Dynamic programming Polynomial-time algorithm Rectilinear convex hull Rectilinear metric Steiner minimal tree |
| 本文献已被 SpringerLink 等数据库收录！ |
