3次元の点集合のL_1平面近似問題に対する線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
統計や数値計算などにおける基本的な問題として、与えられた(x,y,z)空間内のn個の点pi=(Xi,yi,zi)(i=1,...,n)を平面(z=ax+by+c)で近似する問題がある。近似方法の代表的なものとして最小2乗法、チェビシェフ法(L_∞法)、L_1近似法などがよく用いられる。これらの方法にはそれぞれ得失があるが、適当な統計モデルの下で誤差の分散を最小にでき、O(n)の手間で簡単に計算できるという理由から最小2乗法が一般的に用いられている。しかし、与えられた点の中に特異点が存在するような場合には、より頑健な近似方法であるL_1近似法が用いられることが多い。L_1近似法とは、次の式で定義されるL_1ノルムL(a,b,c)を最小にする(a,b,c)を求める方法である。L(a,b,c)=Σ^^n__<i=1>|zi-(ax_i+by_i+c)|……(1) Yamamoto,Kato,Imai,Imaiは、2次元の点集合に対するL_1直線近似問題に対しO(n)の手間の算法を示している。その算法は、手法的にはMegiddoの多次元順次縮小法を用い、さらにそれを発展させたものである。本稿では2次元の算法を拡張していくことにより3次元の点集合に対するL_1平面近似問題がやはりO(n)の手間で計算できることを示す。多くの問題が2次元の場合と3次元の場合では算法の手間が異なることに比べると、対照的である。
- 一般社団法人情報処理学会の論文
- 1988-09-12
著者
関連論文
- 利用者インターフェースとしての文字自動配置機能(計算アルゴリズムと計算量の基礎理論)
- 3次元の点集合のL_1平面近似問題に対する線形時間アルゴリズム
- 既存のCADシステムに対する設計データベース機能の追加について
- 文字の可読性を考慮した対話的地図表示機能
- 計算幾何学と折れ線近似問題
- 3次元空間に与えられた2次元集合間のマッチングについて
- 拡大縮小を考慮した点集合の正方格子度を求めるアルゴリズム
- 凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図(アルゴリズムと計算量の理論)
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- 重み付きL_∞距離Voronoi図の構成と文字配置問題
- 連結性を考慮した近似折れ線による曲線の階層管理
- 内点法の平面ネットワークフロー問題への適用(アルゴリズムと計算量の理論)
- 線形計画法の新解法について
- 線形計画法と計算の複雑さ
- 線形計画問題に対する乗法的罰金関数法について(線形計画法の最近の発展)