著者

渕田 孝康 森 邦彦 村島 定行

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.83, no.9, pp.927-935, 2000-09-25

被引用文献数

10

---

2次元離散平面上に存在する互いに重複しない一般図形を生成元とする離散ボロノイ図を, 波面法を用いて高速に作成する手法を提案する.波面法は, 離散平面内に一様ダンラムに母点が存在する場合, 母点数によらずほぼ一定時間で離散ボロノイ図を作成するアルゴリズムであり, 一般図形を母点とする場合でも, 全く変更しないで適用可能である.しかし, 一般図形を構成するすべての点を母点とみなして波面法を適用すると, 領域拡大の判定時に重複する領域が多く, 無駄な処理時間を要してしまう.本論文ではこの無駄を省き, 一般図形ボロノイ図をより効果的に波面法で作成するアルゴリズムを提案する.また, 計算機シミュレーションにより, その有効性を確認する.