A-007
最遠点ボロノイ図の作図手法に関する研究

◎堤　建介・鹿嶋雅之・福元伸也・佐藤公則・渡邊　睦（鹿児島大）

ボロノイ図は, 空間上に配置された複数個の母点からの距離を基に領域分割を行った図であり, 最適施設配置や小学校の校区の設定, 画像処理など, 様々な分野で応用されている. また, ボロノイ図については様々な種類と作図手法が存在するが, その中でも最遠点ボロノイ図に関しては作図手法が確立されていない. 最遠点ボロノイ図の作図手法に関する研究として, 逐次添加法を用いて作図する研究がある.しかし, この研究では, はじめに凸包上の3点を母点とする最遠点ボロノイ図が準備されていることと追加していく母点は凸包上になるように配置するという条件がある. 本研究では, そのような条件のない最遠点ボロノイ図の新しい作図手法を提案する. また, 全探索法と提案手法の作図結果, 作図計算時間の比較を行い, 新しい作図手法の有用性を検証する.