一组固定点和一个移动点组成的最小覆盖圆

《一组固定点和一个移动点组成的最小覆盖圆》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一组固定点和一个移动点组成的最小覆盖圆简介许多2D设施的位置问题中，一个设施被放置在一组用户中的平面上，使得该设施到用户的最大距离为最小。当一对点之间的距离（L2度量即：欧几里德度量）被测量时，这里就引出了欧几里德1-中心的概念和一组点的最小外接圆（MEC）的概念。一组固定点S的欧几里德1-中心是最小的圆的中心所包围的S的所有点。更正式地是，如果在R²之间的任何两个点A和B，表示为（A，B），其欧几里得距离为d，那么对于一个在R²中的有限集S，欧几里德1-中心的s是R²中的功能点ε（S），最小化功能为覆盖所有的点q。λ（

2、ε（S））的值是S的MEC半径，被表示为R（S）。这些定义也可以自然地扩展到更高的范畴。据言这是第一次使用阿基米德发现的最小圆圈包围三角形的问题。然而在1857年，一组在平面上的n个点的MEC问题首次被西尔维斯特提出。此后，已经提出了若干算法，用于计算一组在平面上n个点的MEC。最后，米吉多给出了在R²上确定O（n）时间的线性编程解决方案。这个结果被Agarwal、Chazelle和Matousek等人发展，并且当D固定时这个方案逐渐最优。一个由Wekzl提出的更简单的随机算法是对于任何固定点D都使用预计的时间0（n）。

3、在移动计算、通信、导航和地理信息系统的最新进展中，已经在移动设置中使用，移动用户沿轨迹移动，相当于点在平面上运动。在连续运动的点中，贝拉等人发起了不断变化的欧氏1中值问题的研究。它们表明，对于任何V≥0中，都有一组在Rd（d≥2）中的三个点S1，S2，S3。例如：一个单位的运动速度（即两点间的瞬时速度）大于欧几里德1中心的速度（V），那么欧几里德1中心的移动速度在Rd（d≥2）中是无限的。这促使逼近欧几里德1中心的速度被其他中心定义为有界速度。另外还发现，平面围成的点构成了有界的连续运动范围内，欧几里德1中心在Rd（d≥

4、1）中连续的移动。近日，比特纳等人研究了最小分离圆问题（MEC的双色概括问题）。这个问题的动能变化被后来的张等人所研究。在本文中，我们为n个固定点的集合S和一个沿着直线L移动的点，提供一个具有完整特征的欧几里德1中心的轨迹。选择一个坐标系，使得所述直线L与X轴一致，我们定义中心函数ψ:R→R²,其中ψ(p)表示MEC的中心，属于在R²中的S∪{p}集合,应用于任何在直线L上的p点（p=(p,0)）。我们表明,该中心函数ψ是一个持续且分段可微的线性函数，Voronoi图的边界上它的每一个微件位于任一S的最远点，或在直线L的

5、平行线上。此外，我们证明了ψ的组合复杂，也就是说，ψ中的可微的碎片数目为0（n）。基于这种结果，我们在Voronoi图型上给出了一个0（n）的时间的简单算法来计算ψ，并给出S的最远点。与中心函数相关联的是，在p=（P，0）∈L为前提的条件下，可以定义一个半径函数θ：R→R，其中，θ（p）为S∪{P}的MEC半径。我们表明，如果这条直线L不会与S的MEC相交，然后计算出一个点p⊥∈L，那么当p≤P时，θ是呈现严格递减的，并且当p≥P时呈现严格递增。当L与S的MEC相交时，我们也证明出了一个类似的结果。预知我们首先介绍了本文

6、的其余部分中使用的符号及定义。对于在平面上任何两个点a，b，我们表示由[A，B]的线段连接点a和b。对于在平面的一组点Z，则表示为以MEC的中心点集合Z（由E（Z）和其半径r（Z）表示）。很容易看出，Z的MEC是独特，会被Cmin(Z)所标记。我们现在总结一些MEC的重要性质，这将在随后的章节中使用：事实上1：一组三个点的MEC中心，其点位于直角三角形的各顶点的斜边的中点上。事实上2：通过S的三个点的一组点集S所组成的一个封闭圈将是S的MEC，当且仅当由三个点形成的三角形是锐角或直角。事实上3：通过S的三个点的一组点集S

7、所组成的一个封闭圈将是S的MEC，当且仅当线段连接两个点是一个直径S的封闭圈。如果没有四个点的集合S是共圆的，那么在平面中，一组集合S={P1，P2，...，PN}构成n个不同的点会被分配到一般的位置。Voronoi图中的S最远点由FV(S)来表示的，是平面细分成n个不相交的部分{FV（Pi，S）

8、Pi∈S}，除外界限q∈R²所在的所有点集合的界限处（FV(pi,S)），例如d(q,pi)>d(q,pj)，条件是所有的i不等于j。该FV（Pi，S）区域被称为点Pi∈S所在Voronoi图中的最远点单元区域。在R²中，一组

9、n个点构成的最远点Voronoi图可以在O(nlogn)时间段内被统计出来。关于移动版本中的欧几里得1中心问题，本文讨论由某平面和直线L组成的固定点集S={P1，P2，...，PN}，在没有经过任何S集合中的点，其沿另外的点移动的问题。请注意，对于不分布在S的MEC内部且在L上的所有点P，由S∪{P}集合组成的MEC