In this paper, we study the problem of L1-fitting
a shape to a set of point, where the target is to minimize the
sum of distances of the points to the shape, or alternatively
the sum of squared distances. We present a general technique
for computing a (1+µ)-approximation, with running
time O(n + \poly( log n, 1/µ)), where \poly( log
n, 1/µ) is polynomial of constant degree of log n
and 1/µ. This is the first subquadratic algorithm
for this problem.
Applications of our algorithm include
best fitting either a circle, a sphere or a cylinder to a set
of points when minimizing the sum of distances(or squared distances)
to the respective shape.