An Efficient Geometric Solution to the Minimum Spanning Circle Problem
Operations Research · 1987 · Volume 35 · Issue 1
Abstract
We consider the century-old problem of finding the minimum spanning circle (MSC) of N points in the plane. We propose a computational scheme that incorporates the ideas that motivate three of the best-known primal feasible algorithms. The technique converges in finite time and is extremely fast. In all our experiments that involved digitized and random data, without even a rare exception, the technique converged in exactly two iterations. We conjecture that the algorithm, which is purely geometric, has a linear time complexity.
Keywords
185 minimax location problem, 655 Chrystal-Peirce algorithm
Enable JavaScript for citation tools and additional paper interactions.