TY - JOUR

T1 - How to get close to the median shape

AU - Har-Peled, Sariel

N1 - Funding Information:
✩ Alternative titles for this paper include: “How to stay connected with your inner circle” and “How to compute one circle to rule them all”. The latest version of this paper is available from [S. Har-Peled, How to get close to the median shape, http://www.uiuc.edu/~sariel/papers/05/l1_fitting/, 2006]. E-mail address: sariel@uiuc.edu (S. Har-Peled). 1 Work on this paper was partially supported by an NSF CAREER award CCR-0132901.

PY - 2007/1

Y1 - 2007/1

N2 - In this paper, we study the problem of L1-fitting a shape to a set of n points in R d (where d is a fixed constant), 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 for such a problem, with running time O(n+poly(logn,1/)), where poly(logn,1/) is a polynomial of constant degree of logn and 1/ (the power of the polynomial is a function of d). This is a linear time algorithm for a fixed >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 when minimizing the sum of distances (or squared distances) to the respective shape.

AB - In this paper, we study the problem of L1-fitting a shape to a set of n points in R d (where d is a fixed constant), 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 for such a problem, with running time O(n+poly(logn,1/)), where poly(logn,1/) is a polynomial of constant degree of logn and 1/ (the power of the polynomial is a function of d). This is a linear time algorithm for a fixed >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 when minimizing the sum of distances (or squared distances) to the respective shape.

KW - Approximation algorithms

KW - Shape fitting

UR - http://www.scopus.com/inward/record.url?scp=84867921047&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867921047&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2006.02.003

DO - 10.1016/j.comgeo.2006.02.003

M3 - Article

AN - SCOPUS:84867921047

SN - 0925-7721

VL - 36

SP - 39

EP - 51

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 1

ER -