基于积极集策略的最小闭包球问题算法研究

摘要：

首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法.对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε).然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点.将该策略结合到提出的算法中,得到一个基于积极集策略的算法.最后,实验结果表明基于积极集策略的算法能够快速、有效地求解m》n的大规模数据集的近似最小闭包球.

关键词：最小闭包球、核心集、积极集策略、大规模数据集

所属期刊栏目：40

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61072144,61075117;陕西省教育厅专项科研基金项目12JK0735;西安邮电大学博士科研启动基金项目1051203

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

页数：共4页

页码：234-236,253