We study the problem of determining whether a manufactured disk of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of the manufactured object, compute the thinnest annulus whose outer (or inner, or median) radius is r and that contains all the probe points. Our algorithms run in O(nlogn) time.

CAD Computer Aided Design
School of Computer Science

De Berg, M. (Mark), Bose, P, Bremner, D. (David), Ramaswami, S. (Suneeta), & Wilfong, G. (Gordon). (1998). Computing constrained minimum-width annuli of point sets. CAD Computer Aided Design, 30(4), 267–275. doi:10.1016/S0010-4485(97)00073-0