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

計算幾何学の分野においてVoronoi図は中心課題の一つである．通常のVoronoi図では，生成元が点であるが，生成元を線分や多角形などの一般図形にした一般化されたVoronoi図も存在する．一般化されたVoronoi図を求める際，点列近似の手法がよく使われる．この手法では，生成元が点であるときに用いるアルゴリズムを利用できるなどのメリットがあるが、生成元の辺上にとった多数の点を用いて計算を行うため計算時間がかかるデメリットもある．本研究では，生成元がBezier曲線のみで構成されるVoronoi図の生成元上の点の数を位相構造が崩壊しない程度まで減らし点列近似で求める．このとき，近似算法であるため計量情報の正しさは無視するが，位相情報の厳密性のみを保証し求める．