軸平行多角形障害物がある平面上の最短路
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 障害物がある平面上で任意の2点間の最短路を求めるアルゴリズムを与える. 但し, 障害物はすべての辺が座標軸に平行な多角形であり, 道は座標軸に平行な線分からなるとする. このアルゴリズムの前処理の部分は, O(n^^2 log^^2n)の記憶領域を用いてO(n^^2log^^3n)時間で実行できる. また, 平面上の任意の2点間の距離はO(log^^2n)時間で求まり, 最短路はO(log^^2n+k)時間で求まる. ここで, nは多角形障害物の頂点の総数であり, kは最短路の線分の本数である.
- 社団法人電子情報通信学会の論文
- 1996-07-25
著者
関連論文
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 需要点と供給点があるグラフの分割問題の近似可能性
- 内部三角化平面グラフの開矩形勢力描画
- 平面グラフの矩形外周格子凸描画
- 現在のWebにおけるHITSについて
- 平面グラフの外頂点数最小の凸描画