一种基于计算几何方法的最小包容圆求解算法

摘要：

为实现点集最小包容圆(最小外接圆)的求解,将计算几何中的α-壳的概念应用到最小包容圆的计算过程,提出了一种精确有效的最小包容圆求解算法.根据α-壳定义及最小包容圆性质,证明当1/α等于最小包容圆半径时点集的α-壳顶点共圆,1/α小于最小包容圆半径时α-壳不存在,1/α大于最小包容圆半径时随着1/α减小α-壳顶点数逐渐减小的规律.将α-壳顶点数目作为搜索最小包容圆半径的依据,实现了最小包容圆半径的搜索和最小包容圆的求解.

关键词：计算机应用、优化算法、计算几何、最小包容圆、α-壳

所属期刊栏目：28

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金50275083;高等学校博士学科点专项科研项目20020003053

在线出版日期：2007-07-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：97-101