求解最小包容圆问题的一种有效算法

蔡 园， 蒋 毅， 王成露

（四川师范大学 数学科学学院 可视化计算与虚拟现实四川省重点实验室，四川 成都610066）

1 背景介绍

最小包容圆问题是求解平面上包容所有给定圆的最小的圆，该问题简写为SEC［1］.这个问题最初是由Sylvester［2］在1857年提出的，并且可以在线性时间内求解.最小包容圆问题有很多的应用背景，比如规划共享设施的位置、环境科学、模式识别、机械工程以及计算机制图等，具体参考文献［3-6］.许多文献都涉及了最小包容圆问题的算法，例如切平面法［7］、二次规划法［3］以及基于Voronoi图的算法［8］.最小包容圆问题的数学模型描述为如下形式

其中，（x，y）和R分别代表最优圆的圆心和半径，¯=｛o1，o2，…，om｝表示m个给定的圆，它们的圆心和半径分别为｛（a1，b1），（a2，b2），…，（am，bm）｝和｛r1，r2…，rm｝.根据半径的不同，最小包容圆问题又可以分为以下的2种情况：ri=0以及ri＞0，其中i=1，2，…，m.对于ri=0，已经有许多文献报道，比如文献［9-10］.本文主要研究ri＞0的情况，可参考文献［3，7，11］等.在文献［3］中，一共研究了4种著名的算法来解最小包容圆问题，包括二次规划法、次梯度法，随机增量法以及二阶锥规划法.在他们的计算实验中，表明了最好的算法是二次规划法.文献［3］中二次规划法最主要的思想就是把问题（1）转化为如下的一个含有线性约束的二次规划问题

（x0，y0）为任意给定的初始值，此时问题（2）是凸优化［12］.在本文数值实验中，与文献［3］中最好的二次规划法进行比较，新算法处理的数据越大越有效.值得提出的是，本文思想来源于文献［13-14］中的方法.

2 算法描述

下面介绍本文提出的……