An Algorithm for Computing the Minimum Covering Sphere in Any Dimension
Ted Hopp, C Reeve · 1989
An algorithm is presented for computing the minimum covering sphere for a set of n points in d-dimensional space (0 < n, d < #). The steps of the geometric construction can readily be programmed for a computer. In the worst case, with all the points near the sphere surface, the expected computing time is estimated at O(nd ). 2.3 Key words: algorithm; computational geometry; covering sphere; minimax fit; minimum covering sphere; surface fitting 1 Introduction One tool needed in automated manufacturing work at the National Institute of Standards and Technology (NIST) is an algorithm for computing the sphere of minimum radius covering a set of points in three dimensions. The equivalent problem in two dimensions was first posed by Sylvester [11] in 1857. Recent publications by Megiddo [6], Dyer [1], and Preparata and Shamos [8] also address the two-dimensional case. Lawson [5] gives a compact iterative algorithm for solving the three-dimensional case. It is appealing in its simplicity,...