本文解决了一组点集相对于二阶锥下确界的问题,该问题可以等价的看作计算几何中的许多经典问题[1]。文中将通过Jordan内积定义点集在二阶锥的投影,并采用交替方向乘子法来解决n维空间中m个以点ci为中心,ρi为半径的超球的最小包围球、最小相交球以及最大封闭球问题。此外,文中还特别讨论了二维和三维空间中圆盘和球的三类问题,将其看作LP型问题,并将用于解决LP型问题的MSW算法(由Matouusek,Sharir and Welzl提出)的类似算法与交替方向乘子法结合,逐步扩大确定最优解的球的个数,并利用加权的思想逐步收敛到最优解。类MSW算法与交替方向乘子法的结合有效的减少了问题的计算时间,对于m很大的情况同样适用。
暂无评论