Solving Minimum Covering Circle/ Dome Problem Using Four or More Boundary Points of the Given Cluster

¹ Loyola-ICAM College of Engineering and Technology (LICET), Chennai, India
² Vellore Institute of Technology, Vellore, India
³ Wroclaw University of Science and Technology, Poland
⁴ Rajamangala University of Technology, Krungthep (RMUTK), Thailand

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Published online: 2 March 2026

Abstract

Solving the minimum covering circle problem for a cluster of points in the Euclidean plane has been an area of interest for researchers over the past five decades. If the data points are in a three-dimensional spherical space, then the problem becomes a "minimum covering dome". In such cases, the Great Circle Distance (GCD) is used. This paper uses four or more boundary points of a cluster to solve the problem in planar and spherical surfaces. A modified population-based TP-AB algorithm is used for this. Points are generated using Normal, Exponential, Uniform, Poisson and Binomial distributions for the analyses. It is demonstrated that a maximum of six boundary points is sufficient to solve such problems, even with 20,000 points. This saves much time when compared with using all points for the simulation. The advantages of the proposed model are that it can accommodate dynamic points, and use any distance metric, distribution and dimension effectively.