Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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.


References [Enhancements On Off] (What's this?)

  • 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

Similar Articles

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