ON ENCLOSING K-POINTS BY A CIRCLE

Authors
MATOUSEK J
Citation
J. Matousek, ON ENCLOSING K-POINTS BY A CIRCLE, Information processing letters, 53(4), 1995, pp. 217-221
Citations number
13
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
53
Issue
4
Year of publication
1995
Pages
217 - 221
Database
ISI
SICI code
0020-0190(1995)53:4<217:OEKBAC>2.0.ZU;2-6
Abstract
We consider the problem of finding, for a given n-point set P in the p lane and an integer k less than or equal to n, a smallest circle enclo sing at least k points of P. We present randomized algorithms with O(n k) space and O(n log n + nk) expected running time, resp. O(n) space a nd O(n log n + nk log k) time. This improves on previous results by lo garithmic factors, and our algorithms are simpler and easier to implem ent.