Shortest non-crossing rectilinear paths in plane regions

Jun Ya Takahashi, Hitoshi Suzuki, Takao Nishizeki

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)419-436
Number of pages18
JournalInternational Journal of Computational Geometry and Applications
Issue number5
Publication statusPublished - 1997


  • Algorithm
  • Non-crossing paths
  • Plane region
  • Rectilinear paths
  • VLSI single-layer routing


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

Cite this