Name
Abstract | ||
|---|---|---|
The incremental Badoiu-Clarkson algorithm finds the smallest ball enclosing n points in d dimensions with at least O(1/root t) precision, after t iteration steps. The extremely simple incremental step of the algorithm makes it very attractive both for theoreticians and practitioners. A simplified proof for this convergence is given. This proof allows to show that the precision increases, in fact, even as O(u/t) with the number of iteration steps. Computer experiments, but not yet a proof suggest that the u, which depends only on the data instance, is actually bounded by min {root 2d, root 2n}. If it holds, then the algorithm finds the smallest enclosing ball with c precision in at most O(nd root d(m)/is an element of) time, with d(m) = min{d,n}. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/SIBGRAPI.2006.20 | SIBGRAPI - Brazilian Symposium on Computer Graphics and Image Processing |
Keywords | Field | DocType |
computational geometry,smallest enclosing ball,pattern recognition | Convergence (routing),Computer experiment,Combinatorics,Ball (bearing),Computational geometry,Mathematics,Computational complexity theory,Computation,Bounded function | Conference |
ISSN | Citations | PageRank |
1530-1834 | 1 | 0.40 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Martinetz | 1 | 1462 | 231.48 |
| Amir Madany Mamlouk | 2 | 37 | 9.52 |
| Cicero Mota | 3 | 72 | 8.44 |