How to get close to the median shape (Q870425)

The author studies the problem of \(L_1\)-fitting a shape to a est of \(n\) points in \(\mathbb{R}^d\) (where \(d\) is a constant), the target is to minimize the sum of distances (or alternatively the sum of squared distances) of the points of the shape. A general technique for computing a \((1+\varepsilon)\)-approximation for such a problem with running time \(O(n+ p(\log n,{1\over \varepsilon}))\) is presented. The power of the polynomial \(p\) of constant degree of \(\log n\) and \({1\over\varepsilon}\) is a function of \(d\). This is a linear time algorithm for a fixed \(\varepsilon> 0\), and is the first subquadratic algorithm for this problem. Applications of the algorithm include best fitting either a circle, a sphere or a cylinder to a set of points minimizing the sum of distances (or squared distances) to the respective shape.