Home Bookmarks Papers Blog

How to Get Close to the Median Shape

Sariel Har-Peled.

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.


SoCG talk: slides and source.
SoCG submission: 8pt, 10pt, 12pt, 20pt,
Last modified: Thu Jun 8 09:34:55 CDT 2006