平面グラフが凸図形のVoronoi図であることの確認法
スポンサーリンク
概要
- 論文の詳細を見る
図形処理において, 近似アルゴリズムの実装や, 厳密アルゴリズムの計算誤差のある実装では, 出力図形が正しいかどうかはわからない.点のVoronoi図の構成においては, 点のVoronoi図の双対であるDelaunay図に関する定理があり, それを用いて局所的な判定で真のVoronoi図であるか確認できる.本稿では, この定理を拡張し凸図形のVoronoi図の構成に適用できるようにし, その証明を与える.この定理により, 凸図形のVoronoi図に構成に関して, 近似アルゴリズムを利用して厳密解をもとめられるようになる.
- 一般社団法人情報処理学会の論文
- 2005-01-20
著者
関連論文
- 図形の可逆なミンコフスキー和の提案
- 図形のミンコフスキー和の逆演算は何か
- 誤差による破綻の心配のない線分 Voronoi 図構成算法
- 点ボロノイ図を利用した線分ボロノイ図の位相構造決定法
- 自然造形物・工芸品における曲面の曲率線抽出とその性質分析
- ICIAM 99 Edinburgh報告 その2(学術会合報告)
- 平面グラフが凸図形のVoronoi図であることの確認法
- 剰余計算の並列化による誤差なし図形処理とその実装
- 幾何的アルゴリズムの簡易な退化解除法
- 多項式の符号判定のための剰余演算の利用法と計算幾何学への応用
- 組合せ構造を優先した多角形Voronoi図の構成法
- 剰余演算による多項式の符号判定と計算幾何学への応用