Approximation algorithms for the minimum enclosing ball problem in high dimensions
Mahdi Imanparastm.imanparast@ub.ac.irDepartment of Computer ScienceUniversity of BojnordBojnord, North Khorasan, 9453155111, Iran0000-0003-1674-2247View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Mar 2025
- Published Online:
- 27 Aug 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-2146
- Pages:
- 1–11
Abstract
We investigate the minimum enclosing ball problem for given n points in fixed dimension d. We present three new approximation algorithms to the problem: a√d-approximation algorithm, a 2-approximation algorithm, and a 1.619-approximation algorithm, all running in O(nd) time. A critical feature of our algorithms is their simplicity, allowing for rapid computation without recourse to exhaustive optimization techniques. While they may not always yield the minimum enclosing ball, they provide a viable solution that is often sufficient for practical applications, especially when working with large datasets.
Keywords
Subject Classifications
References
[1] J. J. Sylvester, “A question in the geometry of situation,” Quarterly Journal of Pure and Applied Mathematics, vol. 1, no. 1, pp. 79-80 (1857).
[2] N. Megiddo, “Linear programming in linear time when the dimension is fixed,” Journal of the ACM (JACM), vol. 31, no. 1, pp. 114-127 (1984).
[3] J. Ritter, “An efficient bounding sphere,” In Game Programming Gems, A. Glassner (Ed.), Academic Press, Boston, pp. 301-303 (1990).
[4] S. Skyum, “A simple algorithm for computing the smallest enclosing circle,” Information Processing Letters, vol. 37, no. 3, pp. 121-125 (1991).
[5] E. Welzl, “Smallest enclosing disks (balls and ellipsoids),” In New Results and New Trends in Computer Science (LNCS 555), H. Maurer (Ed.), Springer- Verlag, pp. 359-370 (1991).
[6] M. Smolik, and V. Skala, “Efficient Speed-Up of the Smallest Enclosing Circle Algorithm,” Informatica, vol. 33, no. 3, pp. 623-633 (2022).
[7] M. Imanparast, S. N. Hashemi, and A. Mohades, “Efficient approximation algorithms for point-set diameter in higher dimensions,” Journal of Algorithms and Computation, vol. 51, no. 2, pp. 47-61 (2019).
[8] M. Bădoiu, S. Har-Peled, and P. Indyk, “Approximate clustering via core-sets,” In Proc. 34th annual ACM symposium on Theory of computing, pp. 250-257 (2002).
[9] P. Kumar, J. S. Mitchell, and E. A. Yildirim, “Approximate minimum enclosing balls in high dimensions using core-sets,” Journal of Experimental Algorithmics (JEA), vol. 8, pp.1-1 (2003).
[10] K. Fischer, B. Gärtner, and M. Kutz, “Fast smallest enclosing- ball computation in high dimensions,” In Proc. 11th Annual European Symposium on Algorithms, LNCS 2832. Springer-Verlag, pp. 630-641 (2003).
[11] K. Fischer, and B. Gärtner, “The smallest enclosing ball of balls: combinatorial structure and algorithms,” In Proc. 19th annual symposium on Computational Geometry, 292-301 (2003).
[12] F. Nielsen, and R. Nock, “A fast deterministic smallest enclosing disk approximation algorithm,” Information Processing Letters, vol. 93, no. 6, pp. 263-268 (2005).
[13] H. Zarrabi-Zadeh, and T. M. Chan, “A Simple Streaming Algorithm for Minimum Enclosing Balls,” In Proc. 18th Canadian Conference on Computational Geometry, pp. 139-142 (2006).
