Perturbation analysis for circles, spheres, and generalized hyperspheres fitted to data by geometric total least-squares

Author:
Yves Nievergelt

Journal:
Math. Comp. **73** (2004), 169-180

MSC (2000):
Primary 65D10, 51M16

DOI:
https://doi.org/10.1090/S0025-5718-03-01613-2

Published electronically:
August 19, 2003

MathSciNet review:
2034115

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A continuous extension of the objective function to a projective space guarantees that for each data set there exists at least one hyperplane or hypersphere minimizing the average squared distance to the data. For data sufficiently close to a hypersphere, as the collinearity of the data increases, so does the sensitivity of the fitted hypersphere to perturbations of the data.

**1.**Åke Björck,*Numerical methods for least squares problems*, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996. MR**97g:65004****2.**T. Altherr and J. Seixas,*Cherenkov ring recognition using a nonadaptable network*, Nuclear Instruments & Methods in Physics Research, Section A**A317**(1992), no. 1, 2, 335-338.**3.**Fred L. Bookstein,*Fitting conic sections to scattered data*, Computer Graphics and Image Processing**9**(1979), 56-71.**4.**I. D. Coope,*Circle fitting by linear and nonlinear least squares*, Journal of Optimization Theory and Applications**76**(1993), no. 2, 381-388. MR**93k:65054****5.**J. F. Crawford,*A noniterative method for fitting circular arcs to measured points*, Nuclear Instruments and Methods**211**(1983), no. 2, 223-225.**6.**I. Duerdoth,*Track fitting and resolution with digital detectors*, Nuclear Instruments and Methods**203**(1982), no. 1-3, 291-297.**7.**Wendell Helms Fleming,*Functions of several variables*, second ed., Springer-Verlag, New York, NY, 1987, Corrected third printing.**8.**Walter Gander, Gene H. Golub, and Rolf Strebel,*Least-squares fitting of circles and ellipses*, BIT**34**(1994), 558-578. MR**97j:65020****9.**M. Hansroul, H. Jeremie, and D. Savard,*Fast circle fit with the conformal mapping method*, Nuclear Instruments & Methods in Physics Research, Section A**A270**(1988), no. 2, 3, 498-501.**10.**Peter Henrici,*Essentials of numerical analysis with pocket calculator demonstrations*, Wiley, New York, NY, 1982. MR**83h:65002****11.**-,*Solutions manual essentials of numerical analysis with pocket calculator demonstrations*, Wiley, New York, NY, 1982.**12.**Nicholas J. Higham,*Accuracy and stability of numerical algorithms*, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996. MR**97a:65047****13.**V. Karimäki,*Effective circle fitting for particle trajectories*, Nuclear Instruments & Methods in Physics Research, Section A**A305**(1991), no. 1, 187-191.**14.**I. Kasa,*A circle fitting procedure and its error analysis*, IEEE Transactions on Instrumentation and Measurement**25**(1976), no. 1, 8-14.**15.**Charles L. Lawson and Richard J. Hanson,*Solving least squares problems*, Classics In Applied Mathematics, vol. 15, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1995. MR**96d:65067****16.**L. Moura and R. Kitney,*A direct method for least-squares circle fitting*, Computer Physics Communications**64**(1992), no. 1, 57-63. MR**92a:65052****17.**Yves Nievergelt,*A tutorial history of least squares with applications to astronomy and geodesy*, Numerical Anslysis: Historical Develoments in the 20th Century (Amsterdam) (Claude Brezinski and Luc Wuytack, eds.), Elsevier, 2001, pp. 77-112. MR**2001e:65002****18.**Vaughan Pratt,*Direct least-squares fitting of algebraic surfaces*, ACM Computer Graphics**21**(1987), no. 4, 145-152. MR**90e:65019****19.**Chris Rorres and David Gilman Romano,*Finding the center of a circular starting line in an ancient Greek stadium*, SIAM Review**39**(1997), no. 4, 745-754. MR**98i:01002****20.**Helmut Späth,*Least-squares fitting with spheres*, Journal of Optimization Theory and Applications**96**(1998), no. 1, 191-199. MR**98m:65065****21.**G. W. Stewart,*On the early history of the singular value decomposition*, SIAM Review**35**(1993), no. 4, 551-566. MR**94f:15001****22.**Sabine Van Huffel and Joos Vandewalle,*The total least squares problem: Computational aspects and analysis*, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1991. MR**93b:65001****23.**Per-Åke Wedin,*Perturbation bounds in connection with singular value decomposition*, BIT**12**(1972), no. 1, 99-111. MR**46:9071**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65D10,
51M16

Retrieve articles in all journals with MSC (2000): 65D10, 51M16

Additional Information

**Yves Nievergelt**

Affiliation:
Department of Mathematics, Eastern Washington University, 216 Kingston Hall, Cheney, Washington 99004-2418

Email:
ynievergelt@ewu.edu

DOI:
https://doi.org/10.1090/S0025-5718-03-01613-2

Keywords:
Fitting,
geometric,
circles,
spheres,
total least-squares

Received by editor(s):
January 3, 2001

Received by editor(s) in revised form:
April 24, 2002

Published electronically:
August 19, 2003

Additional Notes:
Work done at the University of Washington during a leave from Eastern Washington University.

Article copyright:
© Copyright 2003
American Mathematical Society