1999年
A shortest pair of paths on the plane with obstacles and crossing areas
International Journal of Computational Geometry and Applications
- ,
- ,
- 巻
- 9
- 号
- 2
- 開始ページ
- 151
- 終了ページ
- 170
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1142/S021819599900011X
- 出版者・発行元
- World Scientific Publishing Co. Pte Ltd
Given obstacles and crossing areas together with two pairs of terminals on the plane, our algorithm finds a pair of rectilinear paths which connect the pairs of terminals, neither pass through any obstacle nor cross each other except in the crossing areas, and minimize the total length, where all obstacles and crossing areas are assumed to be axis-parallel rectangles. The algorithm takes O(n log n) time and O(n) space, where n is the total number of obstacles and crossing areas.
- ID情報
-
- DOI : 10.1142/S021819599900011X
- ISSN : 0218-1959
- SCOPUS ID : 0033409992