多角形内での2-リンクアームの到達可能性判定問題

スポンサーリンク

概要

論文の詳細を見る
k-リンクアームはリンクと呼ばれるk本の互いに接続された線分より構成される. 本論文では, n頂点単純多角形内での2-リンクアームの任意の2状態が与えられたとき, この2状態が互いに到達可能かどうかを判定する問題を, 判定グラフを構成することにより解く手法を提案する. 判定グラフは2-リンクアームの動作が制限される状態に着目し, 2-リンクアームの状態をO(n^2)個の節点で表したグラフであり, O(n^2)時間, O(n^2)領域で構成できることを示す. 判定グラフ構成後, 2-リンクアームの2状態が与えられたとき, O(n)時間で到達可能性の判定ができることを示す. また, n頂点凸多角形内の2-リンクアームに関して同様の問題が, O(n^2)時間, O(n^2)領域の前処理で, 質問当りO(logn)時間で解くことができることを示す.
社団法人電子情報通信学会の論文
1997-04-25

著者

関連論文

もっと見る

スポンサーリンク