Fitting circles and spheres to coordinate measuring machine data

This work addresses the problem of enclosing given data points between two concentric circles (spheres) of minimum distance whose associated annulus measures the out-of-roundness (OOR) tolerance. The problem arises in analyzing coordinate measuring machine (CMM) data taken against circular (spherical) features of manufactured parts. It also can be interpreted as the ‘geometric’ Chebychev problem of fitting a circle (sphere) to data so as to minimize the maximum distance deviation. A related formulation, the ‘algebraic’ Chebychev formula, determines the equation of a circle (sphere) to minimize the maximum violation of the equation by the data points. In this paper, we describe a linear-programming approach for the algebraic Chebychev formula that determines reference circles (spheres) and related annuluses whose widths are very close to the widths of the true geometric Chebychev annuluses. We also compare the algebraic Chebychev formula against the popular algebraic least-squares solutions for various data sets. In most of these examples, the algebraic and geometric Chebychev solutions coincide, which appears to be the case for most real applications. Such solutions yield concentric circles whose separation is less than that of the corresponding least-squares solution. It is suggested that the linear-programming approach be considered as an alternate solution method for determining OOR annuluses for CMM data sets.