徐 弈， 陳 瑩

（1.西安理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，陜西 西安710054；2.西安交通大學(xué) 管理學(xué)院，陜西 西安710049）

0 引言

近些年，選址問(wèn)題中的二中心問(wèn)題及其擴(kuò)展問(wèn)題已成為主要的研究方向之一，其中平面點(diǎn)集的二中心問(wèn)題更是人們關(guān)注的重點(diǎn)問(wèn)題，該問(wèn)題定義如下：給定平面點(diǎn)集P，求兩個(gè)圓的并覆蓋整個(gè)點(diǎn)集，使得兩個(gè)圓半徑的最大值最小。Drezner在1984年首次給出了O（n3）時(shí)間復(fù)雜性的算法［1］。1994年，Agarwal和Sharir兩人給出了第一個(gè)接近平方級(jí)別的算法—O（n2log3n）的確定時(shí)間算法［2］，而該算法的中心思想來(lái)源于Hershberger和Suri兩人于1991年給出的二中心問(wèn)題的判定問(wèn)題解法［3］。所謂判定問(wèn)題，即為給定半徑r＞0，問(wèn)是否存在兩個(gè)半徑為r的全等圓覆蓋P。他們給出這個(gè)判定問(wèn)題可以在O（nlogn）的時(shí)間內(nèi)求解。緊接著在1994年，Jaromczyk和Kowaluk給出了O（n2logn）時(shí)間復(fù)雜性的算法［4］。作為一個(gè)突破，通過(guò)結(jié)合之前Hershberger和Suri提出的判定問(wèn)題解法，1997年Sharir利用參數(shù)搜索技巧設(shè)計(jì)并行算法，將求解二中心問(wèn)題的時(shí)間復(fù)雜性降到了O（nlog9n）［5］，這是歷史上第一個(gè)接近線性時(shí)間的確定算法。同年，同樣運(yùn)用參數(shù)搜索設(shè)計(jì)并行算法，Eppstein給出了O（nlog2n）的期望時(shí)間算法［6］。1999年，Chan對(duì)Sharir給出的算法又做了進(jìn)一步改進(jìn)，給出了到目前為止最快的算法，其時(shí)間復(fù)雜性為O（nlog2nlog2logn）［7］。對(duì)離散二中心問(wèn)題，即限定兩個(gè)圓的圓心在點(diǎn)集P內(nèi)，Hershberger和Suri在他們求解判定問(wèn)題的文章中給出離散二中心問(wèn)題可以在O（n2logn）時(shí)間內(nèi)求解［3］。通過(guò)運(yùn)用Katz和Sharir提出的幾何優(yōu)化問(wèn)題中的擴(kuò)展方法，Agarwal和Sharir等人給出目前為止最快的算法，其時(shí)間復(fù)雜性為O（n4/3log5n）［8］。而二中心問(wèn)題的在線情況，由Zhu等人于2013年提出并給出近似比為5.611的近似算法［9］，接著該問(wèn)題在2015年被Kim等人將近似比改進(jìn)到1.865［10］。

本文著重討論二中心問(wèn)題的一個(gè)擴(kuò)展問(wèn)題-最小最大二點(diǎn)集覆蓋問(wèn)題，并對(duì)該問(wèn)題已有算法進(jìn)行改進(jìn)。2003年，Huang等人考慮了α連通二中心問(wèn)題［11］。他們首先考慮這個(gè)問(wèn)題的判定問(wèn)題，即：給定半徑r＞0，是否存在兩個(gè)半徑為r的全等圓，使兩圓的并覆蓋P并且圓心距與半徑之比小于常數(shù)α。通過(guò)最遠(yuǎn)點(diǎn)Voronoi圖與點(diǎn)集中心包的關(guān)系，他們給出這個(gè)問(wèn)題的判定問(wèn)題可以在O（n2log2n）的時(shí)間內(nèi)求解。接著在2006年，通過(guò)運(yùn)用參數(shù)搜索設(shè)計(jì)并行算法，他們給出α連通二中心問(wèn)題可以在O（n2log2n）的期望時(shí)間內(nèi)求解［12］。2019年，Xu等人考慮這個(gè)問(wèn)題的衍生問(wèn)題，即圓心限制在點(diǎn)集內(nèi)部的混合與離散情況，對(duì)這兩種情況他們分別給出復(fù)雜性為O（n2log2n）和O（n2logn）時(shí)間的確定算法［13］。2014年，Kavand提出了（n，1，1，α）中心問(wèn)題，即求解兩個(gè)圓使其分別覆蓋點(diǎn)集P，滿足其圓心距不小于α且大圓的半徑最?。?4］。通過(guò)運(yùn)用最遠(yuǎn)點(diǎn)Voronoi圖［15～17］，他們證明該問(wèn)題最優(yōu)解的兩個(gè)圓一定全等，并且給出O（nlogn）時(shí)間復(fù)雜性的算法。本文所考慮的最小最大二點(diǎn)集覆蓋問(wèn)題也可以看成是二中心問(wèn)題的擴(kuò)展問(wèn)題，問(wèn)題的描述如下：

