We study the problem of determining whether a manufactured disc 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(n log n) time.

Additional Metadata
Series Lecture Notes in Computer Science
Citation
de Berg, M. (Mark), Bose, P, Bremner, D. (David), Ramaswami, S. (Suneeta), & Wilfong, G. (Gordon). (1997). Computing constrained minimum-width annuli of point sets. In Lecture Notes in Computer Science.