计算几何中经典问题的交替方向乘子解法
作者单位：南京大学
学位级别：硕士
导师姓名：杨俊锋
授予年度：2019年
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：最小包围球 交替方向乘子法 二阶锥规划 MSW算法 计算几何
摘 要：本文解决了一组点集相对于二阶锥下确界的问题,该问题可以等价的看作计算几何中的许多经典问题[1]。文中将通过Jordan内积定义点集在二阶锥的投影,并采用交替方向乘子法来解决n维空间中m个以点ci为中心,ρi为半径的超球的最小包围球、最小相交球以及最大封闭球问题。此外,文中还特别讨论了二维和三维空间中圆盘和球的三类问题,将其看作LP型问题,并将用于解决LP型问题的MSW算法(由Matouusek,Sharir and Welzl提出)的类似算法与交替方向乘子法结合,逐步扩大确定最优解的球的个数,并利用加权的思想逐步收敛到最优解。类MSW算法与交替方向乘子法的结合有效的减少了问题的计算时间,对于m很大的情况同样适用。
同方学位论文库