How to get close to the median shape (Q870425)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | How to get close to the median shape |
scientific article |
Statements
How to get close to the median shape (English)
0 references
12 March 2007
0 references
The author studies the problem of \(L_1\)-fitting a shape to a est of \(n\) points in \(\mathbb{R}^d\) (where \(d\) is a constant), the target is to minimize the sum of distances (or alternatively the sum of squared distances) of the points of the shape. A general technique for computing a \((1+\varepsilon)\)-approximation for such a problem with running time \(O(n+ p(\log n,{1\over \varepsilon}))\) is presented. The power of the polynomial \(p\) of constant degree of \(\log n\) and \({1\over\varepsilon}\) is a function of \(d\). This is a linear time algorithm for a fixed \(\varepsilon> 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 minimizing the sum of distances (or squared distances) to the respective shape.
0 references
approximation algorithms
0 references
shape fitting
0 references
linear time algorithm
0 references
best fitting
0 references
circle
0 references
sphere
0 references
cylinder
0 references
0 references
0 references