最近點(diǎn)對(duì)問(wèn)題
【想法】最近點(diǎn)對(duì)的分治策略如下。
- 劃分：將集合S分為S1和S2都办，根據(jù)平衡子問(wèn)題的原則每個(gè)子集中大約有n/2個(gè)點(diǎn)，設(shè)集合S的最近點(diǎn)對(duì)是P(i)和P(j)（1 <= i, j <= n），則會(huì)出現(xiàn)以下三種情況揍堰。
-
1.1P(i)∈S1怠缸，P(j)∈S1诗轻，即最近點(diǎn)對(duì)均在S1中； -
1.2P(i)∈S2揭北，P(j)∈S2扳炬，即最近點(diǎn)對(duì)均在S2中； -
1.3P(i)∈S1搔体，P(j)∈S2恨樟，即最近點(diǎn)對(duì)分別在S1和S2中。
- 求解子問(wèn)題：對(duì)于劃分階段的情況1.1和1.2可以遞歸求解疚俱，如果最近對(duì)在1.3的情況就比較復(fù)雜了劝术。
- 合并：分別比較在劃分階段的三種情況下的點(diǎn)對(duì)，取三者之中的距離較小者為問(wèn)題的解呆奕。
下面討論劃分階段1.3的情況养晋。為了將平面上的點(diǎn)集S分割為點(diǎn)的個(gè)數(shù)大致相同的兩個(gè)子集S1和S2，選取垂直線x=m來(lái)作為分割線梁钾，其中绳泉，m為S中各點(diǎn)x坐標(biāo)中位數(shù)。由此將S分割為S1={p∈S1 | x(p)<= m}和S2={q∈S2 | x(q)>m}姆泻。遞歸在S1和S2上零酪，分別得到最近距離d1和d2，令d=min(d1,d2),如果最近對(duì)小于d則屬于1.3的情況拇勃。不妨設(shè)p∈S1,q∈S2,則pq距離x=m距離均小于d蛾娶，所以可以把求解限制在以x=m為中心寬度為2d的垂直帶P1和P2中，垂直帶外任何點(diǎn)對(duì)之間的距離都一定大于d潜秋。
假設(shè)點(diǎn)p(x,y)是集合P1和P2中y坐標(biāo)最小的點(diǎn)蛔琅，則點(diǎn)p可能zaiP1中也可能在P2中，現(xiàn)在需要找出和點(diǎn)p的距離小于d的點(diǎn)顯然這樣的點(diǎn)y坐標(biāo)一定位于[y,y+d]之間峻呛，而且這樣的點(diǎn)不會(huì)超過(guò)八個(gè)罗售，因?yàn)镻1和P2之間的點(diǎn)距離至少為d辜窑。所以可以將P1和P2中的點(diǎn)p(x,y)在y坐標(biāo)區(qū)間按照y坐標(biāo)升序排列，順序處理P1和P2中的點(diǎn)p(x,y)寨躁，在y坐標(biāo)區(qū)間[y,y+d]內(nèi)取出最多8個(gè)候選點(diǎn)穆碎，計(jì)算它們和點(diǎn)p之間的距離。
【算法】簡(jiǎn)單起見(jiàn)职恳。假設(shè)點(diǎn)集S已按x坐標(biāo)升序排列所禀，分治法求解最近對(duì)問(wèn)題的算法偽代碼描述如下。
輸入：按x坐標(biāo)升序排列的n(n>=2)個(gè)點(diǎn)的集合S={(x1,y1),(x2,y2)....(xn,yn)}
輸出：最近點(diǎn)對(duì)的距離
- 如果n等于2放钦，返回兩個(gè)點(diǎn)煎的距離色徘，算法結(jié)束；
- 劃分：m=S中各點(diǎn)坐標(biāo)x的中位數(shù)操禀；
- d1=S1中最近對(duì)距離褂策；
- d2=S2中最近對(duì)的距離；
- d=min(d1,d2);
- 一次考察集合S中的點(diǎn)颓屑，如果（x<=xm&&x>xm-d)則將該店放入P1中斤寂；如果（x>xm&&x<xm+d）,則將點(diǎn)放入P2中；
- 將集合P1和P2按y坐標(biāo)升序排列揪惦；
- 對(duì)集合P1和P2中的每個(gè)點(diǎn)p(x,y),在y坐標(biāo)區(qū)間[y,y+d]內(nèi)最多取出8個(gè)候選點(diǎn)遍搞，計(jì)算與點(diǎn)p的最近距離d3；
- 返回min(d,d3);
github代碼
注：感覺(jué)確實(shí)好長(zhǎng)時(shí)間沒(méi)有簡(jiǎn)書(shū)了器腋，哦哦溪猿，最近忙著其它的事情，去了南京好幾趟蒂培。其實(shí)文章早就寫(xiě)好了再愈，但是代碼沒(méi)有完善榜苫，所以护戳。。垂睬。媳荒。沒(méi)辦法我有強(qiáng)迫癥，沒(méi)代碼不敢網(wǎng)上傳啊驹饺，怕被拍磚钳枕。這個(gè)端午小長(zhǎng)假，難得的休閑赏壹，估計(jì)會(huì)擼兩天代碼鱼炒，多余的一天和小伙伴籃球走起。
