計算誤差があっても破綻しない線分交点列挙アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• 平面上の線分の交点の列挙は、CAD、地理情報処理など、広い範囲で応用される重要な問題である。平面上にn本の線分が与えられたとき、それらの間の交点をすべて求めるには、素朴な算法で、O(n^2)の時間が必要である。BentlayとOttmannは、kを交点の数として、O((n+k)log n)の時間で求められるアルゴリズムを示した。しかし、このアルゴリズムがすべての交点を求めることが保証されているのは、計算誤差が存在しない場合のみであり、計算誤差が存在すると、交点を見落としたり、計算中に矛盾が生じて破綻する可能性がある。本論文では、O((n+k)log n)という時間を変えることなく、計算中にデータの矛盾を生じないことを保証するアルゴリズムの構成を試るとともに、見落とす可能性のある交点の性質を考察する。

• 1989-10-16

著者

• 金沢 裕治

  東京大学工学部

• 杉原 厚吉

  東京大学工学部計数工学科

関連論文

• 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図構成算法
• 柔軟な対話制御機構を持ったコンサルテーション・システム

もっと見る 閉じる

スポンサーリンク