Abstract
We consider the problem of nding a minimum spanning tree for a set of points in the plane where the orientations of edges are restricted to uniformly distributed orientations, = 2; 3; 4; : : :, and where the coordinate system can be rotated around the origo by an arbitrary angle. The most important case with applications in VLSI design arises when = 2; in this, so-called rectilinear case, the edges have to be parallel with the x- or y-axis. We suggest a straightforward algorithm to solve this problem. We also discuss how to solve the rectilinear Steiner tree problem in the rotational setting. Finally, we provide some computational results indicating the average savings for dierent values of n and both for spanning and Steiner trees.
| Original language | English |
|---|---|
| Pages | 1-5 |
| Number of pages | 5 |
| Publication status | Published - 2002 |