Grahamov pregled

Iz MaFiRaWiki

Vsebina

Definicija konveksne ovojnice

Konveksna ogrinjača ali ~ lupina oz. ovojnica množice točk X v realnem vektorskem prostoru V je v matematiki najmanjša konveksna množica, ki vsebuje X kot podmnožico. (Pri tem je lahko X unija poljubnih množic objektov, ki jih sestavljajo točke.)

S problemom iskanja konveksne ogrinjače se pogosto ukvarja tudi računalniška geometrija. Problem si lahko predstavljamo zelo preprosto. Imejmo nekaj žebljičkov zapičenih v desko; to so točke iz X. Okoli njih razpremo elastiko tako, da so vsi žebljički v njej nato pa jo spustimo, da se napne okoli žebljičkov. Žebljički, ki se jih elastika dotika, so člani konveksne ogrinjače. Bolj strokovno povedano je konveksna ogrinjača najkrajša možna povezava točk tako, da so vse točke na notranji strani ali člani konveksne ogrinjače. Za reševanje konveksne lupine v računalništvu poznamo več možnih algoritmov:

  • Grobi pristop
  • Jarvisov obhod
  • Grahamov pregled
  • Inkrementalna metoda
  • Algoritem tvorbe konveksne lupine s strategijo »deli in vladaj«
  • Aproksimacijski algoritem
  • Jarvisov obhod
  • Konveksna ovojnica

Algoritem: Grahamov pregled

1. Imamo P = (p1,p2,...,pn)
2. Poiščemo točko p*
3. Uredimo točke P\{p*} glede na kot do p*
4. S prazen sklad; damo p* in p1 na sklad
5. i=2
6. while i<n
7.    q=vrh(S); p element pod vrhom S
8.    if p,q,pi obrat na desno
9.       damo pi na sklad S
10.      i=i+1 
11.    else
12.       brišemo element q
13.    end if
14. end
15. return sklad S;

Prikaz na primeru

  • Poiščemo točko z najmanjšo koordinato y . Če je takih točk več, potem med temi izberemo točko, ki ima najmanjšo koordinato x . Točko označimo z p*
Slika:Graham_0.png
  • Uredimo glede na kot do p* in jih povežemo v smeri urnega kazalca, da dobimo mnogokotnik M,
Slika:Graham_1.png   Slika:Graham_2.png
  • Sprehodimo se po M in ko imamo levi zasuk brišemo srednjo točko q iz M in tako nadaljujemo po vseh točkah iz P.

1: Določimo točke p, q in r

Slika:Graham_3.png
   

2: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom (p=q, q=r, r=nova točka iz M)

Slika:Graham_4.png

3: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_5.png
   

4:Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_6.png

5:Točke p, q in r določajo levi zasuk

Slika:Graham_7.png
   

6: Točko q odstranimo iz množice M (p=predhodna točka v M, q=p, r=r)

Slika:Graham_8.png

7: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_9.png
   

8: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_10.png

9: Točke p, q in r določajo levi zasuk

Slika:Graham_11.png
   

10: Točko q odstranimo iz množice M

Slika:Graham_12.png

11: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_13.png
   

12: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_14.png

13: Točke p, q in r določajo levi zasuk

Slika:Graham_15.png
   

14: Točko q odstranimo iz množice M

Slika:Graham_16.png

15: Točke p, q in r določajo levi zasuk

Slika:Graham_17.png
   

16: Točko q odstranimo iz množice M

Slika:Graham_18.png

17: Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom

Slika:Graham_19.png
  • Končamo, ko pridemo nazaj v p*.
Slika:Graham_20.png

Časovna zahtevnost

Časovna zahtevnost algoritma je O(n log(n)) in sicer:

  • O(n) iskanje p*
  • O(n log(n)) urejanje po kotih
  • O(n) sprehod, na vsakem korak gremo v novo točko ali pa brišemo točko iz M

T(n) = O(n) + O(n log(n)) + O(n) = O(n log(n))

Literatura

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to algorithms
  • Graham Scan:

Glej tudi

Osebna orodja