Par najbližjih točk

Iz MaFiRaWiki

Vsebina

Definicija problema

 Slika 1: Par najbližjih točk med točkami v ravnini
Slika 1: Par najbližjih točk med točkami v ravnini

V dani množici točk v ravnini iščemo par najbližjih točk.


Razčlenitev problema:

Imamo množico n točk v ravnini P.
|P| = n
P = {t1, t2, t3, …, tn}
Vsaka točka je določena z x- in y-koordinato.
tj = (xj, yj)
Razdalja med dvema točkama ti in tj je običajna evklidska razdalja.
d(ti, tj) = √(xi - xj)2 + (yi - yj)2


Iščemo taka i in j, da je razdalja d(ti, tj) najmanjša.




Enostavni pristop

Neposredni pristop je, da izračunamo medsebojno razdaljo za vsak par točk in poiščemo najmanjšo takšno razdaljo.

Zapis enostavnega algoritma za par najbližjih točk v psevdokodi

Algoritem najblizjiParTock_enostavni(P)
 
 Vhodni podatki: Vhodni podatki: P = {t1, t2, t3, …, tn} 
 
 Rezultat: d (razdalja med najbližjima točkama v množici)

 d = razdalja(t1, t2)        //izračunamo razdaljo med prvima dvema točkama

   for i od 1 do n – 1        //po vrsti gremo od prve do predzadnje točke
     for j od i + 1 do n       //pri vsaki točki pogledamo vse točke od te točke do konca
       če razdalja(ti, tj) < d    //če je razdalja med točkama manjša od do sedaj najmanjše, 
         posodobi d                //si jo zapomnimo
 
 Vrni d

Da poenostavimo zapis smo problem iskanja najbližjega para točk omejili na iskanje razdalje med najbližjima točkama. V natančnem algoritmu je potrebno poskrbeti tudi za to, da se zabeležita in vrneta tudi točki, kjer to najmanjšo razdaljo dosežemo.

Analiza algoritma

Za analizo algoritma moramo določiti osnovno operacijo in ugotoviti, kako pogosto se ta operacija izvede.

Osnovni operaciji pri tem algoritmu sta izračun razdalje med dvema točkama in primerjava razdalj.

Če imamo n točk, se izvede (n – 1) + (n – 2) + (n – 3) + … + 2 + 1 = n(n – 1)/2 izračunov razdalj in za eno manj primerjav.

Takšen algoritem ima torej kvadratno časovno zahtevnost - O(n2).


Uporaba strategije deli in vladaj

 Slika 2: Par najbližjih točk - deli in vladaj
Slika 2: Par najbližjih točk - deli in vladaj

Z uporabo strategije deli in vladaj lahko problem iskanja para najbližjih točk rešimo učinkoviteje, s časovno zahtevnostjo O(n log n).


Osnovni koraki:

  • DELI: Problem razdelimo na podprobleme.
Množico točk s pokončno mejo razdelimo na dva dela (dve ravnini), tako da je v vsakem delu približno polovica točk.
(Če je število točk deljivo z 2, potem je na vsaki strani točno polovica točk, sicer je na eni strani ena točka več. V nadaljnjem besedilu bomo zaradi poenostavitve rekli kar polovica.)


  • VLADAJ: Poiščemo rešitev za vsak podproblem.
V vsaki ravnini rekurzivno poiščemo par najbližjih točk.


  • Rešitve združimo.
Pri združevanju primerjamo rešitvi iz obeh delov. Ugotovimo, kateri par najbližjih točk ima krajšo medsebojno razdaljo.


 Slika 3: Par najbližjih točk - združevanje rešitev
Slika 3: Par najbližjih točk - deli združevanje rešitev
V primeru na sliki 2 imata krajšo medsebojno razdaljo najbližji točki iz desne ravnine (dD).
Pa je to že skupna rešitev za celotno množico točk?
Upoštevati moramo možnost (kot velja v primeru na sliki 3), da ležita še bližje skupaj kakšni točki čez mejo, tako da je ena točka iz enega dela in druga iz drugega dela!


Za rekurzivni algoritem moramo določiti zaustavitveni pogoj. Z delitvijo nadaljujemo, dokler problem ni majhen (enostavno obvladljiv).

Delitev točk zaustavimo, ko imamo dve ali tri točke. Če imamo dve točki, potem samo izračunamo razdaljo med njima. Če imamo tri točke, pa z neposredno primerjavo ugotovimo, kateri par ima najmanjšo medsebojno razdaljo.
Če n > 3 : problem razdelimo na podprobleme.
Če n = 2 : izračunamo in vrnemo razdaljo med točkama (d).
Če n = 3 : izračunamo razdaljo med vsemi tremi pari točk in vrnemo najkrajšo med njimi (d).



Oglejmo si posamezne korake podrobneje in opravimo časovno analizo takšnega algoritma.


Faza delitve

 Slika 4: Faza delitve
Slika 4: Faza delitve

V fazi delitve ne želimo zgolj razdeliti množice točk v dve številčno enaki podmnožici, želimo tudi, da v posamezni podmnožici točke ležijo skupaj. Upoštevamo torej lego točk. Množico točk v ravnini P s pokončno črto m razdelimo v dve podmnožici PL in PD, tako da je polovica točk levo od m v ravnini PL in druga polovica točk desno od m v ravnini PD.

V ta namen je smiselno, da so točke urejene po x-koordinati. Tako lahko za levi del vzamemo prvo polovico točk v seznamu, za desni del pa ostale (slika 4).

PL = {t1, t2, …, tn/2}
PD = {tn/2 + 1, …, tn}


Za x-koordinato pokončne črte m izračunamo sredino med x-koordinatama srednjih dveh točk (točke na mestu n/2 in točko na mestu n/2 + 1)

m = (xn/2 + xn/2+1)/ 2


Urejanje je časovne zahtevnosti O(n log n). Smiselno je, da se opravi na začetku (pred rekurzivno metodo), tako da potem v posameznih fazah rekurzije ni več potrebno. Če se ohranja ureditev po x-koordinati, se lahko delitev vsake podmnožice na dve nadaljnji podmnožici izvede v konstantnem času.


Faza združevanja

 Slika 5: Sredinski pas
Slika 5: Sredinski pas

Iskanje najbližjega para točk v fazi združevanja zahetva nekoliko več razmisleka.

Upoštevati moramo, da je najbližji par točk v celotni ravnini bodisi najbližji par iz levega dela, bodisi najbližji par iz desnega dela, bodisi kakšen par sestavljen iz dveh točk čez mejo, tako da je ena v levem delu in druga v desnem delu.


  • Najprej primerjamo najbližji par iz levega dela in najbližji par iz desnega dela ter vzamemo tistega, ki ima krajšo medsebojno razdaljo. To opravimo v konstantnem času.
d = min(dL, dD)


  • Potem pa moramo pregledati še pare točk čez mejo. Ugotoviti želimo, če je kakšna točka v PL za manj kot razdaljo d oddaljena od točke v PD.
Ali moramo v ta namen preveriti razdalje od vseh točk v PL do vseh točk v PD?
Če bi bilo temu tako, potem s strategijo deli in vladaj ne bi nič pridobili, saj bi bila časovna zahtevnost še vedno kvadratna. Namesto da bi enkrat pregledali razdalje od vseh točk do vseh ostalih točk, bi sedaj na vsaki stopnji rekurzije pregledovali razdalje od polovice točk do druge polovice točk.
Katera dejstva lahko upoštevamo pri oblikovanju časovno manj zahtevnega algoritma v tem delu?
Smiselno je, da pregledamo samo tiste točke, ki so možni kandidati za par najbližjih točk s kakšno točko iz sosednje strani meje.


 Slika 6: Vse točke v sredinskem pasu