問(wèn)題1給定兩個(gè)平面點(diǎn)集P1和P2，分別包含m和n個(gè)點(diǎn)，求兩個(gè)圓分別覆蓋P1和P2，滿足兩個(gè)圓的半徑與圓心距三者中的最大值最小。

對(duì)該問(wèn)題，2006年Huang等人通過(guò)運(yùn)用參數(shù)搜索設(shè)計(jì)并行算法給出這個(gè)問(wèn)題可以在O（（m+n）log（m+n））的確定時(shí)間內(nèi)求解［9］。但是注意到，他們所設(shè)計(jì)的并行算法，需要處理器的個(gè)數(shù)為O（m+n），而當(dāng)m和n足夠大時(shí)，這是不可能實(shí)現(xiàn)的。為了改進(jìn)這個(gè)缺陷，本文同樣給出接近線性時(shí)間的確定時(shí)間算法，但是與之不同的是本文提出的算法不需要運(yùn)用并行計(jì)算，從而大大提高了算法的可實(shí)現(xiàn)性.本文結(jié)構(gòu)如下：第1節(jié)回顧點(diǎn)集的最遠(yuǎn)點(diǎn)Voronoi圖與點(diǎn)集中心包的關(guān)系；第2節(jié)給出最小最大二點(diǎn)集覆蓋問(wèn)題的最優(yōu)解幾何結(jié)構(gòu)；第3節(jié)重點(diǎn)研究在同一個(gè)半徑變化過(guò)程中，兩個(gè)點(diǎn)集中心包之間的最近距離變化關(guān)系；第4節(jié)通過(guò)該變化關(guān)系設(shè)計(jì)最小最大二點(diǎn)集覆蓋問(wèn)題算法；第5節(jié)給出結(jié)論與展望。

1 最遠(yuǎn)點(diǎn)Voronoi圖與點(diǎn)集中心包關(guān)系

在討論最小最大二點(diǎn)集覆蓋問(wèn)題之前，先給出本文所用到的一些符號(hào)：記P1和P2為平面上分別包含m和n個(gè)點(diǎn)的點(diǎn)集，D（o，r）為以o為圓心，r為半徑的圓盤(pán)，C（o，r）為圓盤(pán)D（o，r）的邊界（即圓圈），稱(chēng)C（o，r）上的點(diǎn)為控制點(diǎn)。對(duì)任意兩點(diǎn)｛x，y｝，記d（x，y）為兩點(diǎn)之間的歐氏距離，lx，y為過(guò)兩點(diǎn)的線段。在討論設(shè)計(jì)算法之前，首先介紹一個(gè)點(diǎn)集的中心包與最遠(yuǎn)點(diǎn)Voronoi圖之間的關(guān)系［11］。對(duì)任意點(diǎn)集P，其對(duì)應(yīng)以r為半徑的中心包定義如下［3，11］：

定義1對(duì)點(diǎn)集P而言，其以r為半徑的中心包CHr（P），是以P中的所有點(diǎn)為圓心，r為半徑的圓盤(pán)的交，即CHr（P）∩p∈PD（p，r）。

對(duì)點(diǎn)集P的中心包，有以下幾個(gè)關(guān)鍵性質(zhì)［11］。

性質(zhì)1記點(diǎn)集P的最小覆蓋圓半徑為r0，則CHr（P）＝?當(dāng)且僅當(dāng)r＜r0。

性質(zhì)2點(diǎn)p在CHr（P）內(nèi)當(dāng)且僅當(dāng)p到P中的最遠(yuǎn)點(diǎn)距離小于等于r。

由性質(zhì)2與最遠(yuǎn)點(diǎn)Voronoi圖的定義，又得到如下性質(zhì)：

性質(zhì)3CHr（P）上的每個(gè)弧在所對(duì)應(yīng)圓心的最遠(yuǎn)點(diǎn)Voronoi區(qū)域內(nèi)。

由性質(zhì)1、性質(zhì)2和性質(zhì)3可以得到以下關(guān)鍵性質(zhì)：

