S pojmom konveksnosti se srečamo na mnogih področjih, npr. konveksna funkcija, konveksna leča, konveksen mnogokotnik, konveksna množica, ...

Konveksna množica je v geometriji množica točk, za katero velja, da pri poljubni izbiri dveh točk iz te množice daljica, ki povezuje ti dve točki v celoti leži znotraj te množice.

Primer konveksne množice.

Množica, ki ni konveksna je konkavna.

Primer konkavne množice.

Konveksna ovojnica (tudi konveksna ogrinjača, konveksna lupina) množice točk M v realnem vektorskem prostoru V je najmanjša konveksna množica, ki vsebuje M kot podmnožico.

Najlažje si konveksno ovojnico predstavljamo na naslednjem primeru.

PRIMER: Imamo nekaj risalnih žebljičkov, ki jih poljubno zabijemo v desko. Ti žebljički predstavljajo množico M. Vzamemo elastiko in jo razpnemo okrog žebljičkov tako, da se vsi nahajajo znotraj elastike. Ko elastiko spustimo, se ta napne okrog njih. Žebljički se elastike dotikajo ali pa se nahajajo znotraj nje. Tiste žebljičke, ki se jih elastika dotika, imenujemo elementi konveksne ovojnice.

Točke na spodnji sliki si lahko predstavljamo kot žebljičke, zeleno obarvane povezave med točkami pa kot konveksno ovojnico dane množice točk.

Primer konveksne ovojnice na dani množici točk.

Še ena definicija konveksne ovojnice pravi, da je to najkrajša možna povezava točk tako, da so vse točke ali elementi konveksne ovojnice ali pa se nahajajo znotraj nje.

Najkrajša možna povezava med točkami na zgornji sliki so rjavo obravane daljice. Npr. če točki I in H na sliki povežemo direktno, je to zagotovo krajša pot, kot pa če bi točko I najprej povezali s točko J in šele nato posredno s točko H. Ko med vsemi sosednjimi točkami najdemo najkrajše povezave, dobimo mnogokotnik, kot ga vidimo na zgornji sliki. Ta mnogokotnik predstavlja konveksno ovojnico za dani primer množice točk.

V primeru, da so vse točke iz množice razporejene po krožnici, so vse točke elementi konveksne ovojnice.

Konveksna ovojnica točk, ki so razporejene po krožnici.

Najmanj dve točki pa sta potrebni za tvorbo konveksne ovojnice. Daljica, ki ti dve točki povezuje, predstavlja konveksno ovojnico teh dveh točk.

Konveksna ovojnica dveh točk je kar daljica, ki ju povezuje.

Z iskanjem konveksne ovojnice se dostikrat srečamo tudi v realnem življenju, vendar se takrat ne zavedamo, da dejansko problem rešimo s pomočjo iskanja konveksne ovojnice.

Primeri:

• prirejanje vrtne zabave,
• ograjevanje grmičevja na travniku,
• ograjevanje ovac,
• itd.

Najkrajša ograja, s katero ogradimo dane ovce, predstavlja kar konveksno ovojnico množice ovac.

Za iskanje konveksne ovojnice na množici točk obstaja kar nekaj algoritmov. Konveksno ovojnico lahko poiščemo:

• z grobim pristopom,
• z Jarvisovim obhodom (tudi algoritem zavijanja daril),
• z inkrementalno metodo,
• z algoritmom, ki deluje s strategijo deli in vladaj (angl. Quick hull),
• z aproksimacijskim algoritmom,
• z Grahamovim pregledom,
• itd.

• Grahamov algoritem je eden izmed prej omenjenih algoritmov za iskanje konveksne ovojnice na množici točk v ravnini.
• Leta 1972 ga je objavil Ronald L. Graham.
• Zgodovinsko gledano je to prvi algoritem za iskanje konveksne ovojnice s časovno zahtevnostjo v najslabšem primeru O(n log(n)).
• Pogosto se Grahamov algoritem navaja za prvi geometrijski računalniški program.

• Algoritem ima nekaj prednosti in nekaj slabosti.

  • Prednosti:

    • Časovna zahtevnost algoritma v najslabšem primeru.
    • Algoritem je učinkovit, ker teče hitro ne glede na število točk, ki ležijo na konveksni ovojnici.

  • Slabosti:

    • Algoritem ne moremo posplošiti v 3D in višje dimenzije.
• Pregled točk lahko izvajamo v smeri urinega kazalca ali pa v obratni smeri. Odvisno od izbire smeri se algoritem nekoliko razlikuje.

Algoritem bom predstavil na konkretnem primeru točk. Pregled točk bomo izvajali v smeri urinega kazalca.

1. KORAK: Izbira pivotne točke

Na množici točk (označimo jo npr. z M) poiščemo točko z najmanjšo y koordinato. Lahko se zgodi, da imamo več točk z isto (najmanjšo) y koordinato. V tem primeru izberemo tisto točko, ki ima hkrati tudi najmanjšo x koordinato. Izbrano točko imenujemo pivotna točka in jo označimo s P.

Izbira pivotne točke P na danem primeru množice točk.

Zakaj v primeru več točk z isto (najmanjšo) y koordinato izberemo tako, ki ima tudi najmanjšo x koordinato? Taka točka zagotovo leži na konveksni ovojnici, saj pod njo in levo od nje ni nobene druge točke. Levo seveda so lahko točke, vendar imajo vse večjo y koordinato.

Za začetno (pivotno) točko P lahko seveda izberemo tudi kako drugo točko, npr. točko, ki ima:

• najmanjšo y in največjo x koordinato,
• največjo y in najmanjšo x koordinato,
• največjo y in največjo x koordinato.

2. KORAK: Povezovanje točk v mnogokotnik

Skozi izbrano pivotno točko P in preostale točke narišemo premice, ki nam pomagajo pri določevanju začetnega mnogokotnika. Dobimo premice z naraščajočim in padajočim naklonom.

Skozi pivotno točko in preostale točke narišemo premice.

Točke začnemo povezovati v mnogokotnik pri točki P in nadaljujemo s točko, ki leži na prvi premici v smeri urinega kazalca (premici z najmanjšim naklonom med padajočimi premicami). Nadaljujemo s povezovanjem točk v smeri pregleda, dokler ne sklenemo mnogokotnika (dokler se ne vrnemo nazaj v točko, s katero smo začeli).

Začetni mnogokotnik nad katerim bomo začeli izvajati Grahamov pregled.

3. KORAK: Grahamov pregled

Najprej si izberemo tri zaporedne točke. Naša prva točka je kar pivotna točka P, drugo in tretjo pa predstavljata naslednji dve točki v mnogokotniku v smeri urinega kazalca. Poimenujemo ju Q in R.

Izbira začetne trojice točk P, Q in R.

Za izbrano trojico točk P, Q in R preverimo ali določajo levi ali desni obrat. Kaj pa sploh sta levi in desni obrat?

LEVI OBRAT: Če pri prehodu iz točke P v R naredimo v točki Q levi zavoj, to imenujemo levi obrat.

DESNI OBRAT: Če pri prehodu iz točke P v R naredimo v točki Q desni zavoj, to imenujemo desni obrat.

Odvisno od tega ali izvajamo pregled v smeri urinega kazalca ali v obratni smeri urinega kazalca se Grahamov algoritem nekoliko razlikuje.

• Pregled v smeri urinega kazalca:

  • V primeru desnega obrata nadaljujemo s pregledom - določimo nove točke P, Q in R.

    • Q postane novi P, R postane novi Q, za novi R pa vzamemo naslednjo točko v mnogokotniku v smeri pregleda.

  • V primeru levega obrata izpustimo točko Q iz mnogokotnika in povežemo točki P in R med seboj, ter določimo nov mnogokotnik.

    • R ostane R, P postane novi Q, za novi P pa vzamemo točko, ki v novem mnogokotniku leži levo od trenutno izbrane točke Q.

