求解2—中心问题的算法

AN ALGORITHM FOR THE TWO-CENTER PROBLEM

首先讨论 2—中心问题的各种基本情况及其匹对圆的构造方法 ,然后介绍匹对圆的某些性质 ,最后叙述求解 2—中心问题的算法。算法的思想是覆盖点集的凸壳必然覆盖点集。该算法可以求得两个半径相等而且最小的圆覆盖点集。此外分析了算法复杂性并讨论了正确性 。

All kinds of the basic cases of two-center problems and the construction of their matched-pair circles were discussed. Some properties of the matched-pair circle were then introduced, followed by an algorithm for solving the two-center problems. The governing idea is that the convex hulls covering a set of points must cover the set of points. Using the algorithm can obtain a set of points covered by two equal radii and the smallest circle. Moreover, the complexity of the algorithm was analyzed and its correctness was discussed. A practical example was given.