（计算机软件与理论专业论文）高维空间近似最小球覆盖问题的研究.pdf

j，_ ，土 f 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 立5 ：! 盏丕 日期：丝! 旦：篁：兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 元论文作者签名：篷盘盈导师签名： ， f t 期：型! ! 薹! 兰) lll一 叠 4 卜 噜 厶 - 摘要i a b s t r a c t “ 第1 章绪论l 1 1 应用背景及问题描述l 1 1 1 应用背景1 1 1 2 问题描述2 1 2 研究现状2 1 3 研究方法3 1 4 论文的组织结构3 第2 章高维空间球集覆盖问题5 2 1 问题简介5 2 2 球集直径及初始核心集5 2 31 + s 近似算法8 2 4s o c p 介绍及实验结果一9 2 4 1s o c p 介绍一9 2 4 2 实验结果1l 第3 章二维空间圆覆盖问题1 4 3 1 圆覆盖问题简介一1 4 3 2 圆覆盖问题求解算法1 4 3 2 1 二阶锥规划1 4 3 2 2 次梯度方法1 5 3 2 3 二次规划1 7 3 2 4 随机增量算法1 9 3 3 利用核心集求解圆覆盖问题2 2 3 4 实验结果2 2 3 4 1 二阶锥规划与算法3 4 的实验结果2 3 山东大学硕士学位论文 3 4 2 次梯度方法与算法3 4 的实验结果“2 5 3 4 3 二次规划与算法3 4 的实验结果2 7 3 4 4 二阶锥规划，算法3 1 与算法3 2 实验结果比较2 8 3 4 5 随机增量算法与算法3 4 的实验结果”2 9 3 5 结论一3 l 第4 章总结与展望3 2 4 1 总结一3 2 4 2 展望一3 2 参考文献3 3 致谢3 6 攻读硕士期间发表的学术论文目录3 7 n 飞 堍 - 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e “i a b s t r a c ti ne n g l i s h i i c h a p t e r1i n t r o d u c t i o n 1 1 1a p p l i c a t i o nb a c k g r o u n da n dp r o b l e md e s c r i p t i o n 1 1 1 1a p p l i c a t i o nb a c k g r o u n d 1 1 1 2p r o b l e md e s c r i p t i o n 2 1 2s i t u a t i o no fs t u d y 2 1 3r e s e a r c hm e t h o d s 3 1 4s t r u c t u r eo f p a p e r 3 c h a p t e r2t h e m e bp r o b l e mi nh i g hd i m e n s i o n s 5 2 1i n t r o d u c t i o no f t h ep r o b l e m 5 2 2d i a m e t e ro fs e t so f b a l l sa n di n i t i a lc o r e s e t s 5 2 31 + s a p p r o x i m a t i o na l g o r i t h m 8 2 4i n t r o d u c t i o no f s o c pa n de x p e r i m e n t a lr e s u l t 9 2 4 1i n t r o d u c t i o no f 如c r 尸9 2 4 2e x p e r i m e n t a lr e s u l t s 1 1 c h a p t e r3 t h e m e ci nt w od i m e n s i o n s 1 4 3 1i n t r o d u c t i o no f t h e m e cp r o b l e m 1 4 3 2a l g o r i t h m so f t h e m e c p r o b l e m 1 4 3 2 1s e c o n do r d e rc o n ep r o g r a m m i n g 1 4 3 2 2s u b g r a d i e n ta p p r o a c h 1 5 3 2 3q u a d r a t i cp r o g r a m m i n gs c h e m e 1 7 3 2 4r a n d o m i z e di n c r e m e n t a la l g o r i t h m 1 9 3 3s o l v et h e m e c p r o b l e m u s i n gc o r e s e t s 2 2 3 4e x p e r i m e n t a lr e s u l t s 2 2 3 4 1e x p e r i m e n t a lr e s u l t so fs e c o n do r d e rc o n er e f o r m u l a t i o na n d a l g o r i t h m3 4 2 3 山东大学硕士学位论文 3 4 2e x p e r i m e n t a lr e s u l t so fs u b g r a d i e n ta p p r o a c ha n da l g o r i t h m3 4 2 5 3 4 3e x p e r i m e n t a lr e s u l t so fq u a d r a t i cp r o g r a m m i n gs c h e m ea n d a l g o r i t h m3 4 2 7 3 4 4e x p e r i m e n t a lr e s u l t so f s o c p ，a l g o r i t h m3 1a n da l g o r i t h m3 2 2 8 3 4 5e x p e r i m e n t a lr e s u l t so f r a n d o m i z e di n c r e m e n t a la l g o r i t h ma n d a l g o r i t h m3 4 2 9 3 5c o n c l u s i o n 3 1 c h a p t e r4 c o n c l u s i o na n dp r o s p e c t 3 2 4 1c o n c l u s i o n 3 2 4 2p r o s p e c t 3 2 r e f e r e n c e s 3 3 a c k n o w l e d g e m e n t 3 6 p u b l i s h e da c a d e m i cp a p e r s 3 7 1 v ， 峨 ， 山东大学硕士学位论文 摘要 本文主要讨论高维空间球集最小球覆盖问题和二维空间圆集最小圆覆盖问 题。 高维空间最小球覆盖问题是指对于给定的高维空间球集s ，求解覆盖s 中所 有球的最小球。 二维空间最小圆覆盖问题是高维空间最小球覆盖问题的特例( 维数d = 2 ) 。 点集和圆集的覆盖问题目前已经有很多求解算法。由于这些算法对内存的过 度需求，导致我们无法在合理的时间内求解大数据量问题。b f i d o i u 提出了核心 集的概念，降低了求解该问题的复杂性。本文通过引入核心集的思想，改进了球 集和圆集覆盖问题的各种算法。 提出了球集直径的概念，给出了求解球集直径的近似算法，并证明了该算法 至少可以得到l 3 倍球集直径近似值。 给出了求解高维空间球集最小球覆盖问题的1 + s 近似算法。其中核心集的大 小为d ( 1 占) ，算法的时间复杂度为d ( 刀d 6 - i - ( d 2 占纠2 ) ( 1 s + d ) l o g ( 1 占) ) 。 通过引入核心集的思想，改进了二维空间圆集最小圆覆盖问题的各种求解算 法，给出了求解该问题的1 + s 近似算法。 第2 4 节和第3 4 节对各种算法进行了实验对比。 关键词：最小覆盖球：核心集：高维空间球集；二维空间圆集；近似算法； 球集直径 a b s t r a c t w es t u d yt h em i n i m u me n c l o s i n gb a l l( m e b ) p r o b l e mf o rs e t so fb a l l si nh i g h d i m e n s i o n sa n dt h em i n i m u me n c l o s i n gc i r c l e ( m e c ) p r o b l e mf o rs e t so fc i r c l e si n t w od i m e n s i o n s t h em e bp r o b l e mf o rs e t so fb a l l si nh i l g hd i m e n s i o n sd e f i n e sa s f o l l o w s ： c o m p u t eab a l lo fm i n i m u mr a d i u se n c l o s i n g ag i v e ns e to fb a l l s ( s ) i nh i g h d i m e n s i o n s a b o v ed e f i n i t i o na l s oa p p l i e st ot h em e cp r o b l e mi nt w od i m e n s i o n s ( d i m e n s i o n d = 2f o r m e bp r o b l e m ) m a n ya l g o r i t h m sw e r ep r o p o s e df o rt h em e bp r o b l e mf o rs e t so fp o i n t si nh ig h d i m e n s i o n sa n df o rt h em e cp r o b l e m s t h ew o r s t c a s ec o m p l e x i t ye s t i m a t er e v e a l s t h a tt h ed i r e c ta p p l i c a t i o n so ft h e s ea l g o r i t h m sa r en o tc o m p u t a t i o n a l l yf e a s i b l ef o r l a r g e s c a l ei n s t a n c e sd u et oe x c e s s i v em e m o r yr e q u i r e m e n t s t h a n k st ob 盖d o i uw h o i n t r o d u c e dt h en o t i o no fc o r e s e t s ，e x c e s s i v em e m o r yr e q u i r e m e n tp r o b l e mc o u l db e e f f e c t i v e l ys o l v e d i nt h i sp a p e r , b a s e d o nt h ec o r e - s e t s ，w ei m p r o v er e l a t e d a l g o r i t h m sf o rt h em e b a n dm e c p r o b l e m i n t r o d u c et h en o t i o no fd i a m e t e ro fs e t so fb a l l sa n da na p p r o x i m a t i o na l g o r i t h m f o rt h ed i a m e t e ri sg i v e n w ep r o v et h a tt h i sa p p r o x i m a t i o na l g o r i t h mc a nc o m p u t ea 1 , 5a p p r o x i m a t i o nt ot h ed i a m e t e ro fs d e v e l o pa ( 1 + s ) - a p p r o x i m a t i o na l g o r i t h mf o rt h em e bp r o b l e m i n h i g h d i m e n s i o n su s i n gc o r e s e t s w ep r o v et h ee x i s t e n c eo fc o r e - s e t so fs i z e0 ( 1 e ) t h e t i m ec 。m p l e x i t y 。f t h i sa l g o r i t h mi s d ( 门a s + ( d 2 e 3 2 ) ( i s + d ) l o g ( 1 s ) ) 。 i m p r o v ed i f f e r e n tk i n d so fa l g o r i t h m sf o rt h em e cp r o b l e mb y c o r e - s e t sa n d r e l a t e d ( 1 + s ) 一a p p r o x i m a t i o na l g o r i t h m sa r eg i v e n e x p e r i m e n t sr e l a t e dt od i f f e r e n tk i n d so fa l g o r i t h m sa r eg i v e ni ns e c t i o n2 4a n d s e c t i o n3 4 i i 净 一 一 瞒 l 、 c i r c l e si nt w od i m e n s i o n s ；a p p r o x i m a t i o na l g o r i t h m ；d i a m e t e ro fs e t so fb a l l s i i i h卜- 一 山东大学硕士学位论文 第1 章绪论 高维空间球集最小球覆盖问题目前在很多领域都有应用。本章将简单的介绍 该问题的应用背景及领域，研究现状和研究方法。 1 1 应用背景及问题描述 1 1 1 应用背景 高维空间最小球覆盖问题用于求解覆盖给定球集的最小覆盖球。该问题在现 实生活中有很多应用。例如： 考虑建设一个医院，来服务周边的社区。如果我们将社区中的每个家庭作为 平面中的一个点，寻找一个最小圆来覆盖所有的点。如果我们把医院建在这个最 小圆的中心，则可以最小化医院与最远家庭之间的距离。 在军事上，假设在地图上有需要摧毁的一系列目标点，如果把炸弹投放在覆 盖这些目标点的最小圆的圆心上，则可以更有效的摧毁目标点。进一步说，如果 知道炸弹的有效打击范围( 最大半径) ，摧毁这些目标点所需要的炸弹数目也可 以通过覆盖问题来解决。 高维空间最小球覆盖问题可用于解决环境科学( 设计和优化溶剂) ，模式识 别( 寻找参考点) ，生物学( 蛋白质分析) ，政治学( 分析政党光谱) ，机械工 程( 应力优化) ，计算机图形学( 光线追踪，选择( c u l l i n g ) ) 等领域的问题。 关于更多这些应用的介绍请参照1 1 1 2 3 1 。 也可用于解决机器学习中的差距容错分类【4 1 ，调整支持向量机参数5 1 ，支持 向量聚类【6 】【7 1 ，最远的邻居查询快速逼近【羽，缸中心聚类1 9 1 ，半径集群测试k = - i 【1 0 】 等问题。 二维空间最小圆覆盖问题的应用包括上述建设医院及军事上的应用等实例。 山东大学硕士学位论文 1 1 2 问题描述 本论文主要研究两方面的问题。高维空间球集最小球覆盖问题和二维空间圆 集最小圆覆盖问题。 高维空间球集最小球覆盖问题是指对于给定的球集s ，求一个最小球，该球 可以覆盖s 中所有的球。 给定集合s = b l ，b 2 ，吃，b i 为d 维空间的球，其球心记为q ，半径记为，；。 最小覆盖球m e b ( s ) 是指半径最小且覆盖集合s 的球，记为彤r ，c 为m e b ( s ) 的球心，厂为m e b ( s ) 的半径。 二维空间圆集最小圆覆盖问题可以看做是高维空间球集最小球覆盖问题的 特例( 萨2 ) 。 给定集合c = q ，c ：，c n ，c i 为二维空间的圆( i = 1 7 2 ，玎) ，其圆心记为 ( q ，岛) ，( 吃，b 2 ) ，( a o ，既) ) ，半径记为 r l , 吃，吃) 。最小覆盖圆( m i n i m u m e n c l o s i n gc i r c l e ，m e c ) 是指覆盖集合c 且半径最小的圆。 1 2 研究现状 高维空间点集最小球覆盖问题已经有很多结果 9 1 1 1 1 】【1 2 1 。平面上的最小圆覆盖 问题有多项式时间算法1 3 】。精确求解高维空间点集最小球覆盖问题的时间复杂度 为d ( c 倒) 以1 3 1 。已知的各种求解最小球覆盖l 口- j 题的算法在处理大数据量问题上都 存在对内存的过度需求2 0 1 ，导致在合理的时间内无法求解该问题。b f i d o i u 等【9 】 提出了核心集的概念及其在高维空间点集m e b 问题近似算法设计中的应用。通 过引入核心集思想，求解大数据量的m e b 问题得到解决。k u m a r 等【1 2 1 设计了一 个点集上利用核心集求解高维空间m e b 问题的近似算法，其中核心集大小为 o ( 1 8 ) 。 栾峻峰等l 提出了球到球距离的概念，利用核心集，给出了高维空间球集 m e b 问题的核心集大小为o ( 1 e 21 的近似算法。 2 之 山东大学硕士学位论文 多算法仅仅考虑了点集的覆盖问题，即，：= 0 ，i = 1 ，2 ，力。最简单的算法 是计算n 个点中所有覆盖2 个或者3 个点的圆，然后寻找覆盖所有点的最小圆。 总共有p ( 珂3 1 个覆盖3 个点的圆，验证是否是最小圆需d ( 刀) 时间，因此总共运 行时间是d ( 力4 1 。m e g i d d o t z l l 理论分析了时间复杂度为o ( n ) 的有效方法。c h r y s t a l 【2 2 1 ，e l l i o s o f fa n du n g e r r e f t 2 1 ，e l z i n g aa n dh e a m 2 3 1 ，g l i r t n e r 3 】，h e a r na n dv i ja n t 2 4 1 ， w e l z l 2 5 1 给出了切实有效的算法求解点集最小圆覆盖问题。 s x u 等【1 3 】总结了求解圆覆盖问题的四种算法。包括二阶锥规划( s e c o n d o r d e rc o n ep r o g r a m m i n g ) 、次梯度方法( s u b g r a d i e n ta p p r o a c h ) 、二次规划( q u a d r a t i c p r o g r a m m i n g ) 和随机增量算法( r a n d o m i z e di n c r e m e n t a la l g o r i t h m ) 。在第3 2 节中我们将详细介绍这四种算法。 1 3 研究方法 在第2 章中，首先给出球集直径的求解方法，求解出球集s 的初始核心集， 得到覆盖初始核心集的最小球，该球将尽可能多的包含球集s 中的球。以此初始 核心集为基础，给出求解高维空间球集m e b 问题的1 + s 近似算法。 在第3 章中，通过引入核心集的思想及其近似算法，对二维空间圆集最小圆 覆盖问题的各种已知求解算法进行改进，得到利用核心集求解该问题的1 + s 近似 算法。 1 4 论文的组织结构 本论文共分为4 章。 第1 章为绪论，主要介绍球集最小球覆盖问题的概念及思想，应用背景，研 究现状及方法。 第2 章主要介绍高维空间球集最小球覆盖问题及其求解算法。在本章中，我 们提出了球集直径的概念，给出了求解球集直径的近似算法，并证明了该算法至 少可以得到1 3 直径近似。基于此算法求解出大小为0 0 占) 的核心集，给出了 高维空间球集m e b 问题的1 + s 近似算法。 山东大学硕士学位论文 第3 章介绍圆集最小圆覆盖问题的各种求解算法。通过引入第2 章中核心集 的思想及其算法，得到利用核心集求解圆集最小圆覆盖问题的1 + s 近似算法。本 章通过对各种算法大量的实验对比，得出相关结论： 通过利用核心集求解最小圆覆盖问题的算法与已知各种算法的对比，表明利 用核心集求解最小圆覆盖问题的算法运行效率更高。 通过分析已知的各种求解最小圆覆盖问题的算法，得出它们之间运行效率的 差别。 第4 章对本论文进行了总结。 4 山东大学硕士学位论文 2 1 问题简介 第2 章高维空间球集覆盖问题 本章中将引用到下面两篇论文中的思想。 b f i d o i u 掣9 1 提出了核心集的概念及其在高维空间点集m e b 问题近似算法设 计中的应用。k u m a r 掣1 2 1 设计了一个点集上利用核心集求解高维空间m e b 问题 的近似算法，其中核心集大小为0 ( 1 占1 。 给定集合s = 岛，6 ：，吒，包为d 维空间的球，其球心记为q ，半径记为，；。 最小覆盖球m e b 倒是指半径最小且覆盖集合s 的球，记为曰，c 。为m e b ( s ) 的 球心，为m e b ( s ) 的半径。给定s 0 ，xcs ，b c ，= m e b ( x ) ，如果将球e 。， 的半径，扩大1 + 倍后，眈，( ) ，覆盖集合s ，则称x 为一个核心集，称色，( 。+ ，) ，为 m e b ( s ) 的1 + 占近似。 本文提出球集直径的概念，给出了求解球集直径的近似算法，并证明了该算 法至少可以得到l 3 直径近似。基于此算法求解出大小为o ( 1 6 1 的核心集，给 出了高维空间球集m e b 问题的1 + s 近似算法。 第2 2 节将提出球集直径的概念，利用球集直径的近似算法求得初始核心集， 得到一个覆盖初始核心集的球，该球可以尽可能多的覆盖s 中的球；第2 3 节将 介绍求解m e b ( s ) 的1 + g 近似算法；第2 4 节介绍算法实现和实验结果。 2 2 球集直径及初始核心集 定义2 1 ：若两球气，。，b e , ，吃满足，。不包含钆：，您而且，您不包含气，气，两球 之间的距离定义为历sb 叫，屹) = j ( q , c 2 ) + 巧+ r 2 。若疣为球集s 中两球距离 的最大值，称d i s s 为球集s 的直径。 定义2 2 ：1 1 1 若两球6 ，b c ：，r 2 满足气， 不包含6 吒，吃而且，屹不包含，。，球 b e , ，。至a j b 。：，吃的距离定义为以( 气b e , ，屹) = d ( c 1 , c 2 ) + 巧。f s ( b 。，s ) 定义为球集s 山东大学硕士学位论文 中距离阮，最远的球。 o m e re 莒e c i o 誊l u 等 1 2 1 x 寸- a 集直径近似问题进行了讨论。下面我们讨论球集直 径近似问题。 从球集s 中任意选取一球b s ，寻找一球b 。s ，使得6 l = 只( 6 ，s ) ， 呓= 蟊 ，6 ) ，取b l 上距离球b 球心最远的一点q ；寻找一球b ：s ，使得 b ：= b ( g ，s ) ，名= 以( 6 2 ，q ) 。如图2 1 所示。 6 l 目 图2 1 寻找最远球 定理2 1 ：由上述方法取得的满足历( 1 万) 历。 证明：很明显，d s j 成立。下面证明定理后半部分。给定一球6 r 2 ， r 0 ，定义s ( 6 ，) = x r 。4 ( x ，6 ) ， 。我们可以得出结论- o 2 ) d z , s 。 为了得到更准确的下界值，考虑集合j ( 6 ，吃) n s q ，) 的直径，即 m a x d ( 工，y ) ：x ，y s ( 6 ，吃) n s 7q ，) ) 如图2 2 所示a 直线g c 。与以q 为球心，以为半径的球交于一点p ，满足 p = q + ( r q l r 6 ) ( c b q ) 。因为r q ，如果x s7 ( 6 ，) ，则球x 上任意一点p 满足 d ( p ：p ) d ( p ，c 6 ) + d ( 吃，p ) + 名一吃= 乞，由s ( 6 ，| ) 的定义知，球x s ( p ，r ) 。 6 图2 2 寻找一点p ，使得= d ( 9 ，p ) 考虑集合 s r p ，) n s q ，) 的直径。不失一般性，假设= 1 ，g = ( 一l 2 ，o ) ， p = ( 1 2 ，0 ) ，求s ( p ，1 ) c 、s ( g ，1 ) 的直径可以转化为下列非线性优化问题 m a x d ( x ，y ) s t + 1 + 1 + 蚝1 + 以1 其中x = ( 五，x 2 ，x k ) ，y = ( y l ，耽，虼) 。由三角不等式性质，可将问题转 化为下述等价问题 s t m a x 2 d ( x ，y ) 令g ( 五) = m i n1 一( 五十1 2 ) 2 ，1 一( 五一1 2 ) 2 ) ，则将问题转化为 j t 一1 2 x l 1 2 7 + + + + 谚躬 + + + + 2 2 2 2 、j，u，v， 2 2 2 2 v v v v + 一 + + 葺m h“ ，_i_j、_j_i、 ，_ 1 _ j - o 2 ) r ( 1 ( 2 压) ) 盔曲。 2 3l + s 近似算法 我们在第2 2 节计算出初始核心集墨，算法2 1 利用核心集求解球集m e b ( s ) 问题。 算法2 1 ：l + s 近似算法 输入：球集s ，参数s 0 ，初始核心集x 。cs 输出：m e b ( s ) 的1 + s 近似和大小为0 ( 1 8 1 的核心集x l ：x 。, - - x 。 2 ：l o o p 3 ： c o m p u t e 皿，= m e b ( x ) u s i n g s o c p 4 ： i fsc b ，( 1 + 。) ，t h e n 5 ：r e t u r nb c ”x 7 ：b 七- - m a xd s ( h i 9 统，) ，6 f s 8 ：e n di f 9 ：x 卜x w b ) 1 0 ：e n dl o o p 由算法2 1 得到的核心集x 存在如下引理 引理2 , 1 ：【9 】【1 4 】上述算法每循环一次，b 半径至少增加s 2 h 6 倍，即 ( 1 + ( s 2 1 6 ) ) i 。 为了得到更为准确的核心集x ，不失一般性，假设s = l 2 ”，当 t = 1 2 ( i = 1 , 2 ，m ) ，由算法2 1 可以得到m e b ( s ) 的1 + 毛近似。考虑当 岛+ l = l 2 件1 时，同理可以得到m e b ( s ) 的1 + s 州近似。设由i 到f + 1 ，核心集x 中 增加球的个数为n i + l , 则存在如下引理 引理2 3 ：1 1 2 当s 中球的半径为0 ( 即为点集时) 刀m 2 件6 。 引理2 4 ：【1 2 】引理2 3 对于球集s 仍然成立。 如【1 2 】中对引理2 3 证明。当岛= l 2 时，调用算法2 1 得到m e b ( s ) 的l + 乞 近似，此时有( 1 + 弓) ，；矿，；。当q + 1 = 1 2 “1 时，调用算法2 1 后得到m e b ( s ) 的1 + g 州近似，由引理2 1 知，每次循环半径至少增加( 2 。1 6 ) r ，= 二- 2 i - 6 ，；，则 ( 1 + 2 一) ，；+ 1 ，；+ 伤+ 1 2 - 2 i - 6 ，；，得到1 2 件6 定理2 2 ：算法2 1 求得的核心集x 的大小为d ( 班) 。 证明：核心集x 的大小等于x 。与加入到x 中球个数的总和，即 i 卅2 + 玛= o ( ) = o ( 1 g ) 。 算法2 1 中求解初始核心集需要d ( 疗j ) ，总共需要循环d ( 1 占) ，每次调用 舳c p 求解m 晒( 工) 需要d ( ( d 2 石) ( 1 占+ j ) 1 。g ( 1 占) ) ，求距离皖，最远的球需要 o ( 刀d ) ，所以算法2 1 的时间复杂度为d ( 刀a s + ( d 2 s 纠2 ) o s + d ) l o g ( 1 s ) ) 。 2 4s o c p 介绍及实验结果 2 , 4 1s o c p 介绍 为： s o c p 可以看作是二次锥替代非负象限的扩展的线性规划问题。二次锥定义 k = ( 仃，x ) r 1 + d ：1 1 4 _ 0 。 下面给出该算法的几何解释a 每次循环寻找距离点( 砟，以) 最远的圆，从点 ( x k ，儿) 到每个圆q 的距离呸= ( q x ) 2 + 一儿) 2 + ，；，扛1 ，2 ，刀，。如果仅仅 有一个最远的圆，则向( a i t 包- y ) 方向移动点( 吆，y k ) 以减小最小覆盖圆的半 径：若多于一个圆：以i f ，) ，那么将点( ，儿) 向 1 1 1 i n | - 钞( ，儿) i i ，i ，) 方向 移动。 假设算法3 1 的解与最优解差值不大于s ，算法3 1 至多循g o ( 1 e 2 ) 次， 每次循环需d ( 刀) 时间，因此，该算法的时间复杂度为o ( n s 2 1 。 实验结果如第3 4 2 节所示。 3 2 3 二次规划 最小覆盖圆可以通过凸二次规划( c o n v e xq u a d r a t i cp r o g r a m m i n g ) 求解。为 了求解该问题，首先引入一+ n 的变n o ，对于确定值尺m 觚 ，；，l f ，2 ) ，考 虑公式( 3 3 ) m i n0 j t ( x q ) 2 + ( y 一岛) 2 臼( r i ) 2 f = l ，2 ，刀 ( 3 3 ) 存在如下定理： 定理3 1 ：公式( 3 3 ) 与公式( 3 1 ) 等价，若( x ，少，r 。) 是( 3 1 ) 的最优解 当且仅当r = r 。，( x ，y ，0 ) 是( 3 3 ) 的最优解。 证明：若( x 。，y 。，r ) 是( 3 1 ) 的最优解，则对于尺= r ，( x 。，y ，o ) 是( 3 3 ) 的最优解。由公式( 3 3 ) 对于解( x ，j ，o ) 的可行性可知，0 。0 。很明显，0 0 ，那么( i ，罗，r ) 是 使得( 3 3 ) 严格不等式成立的可行解，因此，f 不是( 3 3 ) 的最优解，臼+ 0 不 可能成立。因此0 = 0 。 反过来，如果( 3 3 ) 的最优解0 = 0 ，则尺等于( 3 3 ) 的最优解彤。否则， 若r ， q ，c 2 ) ，很容易计算 包含两个圆的最小圆，圆心为两球距离的中点，半径为两球距离的一半。 当刀3 时，由推论3 1 知，最小覆盖球是由召决定的。只需要求解曲伊，矽。 1 9 山东大学硕士学位论文 如果i b i = 1 ，2 ， s b 伊，剀为s 6 ( q ) ， q ) ) 或者s b ( q ，c ：) ， q ，巴 ) ：如果1 b l 3 ， 任取b 中三个圆，求解如下等式： ( z q ) 2 + ( y 一岛) 2 = ( r - r x ) 2 ( x - a 2 ) 2 + ( y 一如) 2 = ( r 一吃) 2 ( z 一口3 ) 2 + ( y b 3 ) 2 = ( r 一吩) 2 ( 3 6 ) ( 3 7 ) ， ( 3 7 ) ( 3 8 ) ， ( 3 8 ) ( 3 6 ) 得到： 2 ( a 2 一a 1 ) x + 2 ( b 2 一岛) y + 2 ( 一r 2 ) r = 2 一q 2 一岛2 一( 吃2 一口2 2 一吃2 ) 2 ( a 3 一a 1 ) x + 2 ( b 3 6 1 ) y + 2 ( _ 一，3 ) r = 吒2 一q 2 一岛2 一( 吃2 一口3 2 一吃2 ) ( 3 6 ) ， ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 2 ( a 2 一a 3 ) z + 2 ( b 2 一b 3 ) y + 2 ( r 3 一吃) r = r 3 2 一a 3 2 一乞2 一( 吃2 一a 2 2 6 2 2 ) ( 3 1 1 ) 从等式( 3 9 ) ，( 3 1 0 ) ，( 3 1 1 ) 中取两个等式，假设a ：0 1 ，a 3 q ，得到： x + 粤a 2a 1y + 导a 2a l = 垄氆2 ( 差a 2a i 塑 ( 3 1 2 ) 一一一 j z + 鱼l 二垒y + 量二垒：量：二鱼：二刍：二! 刍：二1 2 ：二塾：!( 3 1 3 ) a 3 一q 。a 3 一a 12 ( a 3 一q ) 、7 求解公式( 3 1 2 ) ，( 3 1 3 ) 得到： x ：f 生：二! ! ：二刍：二延：二丝：二丝2 一量：二鱼：二刍：二! 蔓二堡2 ：二刍21 ，l2 2 一哆)、2 m “、( 3 1 4 ) - - 、v 2 1v l ( 鲁一嚣h 焉一糕 ( 嚣一嚣 p 二鱼：二刍：二! 垒：二竺2 ：二丝：! 一生：二堡! ：二刍：二! 刍：二! 二! 1 2 ( a 2 一a i )2 ( a 3 一q ) 一粤h焉一一a3-a1(必-a，一再b3-bla3 a 1a 2a 3 一 l q ，、一q v ( 3 1 5 ) 将等式( 3 1 4 ) ，( 4 1 5 )