【作者】 李红军； 张晓鹏；

【Author】 Li Hongjun~(1,2),Zhang Xiaopeng~2 1(College of Science,Beijing Forestry University,Beijing 100083,China) 2(NLPR-LIAMA,Institute of Automation,CAS,Beijing 100190,China)

【机构】 北京林业大学理学院； 中国科学院自动化研究所模式识别国家重点实验室&中法实验室；

【摘要】 针对平面上离散点集求取最小包围圆的问题,评述现有算法并给出一种改进算法,称为较远点对定义初始包围圆的随机增量算法。首先对求取最小包围圆的随机增量算法、最远点优先渐近算法、对偶决策算法等三种典型算法进行概述和简要分析;然后对随机增量算法进行改进;最后,以二维区域随机点集、一维共线随机点集和共线有序点集三类数据进行实验对比。实验结果表明,最远点优先渐近算法是本文列举的三种算法中效率最高的;本文提出的改进算法是一种更快的确定性算法,并大大提高随机增量算法的时间效率。离散点集最小包围圆的快速计算在碰撞检测和机器人等领域有广泛应用。更多还原

【Abstract】 For calculating the smallest enclosing disk of a discrete set of points on the planar,three population algorithms,i.e.the randomized incremental algorithm, the dual decision algorithm and the farthest point first progressive algorithm,are evaluated and an improvement of the randomized incremental algorithm has been presented.The new algorithm employs the Axis-Aligned Bounding Boxes of the point set to optimize the initiate enclosing disk,which greatly improves the calculating efficiency.Numerical experiments show that the farthest point first progressive algorithm is the fastest one among the old three algorithms;our new algorithm is fast and a deterministic one,and can be helpful to applications as in computer graphics,facility locations,intelligent robot, and so on.更多还原