FITTING A SET OF POINTS BY A CIRCLE

Given a set of points S = {p(1),...,p(n)} in Euclidean d-dimensional s pace, we address the problem of computing the d-dimensional annulus of smallest width containing the set. We give a complete characterizatio n of the centers of annuli which are locally minimal in arbitrary dime nsion and we show that, for d = 2, a locally minimal annulus has two p oints on the inner circle and two points on the outer circle that inte rlace anglewise as seen from the center of the annulus. Using this cha racterization, we show that, given a circular order of the points, the re is at most one locally minimal annulus consistent with that order a nd it can be computed in time O(n log n) using a simple algorithm. Fur thermore, when points are in convex position the problem can be solved in optimal Theta(n) time.