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 -