Shortest Non-Crossing Rectilinear Paths in Plane Regions
Jun-ya Takahashi, Hitoshi Suzuki, Takao Nishizeki · International Journal of Computational Geometry & Applications · 1997
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.