摘要
分析了已有求覆盖平面上给定的若干个点的尽可能小的圆的问题的算法。给出了一个新的求解最小覆盖问题的算法，其计算时间复杂度为平面上给定的点数量的线性函数，该算法已编程实现，通过几万例随机算例的实际计算比较，表明算法所得结果的平均精度比已有的各种快速近似算法所得的精度要高，而且具体每例所需的计算时间均比已有快速近似算法对应的计算时间要短。
The famous problem of finding a smallest circle to cover a given number of points on aplane(FSCC)is studied.Existing algorithms are discussed and a new one for solving FSCCis given,The computing complexity of this algorithm is a linear function of the number ofthe given points;This algorithm has been programmed and used for the computation for tensof thousands of random examples,It is shown that the average accuracy of results obtainedwith this algorithm is better than those given by currently used algorithms.
出处
《华中理工大学学报》
CSCD
北大核心
1994年第10期101-105,共5页
Journal of Huazhong University of Science and Technology
基金
国家自然科学基金
关键词
最小覆盖问题
精度
快速近似算法
minimum covering problem
computing complexity
accuracy
algorithm
