@InProceedings{MartinetzMadaMota:2006:FaEaCo,
author = "Martinetz, Thomas and Madany Mamlouk, Amir and Mota, Cicero",
affiliation = "Institute for Neuro- and Bioinformatics, University of L uebeck
and Institute for Neuro- and Bioinformatics, University of L
uebeck and Departamento de Matem{\'a}tica, Universidade Federal
do Amazonas",
title = "Fast and Easy Computation of Approximate Smallest Enclosing
Balls",
booktitle = "Proceedings...",
year = "2006",
editor = "Oliveira Neto, Manuel Menezes de and Carceroni, Rodrigo Lima",
organization = "Brazilian Symposium on Computer Graphics and Image Processing, 19.
(SIBGRAPI)",
publisher = "IEEE Computer Society",
address = "Los Alamitos",
keywords = "computational geometry, smallest enclosing ball, pattern
recognition.",
abstract = "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}.",
conference-location = "Manaus",
conference-year = "8-11 Oct. 2006",
language = "en",
targetfile = "MotaC_SmallestEnclosingBalls.pdf",
urlaccessdate = "2020, Nov. 24"
}