离散点集最小包围圆算法分析与改进

摘要：

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

关键词： 最小包围圆 随机增量算法 时间效率 离散点集

作者: 李红军 张晓鹏

作者单位: 北京林业大学理学院,北京市 100083 中国科学院自动化研究所模式识别国家重点实验室&中法实验室,北京 100190 中国科学院自动化研究所模式识别国家重点实验室&中法实验室,北京 100190

会议类型: 国内会议

会议名称: 第五届全国几何设计与计算学术会议(GDC2011)

会议地点: 广州

会议语种:中文

页码: 186-189

在线出版日期: 2011-11-11（万方平台首次上网日期，不代表论文的发表时间）