平面上で2本の最短な道を求めるアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1994-07-22
• タイトル: 平面上で2本の最短な道を求めるアルゴリズム
• タイトル / 言語: en
• タイトル: An Algorithm for Finding a Shortest Pair of Paths in a Plane Region
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomation Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomation Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomation Sciences, Tohoku University
• 著者名: 草苅, 良至; 鈴木, 均; 西関, 隆夫
• 著者名(英): Yoshiyuki, Kusakari; Hitoshi, Suzuki; Takao, Nishizeki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本文では，2次元平面上にいくつかの長方形障害物といくつかの2層配線領域と2組の端子対が与えられたときに，障害物を避け2層領域以外では交差せずに各端子対を結ぶ2本の道で長さの和の最小な組を求める効率の良いアルゴリズムを与える．各道は座標軸に水平垂直な線分だけからなるものとする．障害物の個数をnとし，2層領域の個数をmとすると，アルゴリズムはO（（+）log（+））時間とO（+）の記憶量でこの問題を解くことができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given n rectangular obstacles, m rectangular crossing areas and two pairs of terminals, our algorithm finds a pair of paths P and P' each connecting a pair of terminals such that P and P' do not cross each other except in the crossing areas and the sum of the lengths of P and P' is minimum among all such paths. We assume that all the rectangles and paths are axis-parallel. The algorithm runs in time O((m+n)log(m+n)) and uses O(m+n) space.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 69(1994-AL-040), p. 65-72, 発行日 1994-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会