Rotationally optimal spanning and Steiner trees in uniform orientation metrics |
| |
Authors: | Marcus Brazil Benny K Nielsen Pawel Winter Martin Zachariasen |
| |
Institution: | a ARC Special Research Centre for Ultra-Broadband Information Networks, Department of Electrical and Electronic Engineering, The University of Melbourne, Victoria 3010, Australia b Department of Computer Science, University of Copenhagen, DK-2100, Copenhagen Ø, Denmark |
| |
Abstract: | We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees. |
| |
Keywords: | Steiner trees in uniform orientation metrics Rotational problems VLSI design |
本文献已被 ScienceDirect 等数据库收录! |
|