loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Thomas Martinetz, University of Lubeck, Germany
Amir Madany Mamlouk, University of Lubeck, Germany
Cicero Mota, Universidade Federal do Amazonas, Brazil
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.