性質(zhì)4點(diǎn)集P的中心包CHr（P）弧的個(gè)數(shù)隨半徑r的變化如下：隨著半徑的增加，每當(dāng)半徑超過(guò)P的最遠(yuǎn)點(diǎn)Voronoi圖的一個(gè)交點(diǎn)到其對(duì)應(yīng)最遠(yuǎn)點(diǎn)之間的距離，則中心包弧的個(gè)數(shù)增加1。

2 最優(yōu)解幾何結(jié)構(gòu)與性質(zhì)

記P1和P2的最小覆蓋圓分別為D（o1，r1）和D（o2，r2）（不失一般性，假設(shè)r1≥r2），同時(shí)令最小最大二點(diǎn)集覆蓋問(wèn)題最優(yōu)解所對(duì)應(yīng)P1和P2的覆蓋圓分別為D（）和D（），由問(wèn)題1可以得到其等價(jià)形式：

問(wèn)題2最小最大二點(diǎn)集覆蓋問(wèn)題等價(jià)于兩個(gè)全等的圓分別覆蓋P1和P2，并且要求半徑與圓心距二者中的最大值最小。

本文著重通過(guò)點(diǎn)集中心包的性質(zhì)來(lái)研究問(wèn)題2。由問(wèn)題2可以看出，此時(shí)最優(yōu)解結(jié)構(gòu)存在兩種情況：

情況1圓心距小于等于圓半徑。

由于兩個(gè)點(diǎn)集P1，P2已經(jīng)給定，因此可以通過(guò)計(jì)算這兩個(gè)點(diǎn)集各自的最小覆蓋圓進(jìn)行檢測(cè)。如果滿足d（o1，o2）≤r1，則此時(shí)已然得到最優(yōu)解；否則，計(jì)算點(diǎn)集P2在r1下的中心包CHr1（P2），如果滿足o1到CHr1（P2）的最短距離小于等于r1，則此時(shí)仍然得到最優(yōu)解，這里取該最近點(diǎn)為覆蓋P2的圓所對(duì)應(yīng)的圓心，r1為覆蓋半徑即可。

情況2圓心距大于圓半徑。

對(duì)這種情況，最優(yōu)解半徑一定大于max｛r1，r2｝。從直觀角度看，這時(shí)需要同時(shí)增加兩個(gè)點(diǎn)集各自覆蓋圓的半徑，并且同時(shí)將兩個(gè)圓的圓心相互靠攏，直到兩圓圓心距與半徑相同時(shí)得到最優(yōu)解。此時(shí)，最優(yōu)解情況可以分為以下三種：

情況2a最優(yōu)解由兩個(gè)控制點(diǎn)決定。

情況2b只有一個(gè)圓有一個(gè)控制點(diǎn)。

情況2c兩個(gè)圓至少都有兩個(gè)控制點(diǎn)。針對(duì)情況2a，此時(shí)有：

引理1這兩個(gè)控制點(diǎn)和兩個(gè)圓心共線。

證明記這兩個(gè)控制點(diǎn)為a和b，其中a∈C（，r），b∈C（，r）。不失一般性，假設(shè)a與兩個(gè)圓心不共線，則一定在的鄰域Nε（）內(nèi)存在一個(gè)新的圓心，使得D（，r）仍然能夠覆蓋P1。同時(shí)，在的鄰域Nε／2（）內(nèi)也一定存在一個(gè)新的圓心，使得D，r-ε／10）能夠覆蓋P2并且滿足d（）＜r，注意到這時(shí)D（，r）和D（，r-ε／10）均不是點(diǎn)集P1和P2的最小覆蓋圓，這意味著一定存在兩個(gè)半徑更小，且兩圓圓心距小于r的圓分別覆蓋P1和P2，這與最優(yōu)解假設(shè)相矛盾（見(jiàn)圖1）。

通過(guò)引理1，直觀地可以看出和一定分別在C（a，r）和C（b，r）上，又因?yàn)椋鸻，b｝為兩個(gè)圓的控制點(diǎn)，再由中心包定義，可以得到和一定分別在CHr（P1）和CHr（P2）的一條弧上。

圖1 引理1說(shuō)明

針對(duì)情況2b，此時(shí)與情況2a類(lèi)似的有：

引理2這個(gè)控制點(diǎn)與兩個(gè)圓心共線。

證明設(shè)b為圓D，r）的唯一控制點(diǎn)。若b不與兩個(gè)圓心共線，則與引理1類(lèi)似的可以證明，一定存在兩個(gè)圓分別覆蓋P1和P2，并且滿足max｛r-ε／10，d（）｝＜r（見(jiàn)圖2）。

圖2 引理2說(shuō)明

