计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2010年
1期
44-46,76
,共4页
最小覆盖球%核心集%高维空间球集%近似算法%计算几何
最小覆蓋毬%覈心集%高維空間毬集%近似算法%計算幾何
최소복개구%핵심집%고유공간구집%근사산법%계산궤하
minimum enclosing ball%core-set%balls in high dimensions lapproximation algorithm%computational geometry
高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球.本文提出了球集直径的概念,给出求解球集直径的1/平方根3近似算法.基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d~2/ε~(3/2)(1/ε+d)lg1/ε).算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关.
高維空間毬集的覆蓋問題是指對高維空間中多箇毬構成的集閤S,構造一箇直徑最小的毬來覆蓋S中所有已知毬.本文提齣瞭毬集直徑的概唸,給齣求解毬集直徑的1/平方根3近似算法.基于此算法求解毬集實例集閤S的初始覈心集,進而給齣高維空間毬集覆蓋問題的1+ε近似算法,算法時間複雜度為O(nd/ε+d~2/ε~(3/2)(1/ε+d)lg1/ε).算法保證覈心集中毬的箇數為O(1/ε),與S中毬的箇數和空間維數無關.
고유공간구집적복개문제시지대고유공간중다개구구성적집합S,구조일개직경최소적구래복개S중소유이지구.본문제출료구집직경적개념,급출구해구집직경적1/평방근3근사산법.기우차산법구해구집실례집합S적초시핵심집,진이급출고유공간구집복개문제적1+ε근사산법,산법시간복잡도위O(nd/ε+d~2/ε~(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 balls 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)log(1/ε)). We prove the existence of the core-sets of size O(1/ε) are unrelated to n and d.
