×

zbMATH — the first resource for mathematics

On the circle closest to a set of points. (English) Zbl 0994.90088
Summary: The objective of this paper is to find a circle whose circumference is as close as possible to a given set of points. Three objectives are considered: minimizing the sum of squares of distances, minimizing the maximum distance, and minimizing the sum of distances. We prove that these problems are equivalent to minimizing the variance, minimizing the range, and minimizing the mean absolute deviation, respectively. These problems are formulated and heuristically solved as mathematical programs. Special efficient heuristic algorithms are designed for two cases: the sum of squares, and the minimax. Computational experience is reported.

MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Shunmugam, M.S., Criteria for computer-aided form evaluation, Journal of engineering for industry, 113, 233-238, (1991)
[2] Van-Ban, L.; Lee, D.T., Out-of-roundness problem revisited, IEEE transactions on pattern analysis and machine intelligence, 13, 217-223, (1991)
[3] Ventura, J.A.; Yeralan, S., The minimax center estimation problem for automated roundness inspection, European journal of operational research, 41, 64-72, (1989) · Zbl 0668.90038
[4] Yeralan, S.; Ventura, J.A., Computerized roundness inspection, International journal of production research, 26, 1921-1935, (1988)
[5] Owen, Jean V. CMMs for process control. Manufacturing Engineering 1991;107(2):39-41.
[6] Daskin MS. Network and discrete location: models, algorithms, and applications. New York: Wiley, 1995.
[7] Drezner Z., editor. Facility location: a survey of applications and methods. New York: Springer, 1995.
[8] Francis RL, McGinnis Jr. LF, White JA. Facility layout and location: an analytical approach, 2nd Ed. International Series in Industrial and Systems Engineering. Englewood Cliffs, (NJ): Prentice-Hall, 1992.
[9] Love RF, Morris JG, Wesolowsky GO. Facility location models & methods. NY, North-Holland, 1988.
[10] Coope, I.D., Circle Fitting by linear and nonlinear least squares, Journal of optimization theory and applications, 76, 381-388, (1993) · Zbl 0790.65012
[11] Gruntz, D., Finding the best fit circle, The mathworks newsletter, 1, 5, (1990)
[12] Drezner, Z.; Thisse, J.-.F.; Wesolowsky, G.O., The minimax-MIN location problem, Journal of regional science, 26, 87-101, (1986)
[13] Eiselt HA, Laporte G. Objectives in location problems. In: Drezner Z., editors. Facility Location: a survey of applications and methods. Editors. New York: Springer, 1995.
[14] Erkut, E., Inequality measures for location problems, Location science, 1, 199-217, (1993) · Zbl 0923.90101
[15] Marsh M, Schilling D. A comparison of equity measures in facility siting decisions. In: Reid RD. editor. Proceedings of the First International Conference of the Decision Sciences Institute. (Brussels, Belgium), 1991. p. 244-249.
[16] Marsh, M.; Schilling, D., Equity measurement in facility location analysis: a review and framework, European journal of operational research, 74, 1-17, (1994) · Zbl 0800.90631
[17] Plastria F. Continuous location problems. In: Drezner Z. editor. Facility location: A survey of applications and methods. New York, Springer, 1995.
[18] Carrizosa E. Minimizing the variance of Euclidean Distances. Paper presented at the EWGLA 9 conference, Birmingham England, September, 1996.
[19] Maimon, O., The variance equity measure in locational decision theory, Annals of operations research, 6, 147-160, (1986)
[20] Plastria, F., GBSSS, the generalized big square small square method for planar single facility location, European journal of operational research, 62, 163-174, (1992) · Zbl 0760.90067
[21] Hansen, P.; Peeters, D.; Richard, D.; Thisse, J.-.F., The minisum and minimax location problems revisited, Operations research, 33, 1251-1265, (1985) · Zbl 0582.90027
[22] Fourer R, Gay DM, Kernighan BW. AMPL a modeling language for mathematical programming. South San Francisco, The Scientific Press, 1993.
[23] Weiszfeld, E., Sur le point pour lequel la somme des distances de N points donnés est minimum, Tohoku mathematical journal, 43, 355-386, (1936) · Zbl 0017.18007
[24] Okabe A, Boots B, Sugihara K. Spatial tessellations — concepts and applications of Voronoi diagrams. Chichester, England: Wiley, 1992. · Zbl 0877.52010
[25] Roy, U.; Zhang, X., Development and applications of Voronoi diagrams in the assessment of roundness error in an industrial environment, Computers and industrial engineering, 26, 11-26, (1989)
[26] Demjanov, V.F., Algorithms for some minimax problems, Journal of computers and system science, 2, 342-380, (1968) · Zbl 0177.23104
[27] Drezner, Z.; Wesolowsky, G.O., Layout of facilities with some fixed points, Computers and operations research, 12, 603-610, (1985) · Zbl 0608.90016
[28] Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 382-398, (1959) · Zbl 0103.37603
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.