由引理2可知，記另一個(gè)圓的兩個(gè)控制點(diǎn)分別為a1和a2，有在C（a1，r）和C（a2，r）的交點(diǎn)上，在C（b，r）上，即有一定在CHr（P1）的一個(gè)頂點(diǎn)上，一定在CHr（P2）的一條弧上。

針對(duì)情況2c，這兩個(gè)圓都至少有兩個(gè)控制點(diǎn)。不失一般性，假設(shè)這兩個(gè)圓各自只有兩個(gè)控制點(diǎn)，按照逆時(shí)針?lè)较?，記為｛a1，a2｝和｛b1，b2｝，可以得到以下最優(yōu)結(jié)構(gòu)

證明假設(shè)D（a1，r）∩D（a2，r）∩D（oS1，r）∩D（oS2，r）不止有oS1這一個(gè)點(diǎn)。則此時(shí)一定存在一個(gè)新的圓心，使得D（，r）能夠覆蓋P1∪滿足此時(shí)的情況有兩種：（1）｛a1，a2｝分布在過(guò)兩圓心的直線lo S1，o S2的同側(cè)（見(jiàn)圖3（a））；（2）∠＞180°（以逆時(shí)針?lè)较?，?jiàn)圖3（b））。此時(shí)，與引理1，引理2證明類(lèi)似，一定存在兩個(gè)半徑更小，且圓心距小于r的圓覆蓋P1和P2。同理可證D（a1，r）∩D（b2，r）∩D（oS1，r）∩D（oS2，r）＝

這時(shí)，在C（a1，r）和C（a2，r）的交點(diǎn)上在C（b1，r）和C（b2，r）的交點(diǎn)上，由｛a1，a2｝和｛b1，b2｝分別為兩圓的控制點(diǎn)，有和分別在CHr（P1）和CHr（P2）的一個(gè)頂點(diǎn)上。下一節(jié)將重點(diǎn)對(duì)這種結(jié)構(gòu)給出相關(guān)分析。

圖3 引理3說(shuō)明

3 兩動(dòng)態(tài)中心包之間最近距離變化分析

本節(jié)對(duì)兩個(gè)動(dòng)態(tài)中心包之間最近距離的幾何結(jié)構(gòu)性質(zhì)進(jìn)行分析。對(duì)給定點(diǎn)集P，Huang等人發(fā)現(xiàn)在半徑的變化過(guò)程中，P的中心包的組合性質(zhì)與點(diǎn)集的最遠(yuǎn)點(diǎn)Voronoi圖緊密相關(guān)（即性質(zhì)4）。基于這個(gè)重要的性質(zhì)，他們提出連通二中心問(wèn)題可以在接近平方級(jí)別的期望時(shí)間內(nèi)求解［11］。然而，在該問(wèn)題的子算法中，牽扯到對(duì)兩個(gè)點(diǎn)集的中心包（假設(shè)兩個(gè)點(diǎn)集分別含有m和n個(gè)點(diǎn)）在同一個(gè)半徑r的變化過(guò)程中，這兩個(gè)中心包的組合性質(zhì)不發(fā)生變化時(shí)如何求解最優(yōu)半徑。他們給出該問(wèn)題可以在O（log2（m+n））的時(shí)間內(nèi)通過(guò)設(shè)計(jì)并行算法來(lái)求解。事實(shí)上，通過(guò)運(yùn)用一些幾何性質(zhì)，這個(gè)子問(wèn)題可以在常數(shù)時(shí)間內(nèi)求解，并且不需要運(yùn)用并行計(jì)算，同時(shí)該算法可以完美求解最小最大二點(diǎn)集覆蓋問(wèn)題。

注意到，對(duì)最優(yōu)解幾何結(jié)構(gòu)的第二種情況，只需要找到一個(gè)臨界半徑，滿足在這個(gè)半徑下CHr（P1）和CHr（P2）之間的最近距離等于該半徑即可。為了解決該問(wèn)題，本節(jié)提出以下三個(gè)關(guān)鍵引理。對(duì)兩個(gè)點(diǎn)集P和Q，在同一個(gè)半徑r下，記這兩個(gè)中心包之間最近距離的控制點(diǎn)分別為s1和s2。首先給出第一個(gè)引理。

引理4若s1和s2分別在CHr（P）和CHr（Q）的一條弧上，則在半徑增加到r′的過(guò)程中，如果兩個(gè)中心包的組合性質(zhì)不發(fā)生變化時(shí)，CHr′（P）和CHr′（Q）之間最近距離的控制點(diǎn)仍在對(duì)應(yīng)兩個(gè)弧上。

證明記s1和s2分別在弧ar和弧br上。連接s1和s2，作兩條直線l1和l2垂直于ls1，s2。此時(shí)有l(wèi)1與弧ar相切，l2與弧br相切（見(jiàn)圖4（a））。由中心包的凸性，可以得到當(dāng)半徑增加到r′時(shí)，CHr′（P）和CHr′（Q）之間最近距離的控制點(diǎn)仍在弧ar′和弧br′上（見(jiàn)圖4（b））。

圖4 引理4說(shuō)明，其中r＜r′，s1和s2均在弧上

圖5 性質(zhì)5說(shuō)明，其中r＜r*＜r′，r*是臨界半徑，此時(shí)l與弧ar*相切

在給出第二個(gè)關(guān)鍵引理之前，先給出一個(gè)性質(zhì)并加以證明：

性質(zhì)5給定三個(gè)點(diǎn)｛a，b，c｝和半徑r，記x為弧ar和弧br的交點(diǎn)，l為過(guò)點(diǎn)x且垂直于lc，s的直線。如果l與弧ar僅有一個(gè)交點(diǎn)x，與弧ar′有不止一個(gè)交點(diǎn)（r＜r′），則一定存在一個(gè)臨界半徑r*，使得l與弧ar*相切。

證明當(dāng)半徑為r時(shí)，直線l與弧ar相交于x點(diǎn)（見(jiàn)圖5（a））；當(dāng)半徑為r′時(shí)，l與弧ar′相交于x和y點(diǎn)，同時(shí)注意到此時(shí)有y在弧ar′上（見(jiàn)圖5（c））。因此，隨著半徑的增加，可以得到a點(diǎn)從直線lc，x的一側(cè)連續(xù)移動(dòng)到另一側(cè)，則一定存在一個(gè)臨界半徑r*使得｛a，c｝和x是共線的。這時(shí)，l與C（a，r*）相切（見(jiàn)圖5（b））。

由上述事實(shí)，給出第二個(gè)關(guān)鍵引理。

引理5假設(shè)s1為弧ar和弧cr的交點(diǎn)，s2在弧br上，其中｛a，b，c｝為圓心。在半徑從r增加到r′的過(guò)程中，如果兩個(gè)中心包的組合性質(zhì)不發(fā)生變化，則這兩個(gè)中心包CHr′（P）和CHr′（Q）之間的最近距離對(duì)應(yīng)的兩個(gè)控制點(diǎn)有如下三種情形：（1）仍然是一個(gè)為弧ar′和弧cr′的交點(diǎn)，另一個(gè)在弧br′上；（2）一個(gè)在弧ar′上，另一個(gè)在弧br′上；（3）一個(gè)在弧cr′上，另一個(gè)在弧br′上。

證明令s1′和s2′為CHr′（P）和CHr′（Q）之間最近距離的兩個(gè)控制點(diǎn)，由引理2，有｛b，s1，s2｝三點(diǎn)共線。連接s1和s2，過(guò)s1和s2分別作l1和l2垂直于ls1，s2，則有l(wèi)2與弧br相切。因?yàn)樵诎霃皆黾拥絩′的過(guò)程中，兩中心包的組合性質(zhì)不發(fā)生變化，則有：如果沒(méi)有弧與l1相交，則由于變化過(guò)程拓?fù)浣Y(jié)構(gòu)不發(fā)生變化，兩中心包最近距離的控制點(diǎn)仍舊落在弧ar′和弧cr′的交點(diǎn)以及弧br′上；否則，由于中心包的凸性，只會(huì)有CHr′（P）的一條弧與l1相交（不可能有大于一條弧與l1相交，如此做中心包則不為凸），不失一般性，假設(shè)弧cr′與l1相交。

接下來(lái)證明只有在弧cr′上的點(diǎn)有可能是距離弧br′最近的點(diǎn)。由于在半徑增加的過(guò)程中，弧cr′與l1產(chǎn)生了第二個(gè)交點(diǎn)（除去s1′），由性質(zhì)5可以得到，一定存在一個(gè)臨界半徑r*，使得弧cr*與l1相切。這時(shí)中心包CHr*（P）和CHr*（Q）最近距離的兩控制點(diǎn)均在兩條弧上，再由引理4，?r′≥r*，CHr′（P）和CHr′（Q）最近距離的兩控制點(diǎn)一定一直在兩條弧上（即當(dāng)r′≥r*時(shí)，此時(shí)與引理4情況相同）。圖6給出一個(gè)例子，其中r1＜r2＜r3，r2是臨界半徑。當(dāng)半徑r′＞r2時(shí)，兩個(gè)中心包之間最近距離的兩控制點(diǎn)為一個(gè)在弧cr′上，一個(gè)在弧br′上。同理可證弧ar′與l1相交的情況。

