IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v53y2005i6p957-967.html
   My bibliography  Save this article

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

Author

Listed:
  • K. Van Deun

    (Department of Psychology, Catholic University of Leuven, Tiensestraat 102, B-3000 Leuven, Belgium)

  • P. J. F. Groenen

    (Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands)

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

Suggested Citation

  • K. Van Deun & P. J. F. Groenen, 2005. "Majorization Algorithms for Inspecting Circles, Ellipses, Squares, Rectangles, and Rhombi," Operations Research, INFORMS, vol. 53(6), pages 957-967, December.
    • Handle: RePEc:inm:oropre:v:53:y:2005:i:6:p:957-967
    DOI: 10.1287/opre.1050.0253
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1050.0253
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1050.0253?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Henk Kiers & Patrick Groenen, 1996. "A monotonically convergent algorithm for orthogonal congruence rotation," Psychometrika, Springer;The Psychometric Society, vol. 61(2), pages 375-389, June.
    2. Kiers, Henk A. L., 2002. "Setting up alternating least squares and iterative majorization algorithms for solving various matrix optimization problems," Computational Statistics & Data Analysis, Elsevier, vol. 41(1), pages 157-170, November.
    3. K. Deun & P. Groenen & W. Heiser & F. Busing & L. Delbeke, 2005. "Interpreting degenerate solutions in unfolding by use of the vector model and the compensatory distance model," Psychometrika, Springer;The Psychometric Society, vol. 70(1), pages 45-69, March.
    4. Patrick Groenen & Bart-Jan Os & Jacqueline Meulman, 2000. "Optimal scaling by alternating length-constrained nonnegative least squares, with application to distance-based analysis," Psychometrika, Springer;The Psychometric Society, vol. 65(4), pages 511-524, December.
    5. Patrick Groenen & Rudolf Mathar & Willem Heiser, 1995. "The majorization approach to multidimensional scaling for Minkowski distances," Journal of Classification, Springer;The Classification Society, vol. 12(1), pages 3-19, March.
    6. P. J. F. Groenen & W. J. Heiser & J. J. Meulman, 1999. "Global Optimization in Least-Squares Multidimensional Scaling by Distance Smoothing," Journal of Classification, Springer;The Classification Society, vol. 16(2), pages 225-254, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Groenen, P.J.F. & Winsberg, S. & Rodriguez, O. & Diday, E., 2006. "I-Scal: Multidimensional scaling of interval dissimilarities," Computational Statistics & Data Analysis, Elsevier, vol. 51(1), pages 360-378, November.
    2. Antanas Žilinskas & Julius Žilinskas, 2008. "A hybrid method for multidimensional scaling using city-block distances," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(3), pages 429-443, December.
    3. Julius Žilinskas, 2012. "Parallel branch and bound for multidimensional scaling with city-block distances," Journal of Global Optimization, Springer, vol. 54(2), pages 261-274, October.
    4. Groenen, P.J.F. & Kaymak, U. & van Rosmalen, J.M., 2006. "Fuzzy clustering with Minkowski distance," Econometric Institute Research Papers EI 2006-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. van Deun, K. & Groenen, P.J.F. & Delbeke, L., 2005. "VIPSCAL: A combined vector ideal point model for preference data," Econometric Institute Research Papers EI 2005-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    6. Raoul Pietersz & Patrick Groenen, 2004. "Rank reduction of correlation matrices by majorization," Quantitative Finance, Taylor & Francis Journals, vol. 4(6), pages 649-662.
    7. Groenen, P.J.F. & Winsberg, S. & Rodriguez, O. & Diday, E., 2005. "SymScal: symbolic multidimensional scaling of interval dissimilarities," Econometric Institute Research Papers EI 2005-15, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Markovsky, Ivan & Niranjan, Mahesan, 2010. "Approximate low-rank factorization with structured factors," Computational Statistics & Data Analysis, Elsevier, vol. 54(12), pages 3411-3420, December.
    9. DeSarbo, Wayne S. & Selin Atalay, A. & Blanchard, Simon J., 2009. "A three-way clusterwise multidimensional unfolding procedure for the spatial representation of context dependent preferences," Computational Statistics & Data Analysis, Elsevier, vol. 53(8), pages 3217-3230, June.
    10. Groenen, P.J.F. & Giaquinto, P. & Kiers, H.A.L., 2003. "Weighted Majorization Algorithms for Weighted Least Squares Decomposition Models," Econometric Institute Research Papers EI 2003-09, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. Joonwook Park & Wayne DeSarbo & John Liechty, 2008. "A Hierarchical Bayesian Multidimensional Scaling Methodology for Accommodating Both Structural and Preference Heterogeneity," Psychometrika, Springer;The Psychometric Society, vol. 73(3), pages 451-472, September.
    12. Michael Brusco & Stephanie Stahl, 2005. "Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming," Psychometrika, Springer;The Psychometric Society, vol. 70(2), pages 253-270, June.
    13. Krijnen, Wim P., 2006. "Convergence of the sequence of parameters generated by alternating least squares algorithms," Computational Statistics & Data Analysis, Elsevier, vol. 51(2), pages 481-489, November.
    14. Michael Brusco & Hans-Friedrich Köhn & Stephanie Stahl, 2008. "Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis," Psychometrika, Springer;The Psychometric Society, vol. 73(3), pages 503-522, September.
    15. Willem Heiser, 2004. "Geometric representation of association between categories," Psychometrika, Springer;The Psychometric Society, vol. 69(4), pages 513-545, December.
    16. Andrew Webb, 1997. "Radial basis functions for exploratory data analysis: An iterative majorisation approach for Minkowski distances based on multidimensional scaling," Journal of Classification, Springer;The Classification Society, vol. 14(2), pages 249-267, September.
    17. Groenen, Patrick J. F. & Franses, Philip Hans, 2000. "Visualizing time-varying correlations across stock markets," Journal of Empirical Finance, Elsevier, vol. 7(2), pages 155-172, August.
    18. Jos Berge, 2005. "J.C. Gower and G.B. Dijksterhuis.Procrustes problems. New York: Oxford University Press," Psychometrika, Springer;The Psychometric Society, vol. 70(4), pages 799-801, December.
    19. Vera, J. Fernando & Macas, Rodrigo & Heiser, Willem J., 2009. "A dual latent class unfolding model for two-way two-mode preference rating data," Computational Statistics & Data Analysis, Elsevier, vol. 53(8), pages 3231-3244, June.
    20. Groenen, P.J.F. & van der Lans, A., 2006. "Multidimensional Scaling with Regional Restrictions for Facet Theory: An Application to Levi's Political Protest Data," ERIM Report Series Research in Management ERS-2006-057-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:53:y:2005:i:6:p:957-967. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.