• Pregled v obratni smeri urinega kazalca:

  • V primeru desnega obrata izpustimo točko Q iz mnogokotnika in povežemo točki P in R med seboj, ter določimo nov mnogokotnik.
  • V primeru levega obrata nadaljujemo s pregledom - določimo nove točke P, Q in R.

Če se vrnemo nazaj na primer.

Vidimo, da smo v zgornjem primeru naredili desni obrat, zato točka Q postane novi P, točka R postane novi Q, za novi R pa vzamemo naslednjo točko v mnogokotniku (v smeri pregleda).

S postopkom nadaljujemo in za izbrane trojice točk P, Q in R preverjamo ali gre za levi ali za desni obrat.

Vidimo, da smo za izbrane točke P, Q in R na zgornji sliki naredili desni obrat, zato nadaljujemo s pregledom - izberemo nove točke.

Na zgornji sliki pa smo za trenutno izbrane točke P, Q in R v točki Q naredili levi obrat. Zato ...

... točki P in R povežemo in dobimo nov mnogokotnik.

Izberemo nove točke P, Q in R ter nadaljujemo s pregledom.

S pregledom nadaljujemo vse dokler začetne (pivotne) točke ne izberemo za točko R.

Mnogokotnik, ki ga dobimo na koncu, predstavlja iskano konveksno ovojnico začetne množice točk.

Časovna zahtevnost v najslabšem primeru je O(n log(n)).

• O(n) - za iskanje začetne točke P
• O(n log(n)) - za urejanje točk po naklonih premic
• O(n) - za sprehod po vseh točkah začetnega mnogokotnika (preverjanje ali gre v točki za levi ali za desni obrat)

V najboljšem primeru, ko imamo vse točke že urejene po naklonih premic, pa je časovna zahtevnost O(n).

Na prvi pogleda izgleda, da je časovna zahtevnost za sprehod O(), ker gre algoritem preveriti ali se je ob odstranitvi točke mogoče pojavil še kakšen levi obrat. Vendar gre pri sprehodu res za O(n), ker se vsaka točka šteje največkrat dvakrat. Vsaka točka se lahko namreč pojavi samo enkrat kot točka v levem obratu (v tem primeru točko izpustimo) in enkrat kot točka v desnem obratu.

Iskanje konveksne ovojnice je eden temeljnih algoritmov v računalniški geometriji. Obstaja tudi mnogo aplikacij, ki uporabljajo algoritem za iskanje konveksne ovojnice.

Iskanje konveksne ovojnice v praksi se uporablja:

• pri zajemu vida območja gibanja (npr. najkrajša pot, po kateri se bo gibal robot),

  Robot s pomočjo konveksne ovojnice poišče najkrajšo pot, da se izogne oviri.

• v zemljepisnih informacijskih sistemih (npr. za določanje poplavnih območij),

  Določanje poplavnih območij na zemljevidu.

• pri prepoznavanju oblik (npr. prepoznavanje registrskih oznak na tablicah),
• za iskanje največje razdalje med pari točk v neki množici,
• v statistiki,
• pri obdelavi slik,
• ...

Preverimo naučeno znanje o konveksnih ovojnicah in Grahamovem algoritmu. Pri vsakem vprašanju je samo en pravilen odgovor.

1. VPRAŠANJE: Kakšna je časovna odvisnost Grahamovega algoritma v najslabšem primeru?

Preveri

2. VPRAŠANJE: Če izvajamo pregled točk v smeri urinega kazalca, v katerem primeru nadaljujemo s pregledom točk (izberemo nove točke P, Q in R)?

Preveri

3. VPRAŠANJE: V primeru, ko so vse točke iz začetne množice točk elementi konveksne ovojnice dane množice, točke ležijo na...?

Preveri

4. VPRAŠANJE: Konveksna množica je v geometriji množica točk, za katero velja, da pri poljubni izbiri dveh točk iz te množice, daljica, ki ju povezuje leži... ?

Preveri

5. VPRAŠANJE: Kaj je konveksna ovojnica množice točk?

Preveri

6. VPRAŠANJE: Grahamov algoritem je ...?

Preveri