多角形包含を決定する問題について
スポンサーリンク
概要
- 論文の詳細を見る
ここでは私は移動できる全領域を構成しないで、多角形Pを別の固定された多角形Qの中へ移動できるかどうかを決定する問題を考える。私は一般的な場合すなわち、PとQが任意の単純多角形の場合)とPとQがレクトリニアルの場合についてアルゴリズムを与える。単純多角形のときはO(n^2m^2)時間O(nm)記憶量でレクトリニアルのときはO(nm log nm)時間、O(nm)記憶量である。ここで、nはQの頂点の数で、mはPの頂点の数である。
- 一般社団法人情報処理学会の論文
- 1995-09-21