3次元の点集合のL_1平面近似問題に対する線形時間アルゴリズム  [in Japanese] A Linear-Time Algorithm for Planar L_1 Approximation of Points in 3-Dimensional Space  [in Japanese]

統計や数値計算などにおける基本的な問題として、与えられた(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次元の場合では算法の手間が異なることに比べると、対照的である。