|
|||||
|
|
| 高维空间球集覆盖问题的改进1+ε近似算法 | |
| 引用本文： | 范克磊,栾峻峰.高维空间球集覆盖问题的改进1+ε近似算法[J].计算机工程与科学,2010,31(1). |
| 作者姓名： | 范克磊 栾峻峰 |
| 作者单位： | 山东大学计算机科学与技术学院,山东,济南,250101 |
| 摘 要： | 高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。 |
| 关 键 词： | 最小覆盖球 核心集 高维空间球集 近似算法 计算几何 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |