氏名: 松尾真臣 (m953430 )
論文題目: 平面上の最短経路に関する研究
論文概要
最短経路問題とは，空間内に障害物と2点が与えられたとき，その2点を結び障
害物に交差しない経路で長さが最短になるものを求める問題である．平面上の
最短経路問題は，VLSI設計，ロボットの動作計画，自動車の航行システムなど
の分野に応用がある．特に，VLSI設計ではユークリッド距離において最短な経
路ではなく，軸平行な経路，つまり水平および垂直な線分のみで構成される経
路で最短なものを求めることが要求される．本論文では，そのような経路を求
める問題を考える．障害物を長方形に限定したとき，前処理をO(n^2)時間で行
い，任意の2点間の最短経路をO(log n+k)時間で求めるアルゴリズムが知られ
ている．ここで，nは長方形の頂点数でありkは最短経路を構成する辺の数であ
る．本論文では，このアルゴリズムを拡張し，障害物が軸平行多角形の場合を
扱う．本アルゴリズムでは，まず，それぞれの障害物において，頂点間の最短
経路を求める．次に，先のアルゴリズムを用いて各障害物間の最短経路を求め
る．最後に，これらの最短経路を組みあわせることにより任意の2点間の最短
経路を求める．
目次に戻る