Slika 6: Vse točke v sredinskem pasu
1. Najprej poglejmo, kako lahko pregled omejimo v x-smeri.
Prav gotovo ni potrebno, da preverjamo točke, ki so od meje oddaljene več od razdalje d. Upoštevamo torej samo točke, ki ležijo v pasu v razdalji za d levo in desno od meje (slika 5).
Če je razdalja med parom točk, ki ležita čez mejo, manjša od d, potem ti dve točki ležita v sredinskem pasu S.
Točke, ki so od meje bolj oddaljene, lahko takoj izločimo. To opravimo v linearnem času, tako da pregledamo x-koordinate vseh točk.
Točka ta je v sredinskem pasu če:
xa >= m – d && xa <= m + d


S tem lahko veliko pridobimo. V obmejnem pasu lahko leži samo kakšna posamezna točka (kot v primeru na sliki 5) ali celo nobena. Vendar pa se po drugi strani lahko zgodi, da se v tem pasu znajde veliko točk, v skrajnem primeru celo vse točke (slika 6).
Če bi morali pregledati vsak par točk v sredinskem pasu, smo v najslabšem primeru ponovno pri kvadratni časovni zahtevnosti.




 Slika 7
Slika 7
2. Pregled omejimo tudi v y-smeri
Na srečo se izkaže, da nam ni potrebno pregledovati vseh parov točk, ki se znajdejo v sredinskem pasu. Za katerokoli točko v sredinskem pasu obstaja namreč zgolj omejeno število možnih točk na drugi strani meje, ki so od te točke oddaljene za manj kot d (slika 7).
Vemo namreč, da morajo biti točke na vsaki strani meje med seboj oddaljene vsaj za razdaljo d. Sicer bi bil naš podatek o d napačen. Če bi kakšni dve točki na eni strani meje ležali bolj skupaj, bi že prejšnji korak moral vrniti to razdaljo kot najmanjšo in ti dve točki kot par najbližjih točk.
To informacijo želimo izkoristiti za omejitev števila točk, s katerimi primerjamo vsako točko v sredinskem pasu.
Na sliki 7 sta dve točki, ki ležita na drugi strani meje v območju kroga s polmerom d od točke T. Koliko pa je lahko največ takšnih točk?
Da bomo lahko oblikovali algoritem, moramo vprašanje zastaviti nekoliko drugače.
Točke uredimo po y-koordinati (v primeru na sliki 7 torej A, T, C, B, D). Na katerem mestu od točke t se v tako urejenem seznamu še lahko nahaja neka točka, ki bi lahko ležala v razdalji največ d od točke T?
V primeru na sliki 7 točka B na primer leži za dve mesti naprej od točke T. Točka D, ki leži na tretjem mestu, je od točke T že bolj oddaljena.
 Slika 8
Slika 8


Poglejmo skrajni primer (slika 8). Točka T leži točno na meji in je razporejena v desno ravnino. V razdalji d navpično navzgor leži točka B, ki je razporejena v levo ravnino. Točke, ki so po y-koordinati oddaljene več od razdalje d, zagotovo niso več kandidati za par najbližjih točk in zato jih ni potrebno pregledovati. Točka B je torej skrajna, ki jo še moramo upoštevati pri pregledu razdalj od točke T. Z omejitvijo sredinskega pasu v y-smeri smo dobili območje pravokotnika širine 2d in višine d.
Ugotoviti moramo, koliko točk bi lahko največ ležalo na tako omejenem območju in bi na ta način v seznamu točk urejenih po y-koordinati lahko zasedle mesto pred točko B.









 Slika 9
Slika 9
V kvadrat na vsaki strani meje lahko postavimo največ 4 točke, ki so med seboj oddaljene najmanj za razdaljo d. To velja, če ležijo točke v ogliščih kvadrata. Razdalja med oglišči je namreč ravno d. Nobene dodatne točke ne moremo postaviti v to območje ob upoštevanju zahteve, da morajo biti točke med seboj oddaljene vsaj za d.
Če bi se tudi na drugi strani meje znašlo na kupu največ možnih točk, bi imeli skupno 6 točk v območju označenega pravokotnika (slika 9).
Točke v primeru na sliki 9 bi bile pri urejanju po y-koordinati lahko razporejene na sledeč način: T, A, D, C, E, B (po tri imajo enako y-vrednost). Točka B bi v tem primeru ležala na 5. mestu od točke T. Vsaka morebitna nadaljnja točka v seznamu je od točke T zagotovo oddaljena več, kot je razdalja d.


