论文部分内容阅读
这是一篇关于最小包含球问题及其相关问题的综述.最小包含球问题早在19世纪由Sylvester根据这样的背景提出:(1)社区医院问题:我们将社区中的每户人家看作平面中的一个点,为了社区医院便民,我们要找寻一个最小的圆来将所有人家进行覆盖,我们医院则选址在圆心;(2)军队炸弹投掷问题:我们在作战图上有一些指定爆破目标,我们先寻找一个最小的圆来将爆破目标覆盖,我们在圆心处投放炸弹则可以起到最大破坏作用,同样我们根据所找到的最小的圆的半径来计算炸弹爆炸范围,进而确定需要多少炸药..对于上述两个问题,Sylvester给出了具体模型:给定一个包含n个点的集合,记P:={pi|i=1,...,N}(?)Rn,寻找最小的球Bn(c,r),使得其中Bn(c,r)={x∈Rn|||x-c||≤r}.自问题提出后,人们对这一模型展开的研究进展迅速Elzinga and Hearn在1972年给出了一种(n2)算法,而Shamos和Hoey(1975),Prepara-ta(1977)不Shamos (1978)发现了O(nlogn)算法.让人惊讶的是,在1983年Nimrod Megiddo证明出O(n)次的最小包含球问题可以用线性规划的去除法来计算,之后平面上的最小包含球问题机上算法空前繁荣.随着研究的逐渐深入,人们将研究范围从简单的集合算例扩大到了抽象的范数空间上,希望在范数定义下来更进一步描述最小包含球问题.而最小相交球问题则是对最小相交球问题的一个延展,它是指范数空间中的一系列集合,我们需要寻找出最佳圆心及最小半径,来与所有的集合相交均非空.为此,人们通过引入最小时间函数,以函数分析的方式来对范数空间上的最优化问题进行讨论,通过引入次梯度,仿射锥等概念得出了一系列有意义的成果.本文旨在介绍自人们将研究对象转移到范数空间上以来,最小包含球问题和最小相交球问题相关的一些结果,包括最小包含球问题解存在的条件,唯一解存在的充分条件,不满足唯一性充分条件时可以产生矛盾的反例.另一方面,对于最小相交球,人们给出的解的存在条件,解的唯一性充分条件,不满足唯一性充分条件可以产生矛盾的反例,并且介绍了关于无边界动量集合情形最小时间函数的一些好的性质.