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

Analysis and improvement of smallest enclosing disk algorithm on discrete set of points

作　　者：李红军[1,2] 张晓鹏[2] 

机构地区：[1]北京林业大学理学院,北京100083 [2]中国科学院自动化研究所模式识别国家重点实验室&中法联合实验室,北京100190

出　　处：《图学学报》2012年第2期34-38,共5页Journal of Graphics

基　　金：国家自然科学基金资助项目(60970093;60902078;60872120)

摘　　要：针对平面上的离散点集求取最小包围圆的问题,评述现有算法并给出一种改进算法,称为较远点对定义初始包围圆的增量算法。首先概述了几条对算法理解和设计有直接影响的最小包围圆性质或判定;然后对求取最小包围圆的随机增量算法、最远点优先渐近算法、对偶决策算法等3种典型算法进行概述和简要分析;再对随机增量算法和最远点优先渐近算法进行改进;最后,以二维区域随机点集、一维共线随机点集和共线有序点集3类数据进行实验对比。实验结果表明,最远点优先渐近算法是过去3种算法中效率最高的;论文提出的较远点对定义初始包围圆的增量算法大大提高了随机增量算法的时间效率,是该文所列举的方法中最快的算法,并且是一种确定性算法。离散点集最小包围圆的快速计算有助于碰撞检测和机器人等领域的广泛应用。For calculating the smallest enclosing disk of a discrete set of points on the planar,three popular 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 is 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;the new algorithm is a fast and deterministic one,and can be helpful to the applications in computer graphics,facility locations,intelligent robot,and so on.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]