This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Van Deun, K. Articles by Groenen, P. J. F. Search for Related Content

Majorization Algorithms for Inspecting Circles, Ellipses, Squares, Rectangles, and Rhombi

Department of Psychology, Catholic University of Leuven, Tiensestraat 102, B-3000 Leuven, Belgium
Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands
katrijn.vandeun{at}psy.kuleuven.ac.be
groenen{at}few.eur.nl

In several disciplines as diverse as shape analysis, location theory, quality control, archaeology, and psychometrics, it can be of interest to fit a circle through a set of points. We use the result that it suffices to locate a center for which the variance of the distances from the center to a set of given points is minimal. In this paper, we propose a new algorithm based on iterative majorization to locate the center. This algorithm is guaranteed to yield a series of nonincreasing variances until a stationary point is obtained. In all practical cases, the stationary point turns out to be a local minimum. Numerical experiments show that the majorizing algorithm is stable and fast. In addition, we extend the method to fit other shapes, such as a square, an ellipse, a rectangle, and a rhombus by making use of the class of l_p distances and dimension weighting. In addition, we allow for rotations for shapes that might be rotated in the plane. We illustrate how this extended algorithm can be used as a tool for shape recognition.

Subject classifications: mathematics: functions: majorizing functions; facilities: location: continuous; engineering: shape analysis.
History: Received September 2003; revision received October 2004; accepted October 2004.