Name
Abstract | ||
|---|---|---|
Let A be a plane region inside an outer rectangle with r rectangular obstacles, and let k terminal pairs lie on the boundaries of the outer rectangle and one of the obstacles. This paper presents an efficient algorithm which finds ''non-crossing'' rectilinear paths in the plane region A, each connecting a terminal pair without passing through any obstacles, and whose total length is minimum. Non-crossing paths may share common points or line segments but do not cross each other in the plane. The algorithm takes time O(nlogn) where n = k + r. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1142/S0218195997000259 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
algorithm, VLSI single-layer routing, non-crossing paths, rectilinear paths, plane region | Journal | 7 |
Issue | ISSN | Citations |
5 | 0218-1959 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun-ya Takahashi | 1 | 80 | 9.82 |
| H. Suzuki | 2 | 238 | 31.31 |
| Takao Nishizeki | 3 | 1771 | 267.08 |