点集合の移動に関する最短経路問題について

スポンサーリンク

概要

論文の詳細を見る
本稿では,移動する物体としてk個の点からなる点集合を定義し,水平,垂直線分からなるn個の長方形の障害物が存在する平面における最短経路問題について考察する.点集合とは,お互いの間の相対位置が移動中もつねに等しいものとする.本稿では,1点の最短経路をT(n)時間S(n)領域で求めるアルゴリズムが存在すれば,k個の点からなる点集合と水平,垂直な辺からなるn個の長方形の障害物の集合と任意の2点s,tが与えられたとき,s,tをそれぞれ始点,終点とする点集合の最短経路をO(max(nklog(nk),T(nk)))時間,O(max(nklog(nk),S(nk)))領域で求めるアルゴリズムを提案する.さらにL_1距離のもとでの点集合の最短経路をO(nklog^2(nk))時間,O(nklog(nk))領域で,ユークリッド距離のもとでの点集合の最短経路をO(n^2k^2)領域で求めることができることを示す.
一般社団法人情報処理学会の論文
1994-05-13

著者

関連論文

もっと見る

スポンサーリンク