単調多角形のMinkowski Sumの計算について
スポンサーリンク
概要
- 論文の詳細を見る
この論文では一群の問題に対する2つの多角形 PとQの Minkowski sum の計算に対するアルゴリズムを与える。凸多角形Pと単調多角形Qに対して、アルゴリズムはO(nm)時間とO(nm)記憶量で与えられる。単調多角形のPとQに対してはO(nm log nm)時間のアルゴリズムが与えられる。Minkowski sum の複雑さは最大の場合、θ(nmα(min(n,m)))である。ここでα(・)は Ackermann 関数の逆数である。最後にPが単調多角形で、Qが単純のとき、O((nm+k)log nm)アルゴリズムが与えられる。ここで最大の場合のkはθ(n^2m)となり得る。mとnはPとQのそれぞれのエッジの数である。
- 一般社団法人情報処理学会の論文
- 1996-03-15