@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",
}