Smallest Circle Problem - Other Algorithms

Other Algorithms

Prior to Megiddo's result showing that the smallest-circle problem may be solved in linear time, several effective algorithms of higher (worst case) complexity appeared in the literature. A naive algorithm solves the problem in time O(n4) by testing the circles determined by all pairs and triples of points.

• An algorithm of Chrystal and Peirce applies a local optimization strategy that maintains two points on the boundary of an enclosing circle and repeatedly shrinks the circle, replacing the pair of boundary points, until an optimal circle is found. Chakraborty and Chaudhuri propose a linear-time method for selecting a suitable initial circle and a pair of boundary points on that circle. Each step of the algorithm includes as one of the two boundary points a new vertex of the convex hull, so if the hull has h vertices this method can be implemented to run in time O(nh).
• Elzinga and Hearn described an algorithm which maintains a covering circle for a subset of the points. At each step, a point not covered by the current sphere is used to find a larger sphere that covers a new subset of points, including the point found. Although its worst case running time is O(h3n), the authors report that it ran in linear time in their experiments. The complexity of the method has been analyzed by Drezner and Shelah. Both Fortran and C codes are available, see the ORSEP article.
• The smallest sphere problem can be formulated as a quadratic program defined by a system of linear constraints with a convex quadratic objective function. Therefore, any feasible direction algorithm can give the solution of the problem. Hearn and Vijay proved that the feasible direction approach chosen by Jacobsen is equivalent to the Chrystal–Peirce algorithm.
• The dual to this quadratic program may also be formulated explicitly; an algorithm of Lawson can be described in this way as a primal dual algorithm.
• Shamos and Hoey proposed an O(n log n) time algorithm for the problem based on the observation that the center of the smallest enclosing circle must be a vertex of the farthest-point Voronoi diagram of the input point set.