摘要
提出求解3-中心问题、4-中心问题、5-中心问题及k(<10)-中心问题的算法.设计该算法的依据是覆盖点集的凸壳必覆盖点集.算法首先判定点集凸壳的形状,然后确定k个圆的排列方式,最后以确定方式计算圆心位置.证明了算法的正确性并且分析了算法的复杂性.
Quick algorithms for solving 3center problem, 4center problem, 5center problem and k(<10)center problems are proposed. This algorithm is designed in terms of which the convex hulls covering a set of points must cover the set of points. The algorithm decides first the character of the convex hulls of the pointset. It then determines the mode of arrangement of k circles and finally computes the positions of the circular centers by the mode determined. The paper also proves their correctness and analyzes their time complexity.
出处
《北京理工大学学报》
EI
CAS
CSCD
北大核心
2003年第5期576-580,共5页
Transactions of Beijing Institute of Technology
关键词
κ—中心问题
凸壳
算法
时间复杂性
k-center problem
convex hull
algorithm
time complexity
