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

Published electronically:
August 19, 2003

MathSciNet review:
2034115

Full-text PDF Free Access

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 (SIAM), Philadelphia, PA, 1996. MR**1386889****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*, J. Optim. Theory Appl.**76**(1993), no. 2, 381–388. MR**1203908**, 10.1007/BF00939613**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), no. 4, 558–578. MR**1430909**, 10.1007/BF01934268**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*, John Wiley & Sons, Inc., New York, 1982. MR**655251****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 (SIAM), Philadelphia, PA, 1996. MR**1368629****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 (SIAM), Philadelphia, PA, 1995. Revised reprint of the 1974 original. MR**1349828****16.**L. Moura and R. Kitney,*A direct method for least-squares circle fitting*, Comput. Phys. Comm.**64**(1991), no. 1, 57–63. MR**1099915**, 10.1016/0010-4655(91)90049-Q**17.**Yves Nievergelt,*A tutorial history of least squares with applications to astronomy and geodesy*, J. Comput. Appl. Math.**121**(2000), no. 1-2, 37–72. Numerical analysis in the 20th century, Vol. I, Approximation theory. MR**1780042**, 10.1016/S0377-0427(00)00343-5**18.**Vaughan Pratt,*Direct least-squares fitting of algebraic surfaces*, Comput. Graphics**21**(1987), no. 4, 145–152. SIGGRAPH ’87 (Anaheim, CA, 1987). MR**987653**, 10.1145/37402.37420**19.**Chris Rorres and David Gilman Romano,*Finding the center of a circular starting line in an ancient Greek stadium*, SIAM Rev.**39**(1997), no. 4, 745–754. MR**1491056**, 10.1137/S0036144596305727**20.**H. Späth,*Least-square fitting with spheres*, J. Optim. Theory Appl.**96**(1998), no. 1, 191–199. MR**1608054**, 10.1023/A:1022675403441**21.**G. W. Stewart,*On the early history of the singular value decomposition*, SIAM Rev.**35**(1993), no. 4, 551–566. MR**1247916**, 10.1137/1035134**22.**Sabine Van Huffel and Joos Vandewalle,*The total least squares problem*, Frontiers in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. Computational aspects and analysis; With a foreword by Gene H. Golub. MR**1118607****23.**Per-Ȧke Wedin,*Perturbation bounds in connection with singular value decomposition*, Nordisk Tidskr. Informationsbehandling (BIT)**12**(1972), 99–111. MR**0309968**

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