TR#:  CIS9309 
Class:  CIS 
Title:  COMPUTING THE SMALLEST
kENCLOSING CIRCLE AND RELATED PROBLEMS. 
Authors:  A. Efrat, M. Sharir and A. Ziv 
Not Available  
Abstract: 
We present an efficient algorithm for solving the ``smallest kenclosing 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 kth 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 kth order Voronoi diagrams takes time O(n^{1+\epsilon}k), for any \epsilon > 0), (ii) is simpler, (iii) yields a storageefficient 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/cgibin/trinfo.cgi/1993/CIS/CIS9309), 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