Approximation algorithm for the L1-fitting circle problem.
Sariel Har-Peled · 2005
In this paper, we study the problem of L1-fitting a circle to a set of points in the plane, where the target function is the sum of distances of the points to the circle. We show an (1 + ε)-approximation algorithm, with running time O(n + poly(log n, 1/ε)), where poly(log n, 1/ε) is a constant degree polynomial in log n and 1/ε. This is the first subquadratic algorithm for this problem. 1