圖6 引理5示例，r1＜r2＜r3，r2是臨界半徑。l1與弧cr2相切，s1′在弧cr3上，s2′在弧br3上

最后給出第三個(gè)關(guān)鍵引理。

引理6記s1為弧ar和弧cr的交點(diǎn)，s2為弧br和弧d r的交點(diǎn)，其中｛a，b，c，d｝為圓心。在半徑從r增加到r′的過(guò)程中，如果兩個(gè)中心包的組合性質(zhì)不發(fā)生變化，則這兩個(gè)中心包CHr′（P）和CHr′（Q）之間最近距離對(duì)應(yīng)的兩個(gè)控制點(diǎn)有如下三種情形：（1）一個(gè)在弧上cr′，另一個(gè)在弧上br′；或者一個(gè)在弧ar′上，另一個(gè)在弧d r′上；（2）一個(gè)是弧ar′和弧cr′的交點(diǎn)，另一個(gè)在弧br′或弧d r′上；或者一個(gè)是 弧br′和 弧d r′的 交 點(diǎn)，另 一 個(gè) 在 弧ar′或 弧cr′上；（3）一個(gè)是弧ar′和弧cr′的交點(diǎn)，另一個(gè)是弧br′和 弧d r′的 交 點(diǎn)。

證明令s1′和s2′為CHr′（P）到CHr′（Q）最近距離的兩個(gè)控制點(diǎn)。連接s1和s2，過(guò)s1和s2分別作l1和l2垂直于ls1，s2。當(dāng)半徑增加到r′時(shí)，由于兩個(gè)中心包的組合性質(zhì)不發(fā)生變化，只會(huì)分別有CHr′（P）到CHr′（Q）的一段弧與l1和l2相交。接下來(lái)給出，如果弧cr′與l1相交，則只可能弧br′與l2相交。否則，假設(shè)弧d r′與l2相交，記這時(shí)CHr′（P）到CHr′（Q）最近距離的兩控制點(diǎn)為u和v，其中u在弧cr′上，v在弧d r′上。由于兩個(gè)中心包的半徑增加速度是一致的，并且由中心包的凸性，u和v之間的距離不可能小于d（）（否則中心包不為凸，或者其中一個(gè)中心包每條弧增長(zhǎng)速度不一致），因此，弧d r′不可能與l2相交。同理可以證明如果弧ar′與l1相交，則只可能弧d r′與l2相交。隨著半徑繼續(xù)增加，會(huì)發(fā)生如下幾種情況。

情況1在半徑增加到r′的過(guò)程中，存在兩個(gè)臨界半徑和），其中當(dāng)半徑增加到時(shí)，弧cr*1與l1相切，當(dāng)半徑增加到時(shí)，弧br*2與l2相切。則根據(jù)半徑增加過(guò)程中兩個(gè)中心包的組合性質(zhì)不發(fā)生變化，?r1≤，CHr1（P）和CHr1（Q）之間最近距離控制點(diǎn)為弧ar1和弧cr1的交點(diǎn)以及弧br1和弧d r1的交點(diǎn)；?，由引理5，CHr2（P）和CHr2（Q）之間最近距離的兩控制點(diǎn)一個(gè)在弧上，另一個(gè)為弧br2和弧d r2的交點(diǎn)；，由引理4，CHr3（P）和CHr3（Q）之間最近距離的兩控制點(diǎn)一個(gè)在弧cr3上，一個(gè)在弧br3上。此時(shí)，有l(wèi)b，c與CHr3（P）和CHr3（Q）在弧cr3和弧br3均有交點(diǎn)，并且兩交點(diǎn)即為兩中心包最近距離控制點(diǎn)。圖7給出一個(gè)例子，其中r1＜r2＜r3＜r4，r2和r3為臨界半徑。當(dāng)r＝r2時(shí)，l1與弧cr2相切；當(dāng)r＝r3時(shí)，l2與弧br1相切；當(dāng)半徑繼續(xù)增加到r4，則兩中心包的最近距離控制點(diǎn)s1′和s2′分別在弧cr4和弧br4上。

情況2在半徑增加到r′的過(guò)程中，假設(shè)存在一個(gè)臨界半徑r*。當(dāng)半徑增加到r*時(shí)，l1與弧ar*和弧cr*均不相交，而l2與弧br*或弧d r*其中之一相切（l1與弧ar*或弧cr*其中之一相切，l2與弧br*和弧d r*均不相交的證明類(lèi)似），則在半徑從r增加到r′的過(guò)程中，CHr′（P）與CHr′（Q）的最近距離的控制點(diǎn)一個(gè)為弧ar′和cr′的交點(diǎn)，另一個(gè)在弧br′上或弧d r′上（當(dāng)r′≥r*），或者為弧br′與弧d r′的交點(diǎn)（當(dāng)r′＜r*）。

