情報処理学会 第77回全国大会講演要旨

ボロノイ分割は地理情報システムやコンピュータグラフィクス，コンピュータビジョンなど2次元データを扱う分野で，解析や計画の為に用いられている．通常は，あるデータ点が最近接となる領域として定義されるが，複数の点が最近接である領域で分割する場合を高次ボロノイ分割と呼ぶ．このボロノイ分割は主としてユークリッド距離上で行われてきた．一方，道路網距離でのボロノイ領域をネットワークボロノイ分割と呼ぶ．ボロノイ分割は長い処理時間と保存の為の多くのデータ領域を必要とする．そこで，本稿では高次ネットワークボロノイ領域を逐次的に生成する方式を提案する．本稿ではアルゴリズムを提案し，実験的に評価する．