離散ボロノイ図における母点の追加と削除のアルゴリズム

概要

論文の詳細を見る
離散平面上に作成されたボロノイ図に, 一つの母点を追加または削除して, 新しい離散ボロノイ図を高速に作成するアルゴリズムを提案する. 離散平面上に高速にボロノイ図を作成する方法である波面法は, 離散平面の大きさが一定ならば母点数によらずほぼ一定時間で離散ボロノイ図を作成できるアルゴリズムであるが, 白紙の状態からボロノイ図全体を作成するアルゴリズムであった. 本論文では, 追加する母点の周囲の最小限の領域を波面法を利用して更新することにより, 既に作成されている離散ボロノイ図に, 高速に母点を追加するアルゴリズムを提案する. また, 母点の削除には波面法アルゴリズムを用いた方法と, 全探索法を用いた方法の二つを提案する. 計算機シミュレーションの結果, 母点が離散平面にランダムに分布している場合, 離散平面の大きさや母点数にかかわらず, 波面法よりも全探索法で削除した方が高速であることを示す. 更に, 離散平面の大きさと母点数を変化させて計算機シミュレーションを行うことにより, 提案する追加・削除アルゴリズムの有効性を確認する.
社団法人電子情報通信学会の論文
2001-08-01