# Technical Report CIS9309

 TR#: CIS9309 Class: CIS Title: COMPUTING THE SMALLEST k-ENCLOSING CIRCLE AND RELATED PROBLEMS. Authors: A. Efrat, M. Sharir and A. Ziv PDF Not Available Abstract: 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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CIS/CIS9309), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.