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(n log n) where n = k + r.
|Number of pages||18|
|Journal||International Journal of Computational Geometry and Applications|
|Publication status||Published - 1997|
- Non-crossing paths
- Plane region
- Rectilinear paths
- VLSI single-layer routing