Definicija konveksne ogrinjače
Imamo 6 točk v ravnini. Radi bi poiskali konveksno ogrinjačo te množice točk.
Rdeče obarvane daljice predstavljajo konveksno ogrinjačo modro obarvanih točk.
|
Ogrinjači rečemo tudi ovojnica ali lupina.
Definicija konveksne ogrinjače pravi, da je to najmanjša množica, ki vsebuje X kot podmnožico, pri čemer je X množica točk.
Zakaj KONVEKSNA ogrinjača?
Konveksna množica v geometriji pomeni tako množico, da če imamo poljubni točki X in Y, ki se nahajata v tej množici, ju lahko vedno povežemo tako, da se daljica XY nahaja v tej množici.
|
Malce bolj preprosto, si lahko definicijo konveksne ogrinjače predstavljamo tako, da imamo nekaj žebljičkov, ki so zapičeni v desko. Žebljički so elementi množice X. Nato okoli žebljičkov napnemo elastiko tako, da se vsi žebljički nahajajo znotraj elastike in jo spustimo. Rečemo, da so žebljički, ki se jih elastika dotika člani konveksne ogrinjače.
|
|
Na zgornji sliki so člani koveksne ogrinjače točke A, B, C in P.
Še tretja razlaga: Konveksno ogrinjačo si lahko predstavljamo kot najkrajšo možno povezavo med točkami, pri čemer morajo biti vse točke vsebovane: kot člani konveksne ogrinjače ali pa kot notranji člani.
|
|
Najkrajša možna povezava med točkami na zgornji sliki so rdeče obarvane daljice. Torej, če točki C in P povežemo direktno, je to gotovo krajša povezava, kot če bi najprej točko C povezali z E in šele nato s P. Ko med vsemi sosednjimi točkami najdemo take povezave, se le-te povežejo v mnogokotnik, kot je razvidno iz zgornje slike.
Da so vse točke vsebovane pomeni, da se nahajajo na koveksni ogrinjači, torej na rdeči premici ali pa znotraj konveksne ogrinjače, torej znotraj mnogokotnika.
Pristopi za iskanje konveksne ogrinjače
V nadaljevanju si bomo ogledali Grahamov pregled na primeru.
PRIMER 1
Janez ima gozdiček, okoli gozdička pa prelep travnik. Da bi travnik obvaroval pred divjimi svinjami,ki se nahajajo v gozdu, se odloči, da bo okoli gozdička postavil ogrado. Pomagajmo mu s pomočjo Grahamovega pregleda. Lahko si prestavljamo, da so drevesa poljubne točke neke množice. Če okoli te množice oz. dreves postavimo konveksno ogrinjačo (ogrado) to pomeni, da se bodo vsa drevesa nahajala znotraj te ogrinjače (ograde) in divje svinje ne bodo mogle do travnika.
|
To je naš gozdiček, sestavljen iz poljubnih točk.
Najprej določimo točko P. To je tista točka med vsemi, ki ima najmanjšo koordinato y. Če je točk z najmanjšo y koordinato več, potem med temi izberemo tisto točko, ki ima tudi x koordinato najmanjšo. To bo torej najnižja in najbolj leva točka(ker ima koordinati x in y - obe hkrati - najmanjši oz. bo najbolj leva točka med najnižjimi). Ta točka zagotovo leži na konveksni ogrinjači, saj pod in levo od nje ni nobene druge točke(ker je to najnižja in najbolj leva točka bo zagotovo na koveksni ogrinjači, saj drugače ne bo v konveksni množici). Pri izbiranju točke P pa imamo nekaj svobode, saj lahko izberemo za P tudi kakšno drugo točko, npr. najnižjo in najbolj desno točko. Če bi izbrali tako točko, bi imela ta točka najmanjšo y koordinato in hkrati največjo x koordinato. Zagotovo je tudi ta točka član konveksne ogrinjače, ker se drugače ne bi nahajala v konveksni množici.
Primer, ko imamo več najnižjih točk
Na prvi sliki vidimo, da imamo kar tri najnižje točke. Med temi najnižjimi točkami za P lahko izberemo katero koli, saj bodo vse nastopale kot člani konveksne ogrinjače. Priporočljivo je, da izberemo F ali H, saj sta to najbolj leva oz. najbolj desna med najnižjimi in bosta zagotovo člana konveksne ogrinjače.
|
Na drugi sliki smo eno izmed treh najnižjih prestavili višje. Za P lahko izberemo ali točko H (najbolj leva med najnižjimi) ali točko F (najbolj desna med najnižjimi).
|
Nadaljujemo s PRIMEROM 1
|
Potegnemo premice skozi vse točke in točko P. Nato točke povežemo, da dobimo mnogokotnik. Premice potegnemo zato, da vemo v kakšnem vrstnem redu moramo točke povezati - torej iz leve proti desni z začetkom v točki P. Premice nam določajo kote in točke povezujemo tako, da P povežemo najprej s tisto z najmanjšim kotom.
|
Sedaj se sprehodimo po mnogokotniku. Začnemo v točki P. Določimo točke p, q in r, ki so vedno tri zaporedne točke. Če te točke določajo levi obrat oz. zasuk zbrišemo točko q iz mnogokotnika in povežemo točki p in r.
Določimo točke p, q in r. Ker te točke določajo desni zasuk, s sprehodom nadaljujemo. Točka, ki je sedaj q postane p, točka r postane q, nova točka postane r.
Zasuk pomeni prehod iz začetne v končno lego. Lahko si predstavljamo, da je v našem primeru začetna lega točka p, končna pa točka r. Ker pri prehodu iz začetne točke naredimo desni ovinek, da pridemo v končno točko, to imenujemo desni zasuk oz. obrat.
Levi zasuk pomeni, da iz začetne lege v končno lego pridemo s pomočjo levega obrata.
|
Točke p, q in r določajo levi zasuk, zato točko q odstranimo iz mnogokotnika. Točka p postane predhodna točka, točka q postane točka p, točka r pa ostane ista.
|
Točko q smo odstranili iz mnogokotnika. Določimo nove točke p, q in r. Te določajo desni zasuk, zato s sprehodom nadaljujemo.
|
Točke p, q in r določajo desni zasuk, zato nadaljujemo s sprehodom.
|
Točke p, q in r določajo levi zasuk, zato točko q odstranimo iz mnogokotnika.
|
Točko q smo odstranili iz mnogokotnika. Tako nadaljujemo Grahamov prehod (pri levem zasuku točko q odstranimo). S postopkom končamo, ko pridemo nazaj v P (torej, ko točka P postane r). Pa si poglejmo končni rezultat na naslednji sliki.
|
To je končni rezultat. Janezu smo pomagali ograditi gozdiček. Drevesa, ki se dotikajo konveksne ogrinjače, so člani konveksne ogrinjače. Ostala dervesa pa so notranji člani.
PRIMER 2
Pa si oglejmo še en celoten postopek na nekoliko manjši množici točk, kjer bomo za pivot P izbrali najnižjo in najbolj desno točko. Sprehajali se bomo v nasprotni smeri urinega kazalca, torej bomo brisali tiste točke, ki bodo imele desni zasuk.
|
Imamo množico X, sestavljeno iz šestih točk. Za P smo izbrali točko z najmanjšo koordinato y in hkrati največjo koordinato x.
|
Potegnemo premice skozi P in ostale točke. Točke povežemo v mnogokotnik.
|
Začnemo pri točki P in označimo točke p, q in r. Te določajo levi zasuk, zato s sprehodom nadaljujemo, saj tokrat odstranjujemo tiste točke, ki določajo desni zasuk.
|
Točke smo prestavili za eno mesto naprej. Tudi te določajo levi zasuk, zato nadaljujemo.
|
|
Točke p, q in r določajo desni zasuk, zato točko q odstranimo.
|
Točka p je postala prejšnja točka, točka q pa je postala točka, ki je bila prej p. Točka r se ni spremenila. Določajo levi zasuk, zato s sprehodom nadaljujemo.
|
Imamo levi zasuk, zato nadaljujemo.
|
Zopet imamo levi zasuk. Ker smo prišli do pivota P, končamo.
PRIMER 3
Prikaz Grahamovega pregleda na filmu.
Časovna zahtevnost
Časovna zahtevnost je torej : T(n) = O(n log(n))
VPRAŠANJE 1
Napačno!
Ok
VPRAŠANJE 2
Bravo! Naprej
Napačno! Ok
VPRAŠANJE 3
Bravo! Naprej
Napačno! Ok
Literatura