情況3在半徑增加到r′的過(guò)程中，如果l1與弧ar′和弧均不相切，l2與弧和弧d r′均不相切，則在半徑增加過(guò)程中，CHr′（P）與CHr′（Q）之間最近距離的兩控制點(diǎn)仍為兩個(gè)弧的交點(diǎn)。至此，完成了對(duì)引理的全部證明。

圖7 引理6示例，r1＜r2＜r3＜r4，r2和r3為臨界半徑，當(dāng)r＝r2時(shí)，l1與弧cr2相切；當(dāng)r＝r3時(shí)，l2與弧br3相切；s1′在弧cr4上，s2′在弧br4上

4 算法設(shè)計(jì)與分析

這一節(jié)給出最小最大二點(diǎn)集覆蓋問(wèn)題的確定性算法設(shè)計(jì)并分析算法復(fù)雜性，具體算法流程見(jiàn)Algorithm 1。

算法第1行計(jì)算點(diǎn)集P1和P2的最小覆蓋圓［18］，這部分可以在O（m+n）的時(shí)間內(nèi)完成。

算法第2行到第3行，檢查是否滿足d（o1，o2）≤max｛r1，r2｝。如果是，則已然得到最優(yōu)解。該檢測(cè)可以在常數(shù)時(shí)間內(nèi)完成。

算法第5行計(jì)算一個(gè)點(diǎn)到一個(gè)中心包的最近距離，這一步可以在O（log（m+n））的時(shí)間內(nèi)求出［19］。

算法第6行到第7行，檢查是否滿足min｛d1，d2｝≤max｛r1，r2｝。如果是，則已然得到最優(yōu)解。該檢測(cè)同樣可以在O（log（m+n））常數(shù)時(shí)間內(nèi)完成。故第5行到7行總共可以在O（log（m+n））的時(shí)間內(nèi)完成。

算法第9行到第12行，是在如果上述兩種情況都不滿足的情況下，第9行首先分別計(jì)算P1和P2的最遠(yuǎn)點(diǎn)Voronoi圖，該過(guò)程可以在O（mlogm）和O（nlogn）的時(shí)間內(nèi)完成。

算法第10行分別計(jì)算P1和P2的臨界半徑，這個(gè)過(guò)程可以在O（mlogm）和O（nlogn）的時(shí)間內(nèi)完成。

算法第11行計(jì)算最優(yōu)解區(qū)間，將這兩個(gè)點(diǎn)集的所有臨界半徑合并排序，這可以在O（（m+n）log（m+n））的時(shí)間內(nèi)完成；對(duì)每一個(gè)臨界半徑，可以在O（m+n）的時(shí)間內(nèi)求出兩個(gè)點(diǎn)集的中心包［3］，在O（log（m+n））的時(shí)間可以求出這兩個(gè)中心包之間的最近距離［19］。因此，可以通過(guò)二分查找，在O（（m+n）log（m+n））的時(shí)間內(nèi)找出一個(gè)包含最優(yōu)半徑的臨界區(qū)間（rl，rh］。在該半徑區(qū)間內(nèi)，隨著半徑的變化兩中心包的組合性質(zhì)不會(huì)發(fā)生變化，同時(shí)滿足當(dāng)半徑取rl時(shí)，中心包CHrl（P1）和CHrl（P2）之間的最近距離大于rl，當(dāng)半徑取rh時(shí)，中心包CHrh（P1）和CHrh（P2）之間的最近距離小于rh。

算法第12行求解最優(yōu)圓心及半徑，在文獻(xiàn)［11］中，Huang等人給出求解最優(yōu)半徑需要通過(guò)并行計(jì)算的方法在O（log2（m+n））的時(shí)間內(nèi)求解。由引理4、引理5和引理6可以設(shè)計(jì)算法并得出最優(yōu)半徑可以在常數(shù)時(shí)間內(nèi)求解。當(dāng)r∈（rl，rh］，兩個(gè)中心包CHr（P1）和CHr（P2）變化過(guò)程中其組合性質(zhì)不發(fā)生變化。記s1和s2是中心包CHrh（P1）和CHrh（P2）之間最近距離的控制點(diǎn)，這里分三種情況進(jìn)行分析，其符號(hào)表示與上一節(jié)相同：

