誤差による破綻の心配のない線分 Voronoi 図構成算法
スポンサーリンク
概要
- 論文の詳細を見る
平面上の点の勢力圏を表す図であるVoronoi図を一般化することは,理論的に興味深いだけでなく,実用上も最要である.本論文では,線分Voronoi図の実用的な構成算法を考案する.この新しい算法は,従来の逐次添加型の算法に,位相優先法と我々が呼んでいる数値誤差対策を適用したものである.この算法は,計算誤差による破綻を完全に防止でき,必ず結果が出力される.さらに,出力が本来持つはずの位相的な性質のいくつかが保証される.単精度浮動小数点程度の誤差が発生する環境では,線分数nに対して,理論的に従来並みのο(n^2)の速度を確保することができ,最悪の場合でもο(n^3)時間で処理を終了する.記憶量はο(n)であり,理論的に最良である.また,算法を計算機上に実装し,実際には,さらに高速に計算できることも計算機実験で確かめた.
- 1994-10-15
著者
関連論文
- Crystal Voronoi Diagram and Its Applications (Algorithm Engineering as a New Paradigm)
- 乗法重みつき結晶成長ボロノイ図の近似構成法とその応用(多次元信号処理とその応用・実現論文小特集)
- NLC2000-13 構文情報の定量化とそれを用いた言語比較
- Voronoi図を用いた多次元データの補間 (新しいパラダイムとしてのアルゴリズム工学)
- 3次元単体メッシュ生成の課題 : 計算幾何学の立場から (数値計算における前処理の研究)
- 図形の可逆なミンコフスキー和の提案
- 図形のミンコフスキー和の逆演算は何か
- 部屋を実際より広く見せる写真術(応用数理の遊歩道(1))
- 誤差による破綻の心配のない線分 Voronoi 図構成算法
- 概念形成過程を観察するためのグラフ理論的一手法
- 制約つき3次元Delaunay図の構成算法
- 退化を許す3次元Delaunay図構成算法
- 3次元ボロノイ図構成のための数値的に安定な逐次添加法
- 検出もれのない代数曲線の追跡法
- 計算誤差があっても破綻しない線分交点列挙アルゴリズム
- 3.画像からの立体の認識(AI(人工知能)と画像技術)
- 計算誤差による暴走の心配のないソリッドモデラの提案
- 点ボロノイ図を利用した線分ボロノイ図の位相構造決定法
- 数値的に安定な分割統治型Voronoi図構成算法
- 自然造形物・工芸品における曲面の曲率線抽出とその性質分析
- ICIAM 99 Edinburgh報告 その2(学術会合報告)
- 平面グラフが凸図形のVoronoi図であることの確認法
- 剰余計算の並列化による誤差なし図形処理とその実装
- 幾何的アルゴリズムの簡易な退化解除法
- 多項式の符号判定のための剰余演算の利用法と計算幾何学への応用
- 組合せ構造を優先した多角形Voronoi図の構成法
- 剰余演算による多項式の符号判定と計算幾何学への応用
- 柔軟な対話制御機構を持ったコンサルテーション・システム