包含多角形列の計算手法とその実験的解析

概要

論文の詳細を見る
我々はこれまで包含多角形列の計算手法について研究をおこなってきた.前の論文で,凸多角形に対する2つの手法:最適法と貪欲法という構成法を提案した.前者は最適なk多角形を順に計算するものであり,後者は最適に近いk多角形(k≧5の場合)を省メモリで高速に計算する手法であった.本稿では,単純多角形に対する包含多角形列の計算手法:ナイーブ法とポケット法について述べる.これらの手法は,以前の研究でよい性能をあげた貪欲法を元にしたものであり,これらの手法の最悪計算量は,n頂点を持つ単純多角形の場合,O(n^2)時間とO(n)領域である.ポケット法は平均時間計算量の解析ができ,単純多角形の頂点が正方形領域から一様に選ばれた場合はO(n^2/log n)時間であり,円盤領域から選ばれた場合はO(n^<5/3>)時間であること示す.また,これらの手法を実装し,単純多角形の集合に適用したところ,ナイーブ法はO(n^2)時間,ポケット法はO(n^2/log n)時間(正方形領域),O(n^<5/3>)時間(円盤領域)となったことについても述べる.
2012-06-14