Bezier 曲線を生成元とするVoronoi 図の位相構造の決定

摘要

計算幾何学の中心課題の一つであるVoronoi 図は，母点の勢力圏を表す．Voronoi 図は，郵便局問題や移動可能ロボットの経路探索，都市工学において建物の密集度の測定など幅広い分野で使用されている．通常のVoronoi 図では，障害物を避けた経路探索などでは母点を線分や多角形などの一般図形にしたいという需要がある．母点を一般図形としたVoronoi 図を一般化Voronoi 図と呼び，母点のことを生成元と呼ぶこととする．一般化Voronoi 図を求める際，点列近似による手法がよく使用されている．この手法では，生成元となる一般図形の辺上に多数の点を隙間なく敷き詰めることにより求める．このような操作を行うことにより，生成元が点である場合のVoronoi 図のアルゴリズムを用いることができ，様々な多角形に対応する新たなアルゴリズムを考える必要がない．しかし，生成元上の多量な点で計算を行う必要があり，計算時間がかかるデメリットがある．そこで，一般化されたVoronoi図の位相構造のみを厳密に求めることにより，計算時間の高速化を図った手法がある．この手法における生成元を線分や円としたときのものはすでに研究されているため，本研究では，生成元をBezier 曲線としたときのVoronoi 図へと拡張する．