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

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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
Volume53
Issue number6
DOIs
Publication statusPublished - 2005
Externally publishedYes

Fingerprint

Quality control
Majorization
Experiments
Archaeology
Numerical experiment
Psychometrics
Weighting
Location theory

Cite this

@article{b5c887491c26463582b21961b6da8fc3,
title = "Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi",
abstract = "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.",
author = "{Van Deun}, K. and Groenen, {P. J. F.}",
year = "2005",
doi = "10.1287/opre.1050.0253",
language = "English",
volume = "53",
pages = "957--967",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "6",

}

Majorization algorithms for inspecting circles, ellipses, squares, rectangles, and rhombi. / Van Deun, K.; Groenen, P. J. F.

In: Operations Research, Vol. 53, No. 6, 2005, p. 957-967.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Van Deun, K.

AU - Groenen, P. J. F.

PY - 2005

Y1 - 2005

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

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

U2 - 10.1287/opre.1050.0253

DO - 10.1287/opre.1050.0253

M3 - Article

VL - 53

SP - 957

EP - 967

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 6

ER -