Close
Metadata

@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"
}


Close