Finding shortest non-crossing rectilinear paths in plane regions

Jun Ya Takahashi, Hitoshi Suzuki, Takao Nishizeki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings
EditorsKam Wing Ng, Prabhakar Raghavan, N.V. Balasubramanian, Francis Y.L. Chin
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783540575689
Publication statusPublished - 1993
Event4th International Symposium on Algorithms and Computation, ISAAC 1993 - Hong Kong, China
Duration: 1993 Dec 151993 Dec 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume762 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Symposium on Algorithms and Computation, ISAAC 1993
CityHong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Finding shortest non-crossing rectilinear paths in plane regions'. Together they form a unique fingerprint.

Cite this