When using a coordinate measuring machine (CMM) to ascertain, say, circularity (or sphericity) within a prescribed tolerance, one needs to find a suitable annulus, that is, the region inside the larger and outside the smaller of two concentric circles that enclose the measured data points. If the distance between the bounding circles exceeds tolerance, then the circularity test has failed. A linear-programming approach to finding the smallest annulus is proposed.
Much of the Nation's manufacturing industry depends on the availability of accurate coordinate measurements. The Mechanical Engineering Laboratory of NIST has been pivotal in examining CMM performance and in issuing guidelines for their proper use. ACMD can contribute to this effort through its expertise in optimization and computational geometry techniques.
Finding the minimum annulus is a nonlinear-programming problem. It is not convex so that local minima need not be global. A complicated computational-geometric procedure avoids that difficulty but requires the examination of all intersections of the closest and farthest point Voronoi diagrams, respectively, of the data points.
The minimum annulus problem requires finding the circle which best fits given points in the sense of Chebychev: minimize the maximum orthogonal distance from the circle. The Chebychev necessary optimality condition for an enclosing annulus requires that four of the data points occupy the bounding circles, limiting potential solutions to a finite set.
The same necessary optimality condition holds for a slightly modified problem: minimize the maximum squared orthogonal distance. This problem turns out to have a straightforward linear-programming solution which obviates the examination of local minima. While examples can be constructed in which the actual minimum annulus and the ``squared" minimum annulus differ, they coincide in most observed instances derived from actual measurements. Analogous results were found for spherical fits. At the INFORMS conference in Washington, DC, on May 8, the squared minimum annulus was therefore proposed as an excellent approximation to, and likely to coincide with, the actual minimum annulus.
Plans are to search for conditions under which the squared minimum annulus coincides with the actual minimum annulus, and develop specialized linear-programming software.