Fast Algorithms for Computing the Smallest k-Enclosing Disc

Sariel Har-Peled and Soham Mazumdar

Since this problem is believed to require Omega(n k) time, we present a linear time µ-approximation algorithm that outputs a circle that contains at least k points of P, and of radius less than (1+ µ)ropt(P,k), where ropt(P,k) is the radius of the minimal disk containing at least k points of P. The expected running time of this approximation algorithm is O(n + n * min( [1/(k µ³)] log²1/µ, k)).

Postscript, PDF.

@string{ALGORITHMICA = "Algorithmica"}

@article{hm-facsk-05,
  keyent       = {hm-facsk-05},
  author       = {S. {Har-Peled} and S.~{Mazumdar}},
  title        = {Fast Algorithms for Computing the Smallest
                  $k$-Enclosing Disc},
  journal      = ALGORITHMICA,
  year         = 2005,
  pages        = "147--157",
  Volume       = {41}, 
  Number       = {3},
  url          = {http://www.uiuc.edu/~sariel/papers/03/min_disk/}
}


@string{ESA_2003 = "Proc. 11th Annu. European Sympos. Algorithms"}

@inproceedings{hm-acsk-03,
  author       = {S. {Har-Peled} and S.~{Mazumdar}},
  title        = {Fast Algorithms for Computing the Smallest
                  $k$-Enclosing Disc},
  booktitle    = ESA_2003,
  series       = LNCS,
  volume       = 2832,
  publisher    = "Springer-Verlag",
  year         = 2003,
  pages        = "278--288"
}