@inproceedings{646c8776c56c4f878e6f7cf3b527d933,

title = "Finding shortest non-crossing rectilinear paths in plane regions",

abstract = "Let A be a plane region which is bounded by an outer rectangle and an inner one and has r rectangular obstacles inside the region. Let k terminal pairs lie on the outer and inner rectangular boundaries. This paper presents an efficient algorithm which finds k “non-crossing” rectilinear paths in the plane region A, each connecting a terminal pair without passing through any obstacles, 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 runs in time O(n log n) where n=r+k.",

author = "Takahashi, {Jun Ya} and Hitoshi Suzuki and Takao Nishizeki",

year = "1993",

doi = "10.1007/3-540-57568-5_239",

language = "English",

isbn = "9783540575689",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "98--107",

editor = "Ng, {Kam Wing} and Prabhakar Raghavan and N.V. Balasubramanian and Chin, {Francis Y.L.}",

booktitle = "Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings",

note = "4th International Symposium on Algorithms and Computation, ISAAC 1993 ; Conference date: 15-12-1993 Through 17-12-1993",

}