Technical Report CIS9309

Authors: A. Efrat, M. Sharir and A. Ziv
PDFNot Available

We present an efficient algorithm for solving the ``smallest k-enclosing circle'' (kSC) problem: Given a set of n points in the plane and an integer k \leq n, find the smallest disk containing k of the points. We present several algorithms that run in O(n k \log^c n) time, where the constant c depends on the storage that the algorithm is allowed. When using O(nk) storage, the problem can be solved in time O(n k \log^2 n). When only O(n \log n) storage is allowed, the running time is O(n k \log^2 n \log \frac{n}{k}). This problem can also be tackled using the k-th order Voronoi diagram of the given set. However, our method, which is based on the parametric searching paradigm, (i) is more efficient (the best known algorithm for constructing k-th order Voronoi diagrams takes time O(n^{1+\epsilon}k), for any \epsilon > 0), (ii) is simpler, (iii) yields a storage-efficient version (as mentioned above), and (iv) can be easily extended to obtain efficient solutions of several related problems (with similar time and storage bounds). These related problems include: finding the smallest homothetic copy of a given convex polygon P, which contains k points from a given planar set, and finding the smallest hypodrome of a given length and orientation (formally defined in Section 4) containing k points from a given planar set.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion