TY - CHAP

T1 - Fast algorithms for computing the smallest k-enclosing disc

AU - Har-Peled, Sariel

AU - Mazumdar, Soham

PY - 2003

Y1 - 2003

N2 - We consider the problem of finding, for a given n point set P in the plane and an integer k ≤ n, the smallest circle enclosing at least k points of P. We present a randomized algorithm that computes in O (nk) expected time such a circle, improving over all previously known algorithms. Since this problem is believed to require Ω(nk) 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δ3 log2 1/δ, k)).

AB - We consider the problem of finding, for a given n point set P in the plane and an integer k ≤ n, the smallest circle enclosing at least k points of P. We present a randomized algorithm that computes in O (nk) expected time such a circle, improving over all previously known algorithms. Since this problem is believed to require Ω(nk) 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δ3 log2 1/δ, k)).

UR - http://www.scopus.com/inward/record.url?scp=0142183803&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0142183803&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-39658-1_27

DO - 10.1007/978-3-540-39658-1_27

M3 - Chapter

AN - SCOPUS:0142183803

SN - 3540200649

SN - 9783540200642

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 278

EP - 288

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - di Battista, Giuseppe

A2 - Zwick, Uri

PB - Springer-Verlag Berlin Heidelberg

ER -