An Efficient Geometric Solution to the Minimum Spanning Circle Problem

B. John Oommen
Additional contact information
B. John Oommen: Carleton University, Ottawa, Ontario, Canada

Operations Research, 1987, vol. 35, issue 1, 80-86

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 (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.1.80 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:35:y:1987:i:1:p:80-86

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().