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

一组固定点和一个移动点组成的最小覆盖圆简介许多2D设施的位置问题中，一个设施被放置在一组用户中的平面上，使得该设施到用户的最大距离为最小。当一对点之间的距离（L2度量即：欧几里德度量）被测量时，这里就引出了欧几里德1-中心的概念和一组点的最小外接圆（MEC）的概念。一组固定点S的欧几里德1-中心是最小的圆的中心所包围的S的所有点。更正式地是，如果在R之间的任何两个点A和B，表示为（A，B），其欧几里得距离为d，那么对于一个在R中的有限集S，欧几里德1-中心的s是R中的功能点（S），最小化功能为覆盖所有的点q。（S）的值是S的MEC半径，被表示为R（S）。这些定义也可以自然地扩展到更高的范畴。据言这是第一次使用阿基米德发现的最小圆圈包围三角形的问题。然而在1857年，一组在平面上的n个点的MEC问题首次被西尔维斯特提出。此后，已经提出了若干算法，用于计算一组在平面上n个点的MEC。最后，米吉多给出了在R上确定O（n）时间的线性编程解决方案。这个结果被Agarwal、Chazelle 和Matousek等人发展，并且当D固定时这个方案逐渐最优。一个由Wekzl提出的更简单的随机算法是对于任何固定点D都使用预计的时间0（n）。在移动计算、通信、导航和地理信息系统的最新进展中，已经在移动设置中使用，移动用户沿轨迹移动，相当于点在平面上运动。在连续运动的点中，贝拉等人发起了不断变化的欧氏1中值问题的研究。它们表明，对于任何V 0中，都有一组在Rd（d 2）中的三个点S1，S2，S3。例如：一个单位的运动速度（即两点间的瞬时速度）大于欧几里德1中心的速度（V），那么欧几里德1中心的移动速度在Rd（d 2）中是无限的。这促使逼近欧几里德1中心的速度被其他中心定义为有界速度。另外还发现，平面围成的点构成了有界的连续运动范围内，欧几里德1中心在Rd（d 1）中连续的移动。近日，比特纳等人研究了最小分离圆问题（MEC的双色概括问题）。这个问题的动能变化被后来的张等人所研究。在本文中，我们为n个固定点的集合S和一个沿着直线L移动的点，提供一个具有完整特征的欧几里德1中心的轨迹。选择一个坐标系，使得所述直线L与X轴一致，我们定义中心函数:RR,其中(p)表示MEC的中心，属于在R中的S p 集合,应用于任何在直线L上的 p点（p=(p,0)）。我们表明,该中心函数是一个持续且分段可微的线性函数，Voronoi图的边界上它的每一个微件位于任一S的最远点，或在直线L的平行线上。此外，我们证明了的组合复杂，也就是说，中的可微的碎片数目为0（n）。基于这种结果，我们在Voronoi图型上给出了一个0（n）的时间的简单算法来计算，并给出S的最远点。与中心函数相关联的是，在p =（P，0）L为前提的条件下，可以定义一个半径函数：RR，其中，（p）为SP的MEC半径。我们表明，如果这条直线L不会与S的MEC相交，然后计算出一个点pL，那么当p P时，是呈现严格递减的，并且当p P时呈现严格递增。当L 与S的MEC相交时，我们也证明出了一个类似的结果。预知我们首先介绍了本文的其余部分中使用的符号及定义。对于在平面上任何两个点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所组成的一个封闭圈将是S的MEC，当且仅当线段连接两个点是一个直径S的封闭圈。如果没有四个点的集合S是共圆的，那么在平面中，一组集合S= P1，P2，.，PN构成n个不同的点会被分配到一般的位置。Voronoi图中的S最远点由FV(S)来表示的，是平面细分成n个不相交的部分FV（Pi，S）| PiS，除外界限qR所在的所有点集合的界限处（FV(pi,S)），例如d(q,pi) d(q,pj)，条件是所有的i不等于j。该FV（Pi，S）区域被称为点PiS所在Voronoi图中的最远点单元区域。在R中，一组n个点构成的最远点Voronoi图可以在O(n log n)时间段内被统计出来。关于移动版本中的欧几里得1中心问题，本文讨论由某平面和直线L组成的固定点集S= P1，P2，.，PN，在没有经过任何S集合中的点，其沿另外的点移动的问题。请注意，对于不分布在S的MEC内部且在L上的所有点P，由SP集合组成的MEC总是通过该点。此外，对于在直线L上的点P，该点位于S的MEC内部，SP组成的集合的MEC是其本身。一般来讲，选择一个坐标系统，其中的直线L与水平轴重合。与实数p相关联,其中点P（p = ( p , 0 )）在直线L上。然后我们定义中心函数 : RR，就像(p) = E( S p)并且半径函数 : RR,就像(p) = r ( S p)。因此，该中心功能曲线图是输出S p集合的MEC轨迹，其中点p在直线L 上移动。对于R的任何子集Q，让(Q ) =(p) | p Q 并且(Q ) =(p) | p Q 。正如前面提到的，MEC中心的连续运动问题被研究到移动设备的位置上。另外，事实证明，根据点在平面内的连续和在有限速度运动下的MEC中心是连续移动的，这个结果的一个直接理论是以下内容：事实上4.该中心函数是连续的。使用这些函数的事实是，在下面的章节中，我们证明了函数是一个连续的，分段的且可微的线性函数。还讨论了该中心函数和半径函数的其它性质。中心函数的表征 本节中，对中心函数进行了研究，其特征是点P=（P，0）沿着线在运动，这条线与X轴平行。当给定包含单点的集合S时，我们开始以下观察。观测1若S包含单个点q=（A，B），则函数映射到直线Y=b/2 in R上。现在，我们进行了表征MEC中心的轨迹为在平面内n个点组成的一个集合S= P1，P2，.，PN。表示与该线段的圆圈 pi , pj ，如直径为C( pi , pj )的圆通过pi 和pj。 下面介绍，当集合S只连接两个固定点时，刻画出来的中心函数的特征为：引理3.1对于S =P1，P2，中心函数是一个分段的可微分的线性函数，并且它的每一个细微部分都位于P1，P2的垂直平分线或平行于线L的直线上。证明。开始时，通过假定圆C（P1，P2）不相交于直线L。让1（P1，P2）和2（P1，P2）的垂线到线段P1，P2之间的连线穿过点p1和p2。注意，对于任何点p1（P1，P2），2（P1，P2），三角形PP1 p2为锐角或直角。事实2，这意味着SP集合中的MEC是三角形PQR的外接圆。因此，E（SP）必须位于线段P1，P2的垂直平分线上。假设垂直平分线的线段P1，P2相交于线段 2（P1，P2），P1和P2，1（P1，P2）且焦点为A（P1，P2）和B（P1，P2）。需要注意的是，当p在L（P1，P2）中，E（SP）是在b（P1，P2）中的，并且当p是在（P1，P2）中，那么E（Sp）= a（P1，P2）。当P点从L（P1，P2）移动到（P1，P2）中时，P1 PP2上升和三角P1 PP2外接圆的半径减小。其结果是，E（P，P1，P2）移向点c（P1，P2）处。因此，任何点p1（P1，P2），（P1，P2）的函数都映射到线段b（P1，P2），C（P1，P2）上。同样地，当p（P1，P2），2（P1，P2）的函数映射到线段c（P1，P2），a（P1，P2）上。因此，该线可以分为三个区间，其他两个函数映射到平行于线和第三函数上，且它映射到垂直平分线 pi , p j 上。整个函数被称为是连续的并且每个时间间隔是可微的。当不相交于C ( p1, p2 )时，这套完整的理论就被引证了。使用上述引理时，在一般位置平面上，中心函数为由n个点组成的集合S= P1，P2，.，PN。我们表示从标点PI，PJ和PK看，最远点的Voronoi顶点是等距的，并且从标点PI，PJ看最远点的Voronoi边界是相等的。重点是，点a ( pi , p j )和b ( pi , pj )位于 eij 的边界上。定理3.1该中心的功能 是连续的且分段可微的线性函数。此外，每个微件的功能在远点Voronoi图的边界是平行的。证明。从事实4，我们知道， 是连续的。假定S点在一般位置上，那么对于所有PL，SP集合的MEC可以通过集合S中至多三个点来表示。在每个时间间隔Li上可能会出现下列三种情况：情况1：对于所有的 p Li ， S p集合中的MEC经过三个点pi , p j , pk S。因此对于所有的p Li ，E(S p)集合上的点将固定在最远点（Voronoi 顶点）Vijk上。情况2：对于所有PIi，SP集合的MEC穿过两个点PI，PJS。在这种情况下，问题简化为引理3.1中的问题。因此，对PLi，（P）将映射到边缘Eij的子集上。情况3：对于所有点PLi，SP集合的MEC中通过一个点PiS。因此，对于pi，则函数（p）位于线段 pi , p的中点上。因此，从一个顶点或FV（S）边缘所产生的将映射到平行线L上。由这三种情况的分析的连续性，定理如下：一组固定的点和一个移动的点所连接的MEC的中心轨迹用下图表示，应用了天然里亚尔问题来确定不同的线性微件的中心函数的数目。我们开始解决这个问题，提出以下意见：观察2设P和Q为在线上的两点且P Q。假设，SP集合的MEC和SQ的MEC由圆的直径PI，P和PI，Q组成，那么对于一些固定的点 pi S，所有点P，Q，SR的集合MEC是由直径 pi , r组成的圆。证明。表示由C（PI，p）和C（PI，q）分别得到的直径为 pi , p和 pi ,q的圆圈。设f（PI）是垂直于线上的点pi。观察到S中所有点必须位于该区域，其中两个圆C（PI，p）和C（PI，q）是重叠的。对于任何点rP，Q，圆C（PI，r）的直径pi , r穿过了pi和R，因为射频（PI）PI=/ 2，并且也是S r组成的封闭圆。事实3，现在对于集合S r，圆C（PI，r）是MEC 。观察3设P和Q是直线L上的两个点，且PQ。假设，对于一些固定点PI，PJS，SP集合的MEC和SQ集合的MEC是三角形Pi PjP和Pi P jQ的外接圆。那么对于所有点P，Q，SR集合的MEC是三角形Pi Pj R上的外接圆。使用这两种看法，我们现在证明了有关微件数量的以下结果：定理3.2该函数最多只能有O（n）个微件。证明。定理3.1表示线可以分解