The Alternatin G Direction Method Of Multipliers For Classical Problems In Computational Geometry

We define the problem of infimum of points with respect to a second order cone which is equivalent to many classical problems in computational geometry[1].In this paper,we define the projection of a set of points to a second order cone through Jor-dan product and then adapt the alternating direction method of multipliers to solve the smallest enclosing ball problem,the smallest intersecting ball problem and the largest enclosed ball problem in Rn,with m balls of center ci ?Rn,and radius ?i ? R+.In par-ticular,we discuss these three types of problems in R2 and R3.We regard the smallest enclosing ball problem,the smallest intersecting ball problem and the largest enclosed ball problem as LP-type problems,and combine a algorithm similar to the MSW algo-rithm(proposed by Matousek,Sharir and Welzl)with the alternating direction method of multipliers to solve them.In details,we replace m balls in Rn with less balls which are more important to the optimal solution,and then adapt the idea of weighting which leads the result to converge to the optimal solution gradually.The joint of this two algorithm reduces the time of computation effectively,which is apparent when m is large.