Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.comgeo.2004.04.001 | Comput. Geom. |
Keywords | Field | DocType |
steiner tree,steiner trees in uniform orientation metrics,finite time algorithm,rotational minimum,so-called diagonal,edge segment,vlsi design,rectilinear steiner tree problem,rotational problems,simple algorithm,tree problem,general steiner tree problem,rotationally optimal,steiner tree change,uniform orientation metrics,minimum spanning tree,polynomial time,coordinate system,steiner tree problem | Discrete mathematics,Combinatorics,Distributed minimum spanning tree,Minimum degree spanning tree,Steiner tree problem,k-minimum spanning tree,Euclidean minimum spanning tree,Rectilinear Steiner tree,Spanning tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
29 | 3 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Brazil | 1 | 106 | 19.69 |
| Benny K. Nielsen | 2 | 72 | 5.35 |
| Pawel Winter | 3 | 99 | 12.98 |
| Martin Zachariasen | 4 | 343 | 29.69 |