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 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.

Additional Metadata
Keywords iterative majorization, location, optimization, shape analysis
Persistent URL hdl.handle.net/1765/944
Citation
van Deun, K., & Groenen, P.J.F.. (2003). Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi (No. EI 2003-35). Retrieved from http://hdl.handle.net/1765/944