Iskanje dveh najbližjih točk v ravnini

Iskanje dveh najbližjih točk v ravnini

Avtor: Petra Adamič

Motivacija

  • Ko ponoči opazujemo nebo posejano z zvezdami, vidimo ravnino posejano z velikim številom zvezd. Pri tem si lahko zastavimo vprašanje, kateri dve zvezdi sta si med seboj najbližje (seveda zanima nas razdalja med zvezdami v ravnini, kot jo mi vidimo).

    (http://www2.nauk.si/files/546/zvezde.gif)
    vir: google
  • Imamo sadovnjak, kjer so drevesa naključno posejana. Med dvema drevesoma želimo napeti vrv, tako da bomo porabili čim manj vrvi. Najti moramo drevesi, ki sta si med seboj najbližji.

Pri takih vrstah problemov iščemo najbližji točki v ravnini. Drevesa oziroma zvezde predstavimo z grafom točk v ravnini in rešimo problem. Kako se takega problema lotimo, bom opisala v nadaljevanju.

Opis problema

Med množico točk v ravnini bi radi poiskali par najbližjih točk.

Matematični model: Imamo množico točk v ravnini, kjer je vsaka točka določena z in koordinato (). Razdalja med točkama je navadna razdalja (). Iščemo minimalno razdaljo med pari točk ().


(http://www2.nauk.si/files/546/primer_0.png)
točke v ravnini

Enostaven princip

Nalogo lahko enostavno rešimo tako, da izračunamo razdaljo za vsak par točk in med njimi poiščemo najmanjšo takšno razdaljo. Pri tem sta osnovni operaciji izračun razdalje med dvema točkama in primerjava razdalj. Za točk se izvede izračunov razdalj. Časovna zahtevnost je .

Deli in vladaj

Veliko bolje je nalogo rešiti s pomočjo strategije deli in vladaj. Tukaj je časovna zahtevnost . V fazi deli problem razdelimo na podprobleme istega tipa kot je glavni problem. Nato v fazi vladaj poiščemo rešitev za vsak podproblem. Na koncu združimo rešitve in tako dobimo končno rešitev glavnega problema.

Delitev

Problem razdelimo tako, da množico točk v ravnini razdelimo z navpično črto na dva dela - in . Pri tem je polovica točk levo od , v ravnini , polovica točk pa desno od , v ravnini .

Točke najprej uredimo po koordinati :

Pri tem je -koordinata navpične črte .

(http://www2.nauk.si/files/546/primer2_1.PNG)
točke ločene s črto

Rešitev problema je tako lahko:

  • ali najbližji par točk v levem delu
  • ali najbližji par točk v desnem delu
  • ali kakšen par, sestavljen iz točk čez mejo (ena točka je v levem, druga točka pa v desnem delu)

Delitev

Postopek rekurzivno ponavljamo. Delitev točk zaustavimo, ko imamo dve ali tri točke

  • - izračunamo in vrnemo razdaljo med točkama
  • - izračunamo razdaljo med vsemi tremi pari točk in vrnemo najkrajšo med njimi
  • - problem razdelimo na podprobleme
(http://www2.nauk.si/files/546/primer4.PNG)
problem razdeljen na podprobleme enakega tipa

Na sliki barve črt ponazarjajo stopnjo delitve. Najprej glavni problem ločimo na dva dela, kar prikazuje rdeča črta . Vsak podproblem zopet razdelimo na pol, kar prikazujeta zeleni črti. Zopet enak postopek ponovimo tudi na teh podproblemih. V našem primeru je treba postopek ponoviti le na treh nivojih. Pri večji količini točk je treba postopek rekurzivno izvajati dlje.

Združevanje

Najprej najdemo manjšo razdaljo med levim in desnim delom (). Pri tem moramo najprej najti vse rešitve za podprobleme.

(http://www2.nauk.si/files/546/primer5.PNG)
rešitve manjših podproblemov
(http://www2.nauk.si/files/546/primer6.PNG)
rešitve levega in desnega podproblema

Združevanje

Za pare čez mejo nas zanima, če je kakšna točka v od točke v oddaljena za manj kot . Pregledamo le tiste točke, ki so smiselni kandidati za par najbližjih točk čez mejo.


Pregled omejimo v smeri

Upoštevamo le točke, ki ležijo v pasu razdalje v levo in v desno. Točka leži v sredinskem pasu, če velja .

(http://www2.nauk.si/files/546/primer7.PNG)
točke v sredinskem pasu

Združevanje

Pregled omejimo v smeri

Za vsako točko v sredinskem pasu obstaja omejeno število možnih točk na drugi strani meje, ki so od te točke oddaljene za manj kot . Vemo, da morajo biti točke na vsaki strani meje med seboj oddaljene vsaj za . Točke uredimo po koordinati . Ko naletimo na točko, ki je od gledane točke oddaljena za več kot , vemo da nadaljnih točk ni potrebno več preverjati, saj zagotovo ležijo dlje kot je dolžina .

(http://www2.nauk.si/files/546/primer8.PNG)
krožnice okoli točk v sredinskem pasu

To vidimo na sliki, kjer vsako točko v sredinskem pasu obkroža krožnica s polmerom . Če bi kakšna točka na drugi strani meje ležala znotraj krožnice druge točke, bi to pomenilo, da smo našli točki, ki sta bližji kot do sedaj najbližji točki. Razdalja znotraj krožnice je namreč manjša kot razdalja do sedaj izmerjene minimalne razdalje.

Združevanje

Za lažje razumevanje omejitve točk v sredinskem pasu glede na koordinato , komentirajmo naslednje slike:

Vir slik: http://wiki.fmf.uni-lj.si/wiki/Par_najbli%C5%BEjih_to%C4%8Dk


(http://www2.nauk.si/files/546/Par.png)
krožnica okoli točke

Na zgornji sliki vidimo, da sta znotraj sredinskega pasu na isti strani meje dve točki znotraj krožnice. To je možno samo, če je njuna razdalja več kot . Če bi bila razdalja manj kot , bi bila to prava minimalna razdalja med najbližjima točkama. Točke na drugi strani meje pa so seveda lahko od gledane točke oddaljene za manj kot , saj tega v dosedanji rešitvi še nismo preverjali.


(http://www2.nauk.si/files/546/Par2.png)
omejimo s pravokotnikom 2d x d

Na sliki imamo primer, ko gledana točka leži ravno na mejni črti. Izkaže se, da točke, ki pridejo v poštev, lahko omejimo s pravokotnikom x znotraj sredinskega pasu. Zaradi predpostavke, da točke v sredinskem pasu preverjamo po vrsti glede na koordinato , je dovolj, da za vsako točko gledamo le točke, ki imajo večjo koordinato , saj smo za tiste točke z manjšo koordinato razdalje že preverili (seveda na enak način).

Združevanje

(http://www2.nauk.si/files/546/Par3.png)
pogledati je dovolj le 6 točk

Kot vidimo na zgornji sliki, se izkaže, da lahko preverjanje še bolj omejimo. Omejimo se lahko na preverjanje z največ nadaljnimi 5 ali 6 točkami. V kvadrat na vsaki strani meje lahko postavimo največ 4 točke, ki so med seboj oddaljene najmanj za razdaljo . To velja le, če ležijo točke v ogliščih kvadrata.Č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 pravokotnika. Torej, da bi zadostili pogoju, da so točke na isti strani meje oddaljene za več ali enako razdalji , so lahko ustrezni kandidati (če jih je res 5 ali 6) le na ogliščih pravokotnika. Če jih je manj, so seveda lahko tudi znotraj pravokotnika.


S tem načinom omejevanja možnih kandidatov si prihranimo precej dela, saj pregledamo le konstantno mnogo točk. Še zlasti se pozna razlika, če bi imeli primer, ko bi bile vse točke znotraj sredinskega pasu. Če bi v takem primeru preverjali vsako točko z vsako, ne bi s strategijo deli in vladaj ničesar izboljšali.


Primer dokaza: http://www.cs.mcgill.ca/~cs251/ClosestPair/proofbox.html

Rešitev

Tukaj je še slika rešitve našega problema. V tem primeru smo našli dve enaki minimalni razdalji, eno kot rešitev levega podproblema in drugo kot rešitev desnega podproblema.

(http://www2.nauk.si/files/546/rešitev.PNG)
rešitev našega problema

Viri

0%
0%