Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Reference Algorithms for Chebyshev and One-Sided Data Fitting for Coordinate Metrology



Craig M. Shakarji


This paper describes reference algorithms developed at the National Institute of Standards and Technology that fit geometric shapes to data sets according to Chebyshev, maximum -inscribed, and minimum - circumscribed criteria. Using an improved approach, we have developed more reliable reference algorithms for Chebyshev fitting for lines, planes, circles, spheres, cylinders, and cones. In the cases of circles, spheres, and cylinders, we also include maximum -inscribed and minimum -circumscribed fitting. In every case, we obtain the fit through an iteration that begins by using a (relatively easy) least-squares fit and then refine to the desired Chebyshev, maximum -inscribed, or minimum -circumscribed fit. We discuss why computing these fits is substantially more difficult than computing a least-squares fit, as the topography of the objective function prevents certain naive algorithms from working. We describe our choice of simulated annealing as a method that is general enough to be used for all the geometric shapes considered, requiring minimal customization for each shape. We outline steps taken for each geometric shape to reduce the number of fit parameters, thus improving the performance of the algorithms. We describe a suitable temperature reduction schedule that allows these algorithms to converge. We note cases of nonuniqueness related to maximum - inscribed fits. Finally we document test results showing the effectiveness of these algorithms against a battery of data sets with known solutions, against a limited number of exhaustive search results, against intercomparisons with other algorithms that provide for some of these fits, and against themselves by means of a repeatability study. We note that during intercomparisons, we found significant differences between our well-researched reference results and results obtained from algorithms that can be found in industrial use today.
Journal of Annals of the CIRF/Manufacturing Technology 2004


Algorithm, Coordinate measuring machine (CMM), Optimisation


Shakarji, C. (2004), Reference Algorithms for Chebyshev and One-Sided Data Fitting for Coordinate Metrology, Journal of Annals of the CIRF/Manufacturing Technology 2004, [online], (Accessed June 15, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created January 1, 2004, Updated February 17, 2017