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

范克磊; 栾峻峰

doi:10.3969/j.issn.1007130X.2010.

计算机工程与科学 >

2010 , Vol. 32 >Issue 1: 44 - 46

DOI: https://doi.org/10.3969/j.issn.1007130X.2010.

论文

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

范克磊 ,
栾峻峰

展开

（山东大学计算机科学与技术学院，山东济南 250101）

范克磊（1985-），男，山东潍坊人，硕士生，研究方向为算法分析与设计；栾峻峰，副教授，研究方向为算法分析与设计。

收稿日期: 2009-04-12

修回日期: 2009-07-10

网络出版日期: 2010-01-18

收起

Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets

FAN Ke-Lei ,
LUAN Jun-Feng

Expand

（School of Computer Science and Technology,Shandong University,Jinan 250101,China）

Received date: 2009-04-12

Revised date: 2009-07-10

Online published: 2010-01-18

Fold

摘要

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

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

本文引用格式

范克磊 , 栾峻峰 . 高维空间球集覆盖问题的改进1+ε近似算法[J]. 计算机工程与科学, 2010 , 32(1) : 44 -46 . DOI: 10.3969/j.issn.1007130X.2010.

Abstract

The minimum enclosing ball problem means to construct a ball of the minimum radius enclosing a given set of balls in 〖WTBX〗S〖WTBZ〗.We propose the concept of the diameter of a set of balls and give an approximation algorithm solve the diameter. We developthe 1+ε approximation algorithm using coresets. The time complexity of this algorithm is O(nd/ε+d2/ε〖SX(〗32〖SX)〗(1/ε+d)log(1/ε)). We prove the existence of the coresets of size O(1/ε) are unrelated to n and d.

Key words： minimum enclosing ball;coreset;balls in high dimensions;approximation algorithm;computational geometry

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract