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.

Additional Metadata
Persistent URL dx.doi.org/10.1016/S0010-4485(97)00073-0
Journal CAD Computer Aided Design
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