Abstract.
Given a set of points S={p 1 ,. . ., p n } in Euclidean d -dimensional space, we address the problem of computing the d -dimensional annulus of smallest width containing the set. We give a complete characterization of the centers of annuli which are locally minimal in arbitrary dimension and we show that, for d=2 , a locally minimal annulus has two points on the inner circle and two points on the outer circle that interlace anglewise as seen from the center of the annulus. Using this characterization, we show that, given a circular order of the points, there is at most one locally minimal annulus consistent with that order and it can be computed in time O(n log n) using a simple algorithm. Furthermore, when points are in convex position, the problem can be solved in optimal Θ(n) time.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received June 25, 1997, and in revised form March 5, 1998.
Rights and permissions
About this article
Cite this article
García-López, J., Ramos, P. & Snoeyink, J. Fitting a Set of Points by a Circle . Discrete Comput Geom 20, 389–402 (1998). https://doi.org/10.1007/PL00009392
Issue Date:
DOI: https://doi.org/10.1007/PL00009392