指定母点に対するボロノイ領域の高能率算出アルゴリズム

情報処理学会

書誌事項

タイトル別名
  • A Fast Algorithm Generating a Voronoi Polygon from a Specified Site

この論文をさがす

抄録

空間中の点群に対し、ある点を最近点とする領域をボロノイ領域と呼び、その点を領域の母点という。また、空間をボロノイ領域によって分けることをボロノイ分割という。ボロノイ分割は隣接関係の自然な定義である。ボロノイ分割を効率良く行なう算法については、従来様々な提案がなされているが、ある点のボロノイ領域だけを求める算法についての提案は少ない。これは、一つ一つのボロノイ領域を求めてボロノイ線図を作成するより、全ての点に対するボロノイ線図を直接求める方が、計算量が少なくてすむためである。しかし多数のデータのうち、少数のデータの隣接データを検索するような要求が多い汎用データベースで利用するには、常に最新のボロノイ線図を記憶しておかなくてはならない算法はメモリ効率の点から実用的ではない。そこで、汎用多次元データ構造上で、指定された母点に対応するボロノイ領域だけを平均O(log^2N)の計算手間で求める算法を提案する。

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