The Algorithm For The Smallest Enclosing Circle Problem

The smallest enclosing circle problem is defined as the circle with a minimum radius that encloses all the given circles.In this thesis,based on the non-convex constrained quadratic programming and the reformulation-linearization technique,two algorithms are proposed to solve the smallest enclosing circle problem.This thesis is divided into three chapters,as follows:In Chapter 1,we introduce the research background of the smallest enclosing circle problem and the main content of this thesis.In Chapter 2,a non-convex quadratic programming problem for the smallest enclosing circle problem is considered and the algorithm is given to solve this problem.We use the idea of increasing dimensions and introduce a new variable to solve non-convex quadratic programming problem as a series of linearly constrained quadratic programming problems.Moreover,in numerical experiments,we compare the numerical performances of the algorithm presented in this chapter with the best quadratic programming algorithm in [3].In small scale problem,the computational speed of two algorithm is almost equal.However,in large scale problem,the algorithm presented in this chapter outperforms the quadratic programming algorithm in [3] in terms of the solution time.In Chapter 3,the second order cone programming problem for the smallest enclosing circle problem is considered and the algorithm is given to solve this problem.We use the reformulation-linearization technique to solve the second order cone programming problem as a series of linear programming problems.In addition,in numerical experiments,we compare the numerical performances of the algorithm presented in this chapter with the second order cone programming algorithm in CPLEX and the best cutting plane algorithm in [4].It shows that the algorithm presented in this chapter outperforms the other two approaches in terms of the solution time.Furthermore,the algorithm presented in this chapter is applied to solve the smallest enclosing ball problem in three-dimensional space.The computational speed of the algorithm presented in this chapter is better than the second order cone programming algorithm in CPLEX and the best cutting plane algorithm in [4].