Study on Algorithm of Minimum Enclosing Ball Problem Based on Active Set Strategy
Cong Wei-ji · 2013
Firstly,based on computing two furthest points from the current center at each iteration,a(1+e)-approximation algorithm was proposed for solving the minimum enclosing ball problem of mpoints in ndimensions.The algorithm returns a core set of size O(1/e)and achieves an O(mn/e)time complexity for a givene∈(0,1).Secondly,an active set strategy was presented,which computes Nfurthest points from the current center at each iteration.By incorporating this strategy into the proposed algorithm,an algorithm based on active set strategy was obtained.Finally,the experiment results show that the algorithm based on active set strategy can quickly and effectively solve approximate minimum enclosing ball of the large-scale date sets with m≥n.