Fast algorithms for computing the smallest k-enclosing disc

Sariel Har-Peled; Soham Mazumdar

doi:10.1007/978-3-540-39658-1_27

Fast algorithms for computing the smallest k-enclosing disc

Sariel Har-Peled, Soham Mazumdar

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

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 + δ)r_opt(P, k), where r_opt(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)).

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Giuseppe di Battista, Uri Zwick
Publisher	Springer
Pages	278-288
Number of pages	11
ISBN (Print)	3540200649, 9783540200642
DOIs	https://doi.org/10.1007/978-3-540-39658-1_27
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2832
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

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

Library availability

Discover UIUC Full Text

Cite this

Har-Peled, S., & Mazumdar, S. (2003). Fast algorithms for computing the smallest k-enclosing disc. In G. di Battista, & U. Zwick (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 278-288). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832). Springer. https://doi.org/10.1007/978-3-540-39658-1_27

Fast algorithms for computing the smallest k-enclosing disc. / Har-Peled, Sariel; Mazumdar, Soham.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Giuseppe di Battista; Uri Zwick. Springer, 2003. p. 278-288 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Har-Peled, S & Mazumdar, S 2003, Fast algorithms for computing the smallest k-enclosing disc. in G di Battista & U Zwick (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2832, Springer, pp. 278-288. https://doi.org/10.1007/978-3-540-39658-1_27

Har-Peled S, Mazumdar S. Fast algorithms for computing the smallest k-enclosing disc. In di Battista G, Zwick U, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer. 2003. p. 278-288. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-39658-1_27

Har-Peled, Sariel ; Mazumdar, Soham. / Fast algorithms for computing the smallest k-enclosing disc. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Giuseppe di Battista ; Uri Zwick. Springer, 2003. pp. 278-288 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{eb80ec622cab4686b47041e8942cd110,

title = "Fast algorithms for computing the smallest k-enclosing disc",

abstract = "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)).",

author = "Sariel Har-Peled and Soham Mazumdar",

year = "2003",

doi = "10.1007/978-3-540-39658-1_27",

language = "English (US)",

isbn = "3540200649",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "278--288",

editor = "{di Battista}, Giuseppe and Uri Zwick",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

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

ER -

Fast algorithms for computing the smallest k-enclosing disc

Abstract

Publication series

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this