On the Least Median Square Problem

Jeff Erickson, Sariel Har-Peled and David M. Mount
Discrete and Computational Geometry
Volume 36, Number 4 / December, 2006
http://dx.doi.org/10.1007/s00454-006-1267-6
Pages 593-607

SoCG2004特集号から．
ロバスト統計に関する論文．
(ロバスト統計と計算幾何は関わりが深い．)

d次元空間に与えられたn個の点に対する線形回帰超平面を計算したいが，このとき点とその超平面の垂直誤差の2乗の中央値を最小にするものを考えたい．
これがleast median square問題である．

この問題に対して，乱択アルゴリズムを与えている．(乱数使用は計算幾何では当たり前の技法である．)
厳密アルゴリズム (つまりラスベガス型) は高確率でO(n^d log n)時間の計算量，
(1+ε)近似アルゴリズム (こちらはモンテカルロ型) は高確率でO(n^{d-1}/ε polylog n)時間の計算量を持つ．
また，問題をd次元点集合のアフィン従属性判定問題に帰着することでΩ(n^d)という計算量の下界を導いている．
(d次元点集合アフィン従属性判定がo(n^d)時間で解けるかどうかは重要な未解決問題．
2次元の場合はいわゆる3SUM-hard問題というもの．)

アルゴリズムで使われている技法は，まず双対変換でアレンジメントの問題に書き直すこと．
そして，厳密アルゴリズムの方は標本抽出，近似アルゴリズムはεネットを使っている．