XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'06) Fast and Easy Computation of Approximate Smallest Enclosing Balls Manaus, AM, Brazil October 08-October 11 ISBN: 0-7695-2686-1
The incremental Badoiu-Clarkson algorithm finds the smallest ball enclosing n points in d dimensions with at least O(1/pt) 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{p2d,p2n}. If it holds, then the algorithm finds the smallest enclosing ball with precision in at most O(ndpdm/) time, with dm = min{d, n}.
Citation:
Thomas Martinetz, Amir Madany Mamlouk, Cicero Mota, "Fast and Easy Computation of Approximate Smallest Enclosing Balls," sibgrapi, pp.163-170, XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||