`%0 Conference Proceedings`

`%4 sid.inpe.br/sibgrapi@80/2006/08.16.16.48`

`%2 sid.inpe.br/sibgrapi@80/2006/08.16.16.48.53`

`%A Martinetz, Thomas,`

`%A Madany Mamlouk, Amir,`

`%A Mota, Cicero,`

`%@affiliation Institute for Neuro- and Bioinformatics, University of L uebeck`

`%@affiliation Institute for Neuro- and Bioinformatics, University of L uebeck`

`%@affiliation Departamento de Matemática, Universidade Federal do Amazonas`

`%T Fast and Easy Computation of Approximate Smallest Enclosing Balls`

`%B Brazilian Symposium on Computer Graphics and Image Processing, 19 (SIBGRAPI)`

`%D 2006`

`%E Oliveira Neto, Manuel Menezes de,`

`%E Carceroni, Rodrigo Lima,`

`%S Proceedings`

`%8 8-11 Oct. 2006`

`%J Los Alamitos`

`%I IEEE Computer Society`

`%C Manaus`

`%K computational geometry, smallest enclosing ball, pattern recognition.`

`%X The incremental Badoiu-Clarkson algorithm finds the smallest ball enclosing n point in d dimensions with at least O(1/t^0.5) 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{(2d)^0.5,(2n)^0.5}. If it holds, then the algorithm finds the smallest enclosing ball with epsilon precision in at most O(nd (d')^0.5 }/epsilon) time, with d=min{d,n}.`

`%@language en`

`%3 MotaC_SmallestEnclosingBalls.pdf`