Naj povzamemo: Točke v sredinskem pasu uredimo po y-koordinati. Za vsako točko preverimo razdaljo zgolj do petih nadaljnjih točk v seznamu. S tem zagotovo pregledamo vse možne kandidate za par najbližjih točk.
Koliko smo pridobili?
Namesto, da za vsako točko v sredinskem pasu pregledamo razdaljo do vseh ostalih točk v tem pasu (kar bi pomenilo kvadratno časovno zahtevnost), zadostuje, da za vsako točko pregledamo zgolj razdaljo do petih (konstantnega števila) nadaljnjih točk (to pa je linearne časovne zahtevnosti).
V ta namen smo sicer dodali še delo urejanja točk v y-smeri, kar je časovne zahtevnosti O(n log n).


Povzetek in analiza algoritma deli in vladaj za par najbližjih točk

Da poenostavimo zapis smo problem iskanja najbližjega para točk omejili na iskanje razdalje med najbližjima točkama. V natančnem algoritmu je potrebno poskrbeti tudi za to, da se zabeležita in vrneta tudi točki, kjer to najmanjšo razdaljo dosežemo.


Predkorak (pred rekurzivno metodo): Uredi točke po x-koordinati. – časovna zahtevnost: O(n log n)

Delitev na dva podproblema, rekurzivno iskanje rešitve za vsak podproblem in sestavljanje skupne rešitve se nato dogaja na vsakem nivoju rekurzije. Ker na vsakem koraku pri rekurzivnih klicih množico točk razdelimo približno na polovico, bo skupno število rekurzivnih stopenj log n.

Faze na posameznem rekurzivnem nivoju:

  1. Razdeli množico na dva enako velika dela z navpično črto m.
  2. V vsakem delu rekurzivno izračunaj najmanjšo razdaljo med pari točk.
  3. Naj bo d manjša od obeh razdalj iz levega in desnega dela. – časovna zahtevnost: O(1)
  4. Izloči točke, ki so od meje m oddaljene več od razdalje d. – časovna zahtevnost: O(n)
  5. Uredi preostanek točk po y-koordinati. – časovna zahtevnost: O(n log n)
  6. Preglej vse točke po vrsti v y-smeri in za vsako izračunaj razdaljo do petih (konstantnega števila) sledečih točk. Če je kakšna od teh razdalj manjša od d, posodobi d. – časovna zahtevnost: O(n)

V fazi združevanja prevladuje časovna zahtevnost podfaze urejanja O(n log n). Faza združevanja se ponovi na vsaki stopnji rekurzije algoritma deli in vladaj (logn-krat). Torej celotni algoritem zahteva O(log n * n log n) = O(n log2 n), kar je bolje kot kvadratna časovna zahtevnost O(n2).


Ali algoritem lahko še izboljšamo?

Iz algoritma za urejanje z zlivanjem vemo, da dva urejena seznama lahko združimo v linearnem času (z enkratnim pregledom vseh elementov v seznamu). Ta pristop lahko uporabimo za bolj učinkovito urejanje v našem algoritmu. V zaustavitveni fazi, ko neposredno rešimo problem, ki je že dovolj majhen (2 ali 3 točke), bomo poskrbeli še za ureditev točk po y-koordinati in vrnili tako urejen seznam. Na vsaki višji stopnji rekurzije bomo pri sestavjanju rešitev iz podproblemov morali samo še združiti dva urejena seznama (v linearnem času).

Algoritem torej lahko izboljšamo, če zagotovimo, da se urejanje po y-koordinati ne dogaja na vsaki stopnji znova. Vsaka faza združevanja mora, poleg najkrajše razdalje in para najbližjih točk, vrniti še točke urejene po y-koordinati. Združevanje dveh urejenih množic pa zahteva zgolj linearni čas O(n), namesto O(n log n) v primeru vsakokratnega urejanja.

