入力誤差を反映したボロノイ領域(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)

概要

論文の詳細を見る
計算幾何学の多くのアルゴリズムは入力数値に誤差がないことを暗に仮定しており, 現実世界から得られたデータのように誤差を含む入力に適用した場合, そのままでは意味のある出力を得ることができない.本研究では「各座標成分に誤差を含む点の集合」が入力に与えられる場合のボロノイ図について考察を行い, ボロノイ図そのものではなく各母点に対して「確実にその母点が最近点となる領域(強ボロノイ領域と呼ぶ)「その母点が最近点となり得る領域(弱ボロノイ領域と呼ぶ)」を構成するという手法を考案した.本論文では最適時O(nlog~*nlogn)時間, 最悪時O(n~2log~*nlogn)時間で強ボロノイ領域を構成するアルゴリズム, 最適時O(n~2α(n))時間, 最悪時O(n~3α(n))(α(n)はAckermann関数の逆関数)時間で弱ボロノイ領域を構成するアルゴリズムについて述べる.入力誤差を考慮したボロノイ領域を考えることにより, 最近点探索において「最近点となり得る母点の候補」を正しく答えたり, ボロノイ図の位相構造が入力誤差に対して安定であるかどうかを判定することができる.
2000-01-25