摘要
提出求解k(<n) 中心问题的两类算法 ,其中第 1类算法适用于k <10的情况 ,而第 2类算法可应用于 10 <k<n的情况 两类算法的思想不同 ,前者利用等分凸壳直径的方法并且所确定的圆的圆心位置是固定的 ,而后者采用多种参数随机化的方法 ,从而圆心是不确定的
In this paper two kinds of algorithms for solving the k(<n) center problem are proposed Here the first kind of algorithm is fit for the case k <10, whereas the second one is fit for the case 10< k<n The ideas of the two kinds of algorithms are different The former uses a method which aliquots the diameter of a convex hull and the center position of the circle determined by it is fixed, but the latter adopts a method in which multi parameters are randomized, thus keeping the center of the circle indeterminate Moreover the correctness of the two algorithms is also proved and their time complexity is analyzed
出处
《计算机研究与发展》
EI
CSCD
北大核心
2004年第4期743-748,共6页
Journal of Computer Research and Development
关键词
k-中心问题
凸壳
算法
时间复杂性
k center problem
convex hull
algorithm
time complexity
