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

Improved 1+ε Approximation Algorithms for the Balls in High Dimensions via Core-Sets

作　　者：范克磊[1] 栾峻峰[1] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250101

出　　处：《计算机工程与科学》2010年第1期44-46,76,共4页Computer Engineering & Science

摘　　要：高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3^(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。The minimum enclosing ball problem means to construct a ball of the minimum radius enclosing a given set of bails in S. We propose the concept of the diameter of a set of balls and give an approximation algorithm solve the diameter. We develop the 1 ＋ε approximation algorithm using core-sets. The time complexity of this algorithm is O（nd/ε＋d^2/ε^3/2（1/ε＋d）lgl/ε） . We prove the existence of the core-sets of size O（1/ε） are unrelated to n and d.

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

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