Study On Approximation Algorithms For Some Class Of Geometry Optimization Problem

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Many classical geometry opti-mization problems are its object of study, such as the minimum enclosing ball problem, the minimum volume enclosing ellipsoid problem, and the minimum volume axis-aligned ellipsoid problem etc. In the fields of modern engineering and mathematics, these prob-lems have applications in numerous fields including computer graphics, pattern recogni-tion, machine learning and collision detection, and these problems themselves are also very significant problems in computational geometry. Therefore, it is very interesting and valuable to study the algorithms of these geometry optimization problems.The existing exact algorithms can be only used to solve small- and medium-scale problems. The goal of this paper is to present efficient approximation algorithms that can compute a (1+e)-approximation of these geometry optimization problems. In par-ticular, these approximation algorithms are to solve large-scale problems with a high accuracy. The main results proposed in this research are as follows:1. Based on approximate optimality conditions of the minimum volume enclosing ellipsoid problem, we define the weak (strong) approximate optimality conditions of the minimum enclosing ball problem and the minimum volume axis-aligned ellipsoid problem, respectively. According to the two different approximate optimality conditions, the existing and proposed approximation algorithms can be divided into two categories. If approximate solutions of the algorithm satisfying the strong approximate optimality conditions, then this algorithm has a linear convergence. Otherwise, this algorithm does not have a linear convergence.2. Based on the existing approximation algorithms, three modified algorithms are proposed for the minimum enclosing ball (MEB) problem. The first modified algorithm obtains approximate solutions satisfying the weak approximate optimality conditions of the MEB problem. The other modified algorithms obtain approximate solutions sat-isfying the strong approximate optimality conditions of the MEB problem. The three modified algorithms compute a (1+e)-approximation to MEB in O(mn/e) operations and return a core set of size O(1/e) for e∈(0,1), which match the currently best known complexity bound and core set result for the approximate MEB problem. The compu-tational results demonstrate that the modified algorithms, which obtain approximate solutions satisfying the strong approximate optimality conditions, are very efficient for solving large-scale problem with a high accuracy. 3. By using the idea of sequential minimal optimization (SMO) method, a rank-two update algorithm of SMO-type and its extension are presented for the minimum volume enclosing ellipsoid (MVEE) problem. They obtain approximate solutions satisfying the strong approximate optimality conditions of the MVEE problem. The rank-two update algorithm computes a (1+e)-approximation to MVEE in O(mn3/e) operations and return a core set of size O(n2/e) for e∈(0,1), which match the currently best known complexity bound and core set result for the approximate MVEE problem. The computational results demonstrate that the proposed rank-two update algorithms have always a better performance than the previous rank-one update algorithms for solving large-scale problem with a high accuracy.4. Based on a recently proposed algorithm, four modified algorithms are presented for the minimum volume axis-aligned ellipsoid (MVAE) problem. The two modified algorithms obtain approximate solutions satisfying the weak approximate optimality conditions of the MVAE problem. The other modified algorithms obtain approximate solutions satisfying the strong approximate optimality conditions of the MVAE problem. The four modified algorithms compute a (1+e)-approximation to MVAE in O(mn3/e) operations and return a core set of size O(n2/e) for e∈(0,1), which improve the complexity bound O(mn5/e) and core set size O(n4/e) of the previous algorithm. These results given the modified algorithms are the currently best known complexity bound and core set result for the approximate MVAE problem, which are consistent with the theoretical results of the approximate MVEE problem. The computational results also imply that the modified algorithms, which obtain approximate solutions satisfying the strong approximate optimality conditions, are very efficient for solving large-scale problem with a high accuracy.