Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error (Q1186452)

The ANSI standards for Mechanical Engineering have a definition of roundness that is not well implemented by current engineering techniques. The problem is to find for any finite plane set of points two concentric circles so that the set is contained in the annular domain bounded by the circles and the difference of the radii is minimal. Current engineering practice has errors of up to 20\%. The authors use Voronoi diagrams for nearest and farthest points and the convex hull to present a (completely documented) exact computation of roundness of complexity \(O(n^ 2)\) that could eventually be improved to \(O(n\log n)\). A simple search would have complexity \(O(n^ 4)\).