STEINER TREE CONSTRUCTIONS IN LAMBDA(3)-METRIC

We consider Steiner minimal trees (SMT's) in metrics defined by given orientations. The problem is motivated by wiring considerations of VLS I chips when the wiring direction is not restricted to only horizontal and vertical. In particular, we concentrate on the case when the give n orientations form angles of 0 degrees, 60 degrees, and 120 degrees ( lambda(3)-metric) since many interesting results can be obtained which may shed light on other metrics in the family, Specifically, we show that any SMT can be transformed to one with their Steiner points locat ed on the grid points of a multilevel grid, where the number of levels can be quite small. Based on this result, we have developed a simulat ed annealing-based algorithm to generate near-optimal SMT's. Empirical results and comparisons with Euclidean cases are also given.