Izboljšan algoritem:

Predkorak (pred rekurzivno metodo): Uredi točke po x-koordinati.

  1. Razdeli množico na dva enako velika dela z navpično črto m.
  2. V vsakem delu rekurzivno izračunaj najmanjšo razdaljo med pari točk. Poleg tega vrni točke urejene po y-koordinati.
  3. Naj bo d manjša od obeh razdalj iz levega in desnega dela. – časovna zahtevnost: O(1)
  4. Združi dva urejena seznama točk. – časovna zahtevnost: O(n) (Združevanje moramo opraviti preden točke izven sredinskega pasu izločimo, saj moramo na višji nivo rekurzije posredovati celoten seznam točk (in ne samo sredinske) iz posamezne polovice)
  5. Izloči točke, ki so od meje m oddaljene več kot za razdaljo d. – časovna zahtevnost: O(n)
  6. Preglej vse točke po vrsti v y-smeri in za vsako izračunaj razdaljo do 5 sledečih točk. Če je kakšna od teh razdalj manjša od d, posodobi d. – časovna zahtevnost: O(n)

Sedaj v fazi združevanja dominirajo tri podfaze s časovno zahtevnostjo O(n).

Ker je vseh rekurzivnih nivojev log n, smo na ta način dosegli časovno zahtevnost O(n log n).


Zapis algoritma v psevdokodi:

 Algoritem najblizjiParTock_DiV(P)
  
   Vhodni podatki: P = {t1, t2, t3, …, tn} (množica n točk v ravnini P)
  
   Rezultat: d (razdalja med najbližjima točkama v množici)
 
 
   uredi P glede na x-koordinate  //pokličemo metodo za ureditev točk v P
   d, Y = najdiNajblizjiParTock(P)  //pokličemo rekurzivno metodo za iskanje para najbližjih točk med urejenimi točkami
 
   vrni d


 Algoritem najdiNajblizjiParTock(P)
 
   Vhodni podatki: P = {t1, t2, t3, …, tn} (množica n točk v ravnini P; točke so urejene po x-koordinati)
  
   Rezultat: d (razdalja med najbližjima točkama v množici)
             in Y, seznam točk, urejenih po y-koordinati
 
 
   če n <= 3       //če so v ravnini največ tri točke, je problem dovolj majhen in d izračunamo neposredno
 
       če n == 2    //če sta samo dve točki
           d = razdalja(t1, t2)    //izračunamo razdaljo med njima
 
       sicer         //če pa so tri točke, izračunamo razdalje pri vseh treh parih
           d = min(razdalja(t1, t2), min(razdalja(t2, t3), razdalja(t1, t3))    //poiščemo minimalno razdaljo med vsemi tremi
 
       uredi točke po y-koordinati v seznam Y
 
 
   sicer    //če je v ravnini več točk, problem razdelimo
 
       razdeli P na dva po številu točk enaka dela PL in PD
 
       //V vsakem delu rekurzivno poiščemo par najbližih točk
       dL, YL = najdiNajblizjiParTock(PL)
       dD, YD = najdiNajblizjiParTock(PD)
 
       Y = zlij(YL in YD)    //združimo oba urejena seznama YL in YD v en urejen seznam Y
 
       d = min(dL, dD)    //primerjamo rešitvi iz obeh delov in vzamemo manjšo
 
       Naj S predstavlja točke v Y, ki so v sredinskem pasu.
 
       for i od 1 do |S| – 1    //pregledamo vse točke v sredinskem pasu od prve do predzadnje
 
           //od vsake točke pregledujemo nadaljnje točke do konca seznama oz. dokler jih ne pregledamo 5
           j = 1
           dokler i + j <= |S| in j <= 5  
 
               če razdalja(si, si + j) < d  //če je razdalja manjša od do sedaj najmanjše, si jo zapomnimo
 
                  posodobi d
              j = j + 1
 
   Vrni d in Y

Viri

Osebna orodja