情況1若s1和s2分別是弧arh和弧crh，弧brh和弧d rh的交點(diǎn)。?r∈（rl，rh］，一定滿足CHr（P1）和CHr（P2）之間最近距離的控制點(diǎn)分別是弧ar和弧cr，弧br和弧d r的交點(diǎn)。因此只需要找到兩個(gè)點(diǎn)滿足這兩點(diǎn)之間距離以及兩點(diǎn)分別到｛a，c｝和｛b，d｝的距離全部相等，記這兩個(gè)點(diǎn)為所求圓心即可。該計(jì)算在常數(shù)時(shí)間內(nèi)即可完成。

情況2若s1和s2其中之一在弧上，不失一般性，假設(shè)s2在弧brh上。?r∈（rl，rh］，CHr（P1）的控制點(diǎn)一定是弧ar和弧cr的交點(diǎn)，但是CHr（P2）的控制點(diǎn)有可能在弧br上，也可能是弧br和弧d r的交點(diǎn)。因此，需要通過(guò)5次計(jì)算：不僅需要找到兩點(diǎn)滿足兩點(diǎn)之間距離以及兩點(diǎn)分別到｛a，c｝和｛b，d｝的距離全部相等，還需要找到兩點(diǎn)滿足兩點(diǎn)之間距離以及兩點(diǎn)分別到｛a，c｝和b（｛a，c｝和d，a和｛b，d｝，c和｛b，d｝）的距離全部相等，在滿足的結(jié)果中找出距離最小的兩點(diǎn)作為圓心即可。

情況3若s1和s2均在弧上，不失一般性，假設(shè)s1和s2分別在弧ar和弧br上。?r∈（rl，rh］，有如下幾種可能：CHr（P1）和CHr（P2）的控制點(diǎn)可能在弧ar和弧br上；可能一個(gè)控制點(diǎn)在弧ar上，另一個(gè)為弧br和弧d r的交點(diǎn)；也可能一個(gè)控制點(diǎn)為弧ar和弧cr的交點(diǎn)，另一個(gè)在弧br上；或者一個(gè)控制點(diǎn)為弧ar和弧cr的交點(diǎn)，另一個(gè)為弧br和弧d r的交點(diǎn)。因此，需要通過(guò)7次計(jì)算：不僅需要找到兩點(diǎn)滿足兩點(diǎn)之間距離以及兩點(diǎn)分別到｛a，c｝和｛b，d｝的距離全部相等，還需要找到兩點(diǎn)滿足兩點(diǎn)之間距離以及兩點(diǎn)分別到｛a，c｝和b（｛a，c｝和d，a和｛b，d｝，c和｛b，d｝）的距離全部相等，以及線段la，d和lb，c的兩個(gè)三等分點(diǎn)。接著檢測(cè)計(jì)算出的兩點(diǎn)到各自點(diǎn)集的最遠(yuǎn)點(diǎn)距離是否等于兩點(diǎn)之間距離，最后在滿足的結(jié)果中找出距離最小的兩點(diǎn)作為圓心，因此在臨界區(qū)間內(nèi)找出最優(yōu)半徑可以在常數(shù)時(shí)間內(nèi)完成。故算法第9行到到12行總共可以在O（（m+n）log（m+n））的時(shí)間內(nèi)完成。

綜上所述，可以得到：

定理給定分別包含m和n個(gè)點(diǎn)的兩個(gè)平面點(diǎn)集P1和P2，最小最大二點(diǎn)集覆蓋問(wèn)題可以在O（（m+n）log（m+n））時(shí)間內(nèi)求解。

5 結(jié)論與展望

本文考慮最小最大二點(diǎn)集覆蓋問(wèn)題并給出時(shí)間復(fù)雜性為O（（m+n）log（m+n））的確定時(shí)間算法，其中求解最優(yōu)半徑過(guò)程改進(jìn)了Huang等人提出的并行算法。因?yàn)闊o(wú)論如何算法設(shè)計(jì)一定需要涉及排序這一操作［20］，而排序時(shí)間至少為O（（m+n）log（m+n）），因此本文設(shè)計(jì)的算法是目前為止最好的算法，并且不需要運(yùn)用并行計(jì)算，大大減少了計(jì)算規(guī)模。而如果考慮兩個(gè)圓覆蓋一個(gè)含有n個(gè)點(diǎn)的點(diǎn)集情況，由于需要對(duì)點(diǎn)集進(jìn)行分割，目前最好的算法仍然是Huang等人提出的O（n2logn）期望時(shí)間算法，而該問(wèn)題的確定時(shí)間算法復(fù)雜性為O（n3logn）。因此，針對(duì)該問(wèn)題，改進(jìn)其算法的計(jì)算復(fù)雜性還是很有希望的。