Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi

K. Van Deun, P. J. F. Groenen

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Pages (from-to)957-967
JournalOperations Research
Issue number6
Publication statusPublished - 2005
Externally publishedYes


Dive into the research topics of 'Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi'. Together they form a unique fingerprint.

Cite this