×

Efficient algorithms for the smallest enclosing ball problem. (English) Zbl 1112.90060

Summary: Consider the problem of computing the smallest enclosing ball of a set of \(m\) balls in \(\mathbb R^n\). Existing algorithms are known to be inefficient when \(n > 30\). In this paper we develop two algorithms that are particularly suitable for problems where \(n\) is large. The first algorithm is based on log-exponential aggregation of the maximum function and reduces the problem into an unconstrained convex program. The second algorithm is based on a second-order cone programming formulation, with special structures taken into consideration. Our computational experiments show that both methods are efficient for large problems, with the product mn on the order of \(10^7\). Using the first algorithm, we are able to solve problems with \(n = 100\) and \(m = 512,000\) in about 1 hour.

MSC:

90C25 Convex programming
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.H. Byrd, P. Lu, J. Nocedal, and C. Zhu, ”A limited memory algorithm for bound constrained optimization” SIAM J. Sci. Comput., vol. 16, pp. 1190–1208, 1995. · Zbl 0836.65080 · doi:10.1137/0916069
[2] J. Elzinga and D. Hearn, ”The minimum covering sphere problem” Management Sci., vol. 19, pp. 96–104, 1972. · Zbl 0242.90061 · doi:10.1287/mnsc.19.1.96
[3] Bn. Gärter, ”Fast and robust smallest enclosing balls” in Algorithms-ESA’99: 7th Annual European Symposium Proceedings, J. Nestril (Ed.), Lecture Notes in Computer Science 1643, Springer-Verlag, pp. 325–338.
[4] B. Gärter, Smallest enclosing ball–Fast and robust in C++, http://www.inf.ethz.ch/personal/gaertner/miniball.html.
[5] G.H. Hardy, J.E. Littlewood, and G. Polya, Inequalities. Cambridge University Press, 1952.
[6] D.W. Hearn and J. Vijan, ”Efficient algorithms for the minimum circle problem” Oper. Res., vol. 30, pp. 777–795, 1982. · Zbl 0486.90039 · doi:10.1287/opre.30.4.777
[7] J.B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithm. Springer-Verlag: Berlin, Heidelberg, 1993.
[8] X.S. Li, ”An aggregate function method for nonlinear programming” Sci. China Ser. A, vol. 34, pp. 1467–1473, 1991. · Zbl 0752.90069
[9] N. Megiddo, ”Linear-time algorithms for linear programming in 3 and related problems” SIAM J. Comput., vol. 12, pp. 759–776, 1983. · Zbl 0521.68034 · doi:10.1137/0212052
[10] Yu. E. Nesterov and A. Nemirovskii, Interior Polynomial Algorithms in Convex Programming. SIAM: Philadelphia, 1994. · Zbl 0824.90112
[11] Yu. E. Nesterov and M.J. Todd, ”Self-scaled barriers and interior-point methods for convex programming” Math. Oper. Res., vol. 22, pp. 1–42, 1997. · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[12] F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag: New York, 1985. · Zbl 0575.68059
[13] M.I. Shamos and D. Hoey, ”Closest-point problems” in 16th Annual Symposium on Foundations of Computer Science (Berkeley, CA, 1975), IEEE Computer Society, Long Beach, CA, 1975, pp. 151–162.
[14] J.F. Sturm, ”Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones” Optim. Methods Softw., vol. 11 & 12, pp. 625–653, 1999. · Zbl 0973.90526 · doi:10.1080/10556789908805766
[15] P. Sun and R.M. Freund, ”Computation of minimum volume covering ellipsoids” MIT Operations Research Center Working Paper OR 064-02, July, 2002.
[16] R.H Tütüncü, K.C. Toh, and M.J. Todd, ”Solving semidefinite-quadratic-linear programs using SDPT3” Math. Programming, vol. 95, pp. 189–217, 2003. · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5
[17] R.J. Vanderbei, ”LOQO user’s manual–version 3.10” Optim. Methods Softw., vol. 11 & 12, pp. 485–514, 1999. · Zbl 0976.90510 · doi:10.1080/10556789908805760
[18] E. Welzl, ”Smallest enclosing disks (balls and ellipsoids)” in New Results and New Trends in Computer Science, H. Maurer (Ed.) Springer-Verlag, 1991, pp. 359–370.
[19] D. White, Enclosing ball software, http://vision.ucsd.edu/\(\sim\)dwhite/ball.html.
[20] S. Xu, R. Freund, and J. Sun, ”Solution methodologies for the smallest enclosing circle problem,”Comput. Optim. Appl.,” vol. 25, pp. 283–292, 2003. · Zbl 1038.90080 · doi:10.1023/A:1022977709811
[21] G.L. Xue and Y.Y. Ye, ”An efficient algorithm for minimizing a sum of Euclidean norms with applications” SIAM J. Optim., vol. 7, pp. 1017–1036, 1997. · Zbl 0885.68074 · doi:10.1137/S1052623495288362
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.