Computing constrained minimum-width annuli of point sets
Mark de Berg, Prosenjit K. Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong · Computer-Aided Design · 1998
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.