TY - GEN
T1 - How to get close to the median shape
AU - Har-Peled, Sariel
PY - 2006
Y1 - 2006
N2 - In this paper, we study the problem of Li-fitting a shape to a set of n points in ℝ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(log n, 1/ε)), where poly(log n, 1/ε) is a polynomial of constant degree of log n 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 Li-fitting a shape to a set of n points in ℝ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(log n, 1/ε)), where poly(log n, 1/ε) is a polynomial of constant degree of log n 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
KW - Shape fitting
UR - http://www.scopus.com/inward/record.url?scp=33748051724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748051724&partnerID=8YFLogxK
U2 - 10.1145/1137856.1137915
DO - 10.1145/1137856.1137915
M3 - Conference contribution
AN - SCOPUS:33748051724
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 402
EP - 410
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PB - Association for Computing Machinery
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -