入力誤差を反映したボロノイ領域

スポンサーリンク

概要

論文の詳細を見る
計算幾何学の基本的な問題であるボロノイ図については従来から様々な研究が行なわれており, 生成元, 距離空間の一般化, 数値誤差対策など様々な研究結果が知られている.しかしながら, これらの手法では入力数値が正しいことを暗に仮定しており, 現実世界から得られた入力データに対してこれらの手法を適用した場合, 得られたボロノイ図をそのまま信用することはできない.本研究では入力に「各座標成分に誤差を含む点の集合」が与えられる場合のボロノイ図について考察を行ない, ボロノイ図そのものではなく, 各母点に対応するボロノイ領域を構成するという手法を考案した.入力数値の誤差を考慮したボロノイ領域を考えることにより, 例えば最近点探索において「最近点となりうる母点の候補」を正しく答えることができる.
1998-07-23

著者

関連論文

もっと見る

スポンサーリンク