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

编号 zgly0000792136

文献类型 期刊论文

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

作者 李红军  张晓鹏 

作者单位 北京林业大学理学院  中国科学院自动化研究所模式识别国家重点实验室＆中法联合实验室 

母体文献 图学学报 

年卷期 2012,33(2)

页码 34-38

年份 2012 

分类号 TP301 

关键词 最小包围圆  随机增量算法  最小包围圆性质  计算几何 

文摘内容 针对平面上的离散点集求取最小包围圆的问题,评述现有算法并给出一种改进算法,称为较远点对定义初始包围圆的增量算法。首先概述了几条对算法理解和设计有直接影响的最小包围圆性质或判定;然后对求取最小包围圆的随机增量算法、最远点优先渐近算法、对偶决策算法等3种典型算法进行概述和简要分析;再对随机增量算法和最远点优先渐近算法进行改进;最后,以二维区域随机点集、一维共线随机点集和共线有序点集3类数据进行实验对比。实验结果表明,最远点优先渐近算法是过去3种算法中效率最高的;论文提出的较远点对定义初始包围圆的增量算法大大提高了随机增量算法的时间效率,是该文所列举的方法中最快的算法,并且是一种确定性算法。离散点集最小包围圆的快速计算有助于碰撞检测和机器人等领域的广泛应用。