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

, ,
doi.org/10.1287/opre.1050.0253, hdl.handle.net/1765/74748
Operations Research
Erasmus Research Institute of Management

van Deun, K., & Groenen, P. (2005). Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi. Operations Research, 53(6), 957–967. doi:10.1287/opre.1050.0253