高维空间球集覆盖问题的改进1+ε近似算法

摘要：

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球.本文提出了球集直径的概念,给出求解球集直径的1/平方根3近似算法.基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d~2/ε~(3/2)(1/ε+d)lg1/ε).算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关.

关键词：最小覆盖球、核心集、高维空间球集、近似算法、计算几何

所属期刊栏目：31

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

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

页数：共4页

页码：44-46,76