Research On Approximate Minimum Enclosing Balls In High Dimensions

We study the minimum enclosing ball (MEB) problem for sets of balls in high dimensions and the minimum enclosing circle (MEC) problem for sets of circles in two dimensions.The MEB problem for sets of balls in high dimensions defines as follows: Compute a ball of minimum radius enclosing a given set of balls (S) in high dimensions.Above definition also applies to the MEC problem in two dimensions (dimension d=2 for MEB problem).Many algorithms were proposed for the MEB problem for sets of points in high dimensions and for the MEC problem's. The worst-case complexity estimate reveals that the direct applications of these algorithms are not computationally feasible for large-scale instances due to excessive memory requirements. Thanks to Badoiu who introduced the notion of core-sets, excessive memory requirement problem could be effectively solved. In this paper, based on the core-sets, we improve related algorithms for the MEB and MEC problem.Introduce the notion of diameter of sets of balls and an approximation algorithm for the diameter is given. We prove that this approximation algorithm can compute a approximation to the diameter of S.Develop a (1+ε)-approximation algorithm for the MEB problem in high dimensions using core-sets. We prove the existence of core-sets of size O(1/ε). The time complexity of this algorithm isImprove different kinds of algorithms for the MEC problem by core-sets and related (1+ε)-approximation algorithms are given.Experiments related to different kinds of algorithms are given in section 2.4 and section 3.4.