How to get close to the median shape

Sariel Har-Peled
Computational Geometry
Volume 36, Issue 1 , January 2007, Pages 39-51
http://dx.doi.org/10.1016/j.comgeo.2006.02.003

いわゆる「コアセット」(coreset) の論文．
例えば，与えられた複数の点からの距離の和を最小にするような球面を求める問題などに対する1+ε近似アルゴリズムを与えている．
コアセットに基づくアルゴリズムの一般論に従った設計なので，当然のようにアレンジメントを使っている．