Konveksni ogrinjači rečemo tudi konveksna lupina oz. ovojnica.

V realnem vektorskem prostoru V imamo neko množico točk X. Konveksna ogrinjača te množice točk X je v matematiki najmanjša konveksna množica, ki vsebuje X kot podmnožico.

Konveksna množica je v geometriji taka množica M, da je za vsak par točk x, y M, tudi daljica med x in y vsebovana v M.

Za lažje razumevanje si konveksno ogrinjačo lahko predstavljamo na naslednji način.

Imamo nekaj risalnih žebljičkov, ki jih poljubno zabijemo v desko. Ti žebljički nam predstavljajo množico X. Vzamemo elastiko in jo razpnemo okrog žebljičkov tako, da se vsi nahajajo znotraj elastike. Ko elastiko spustimo, se ta lepo napne okrog njih. Žebljičke, katerih se elastika dotika, imenujemo člani konveksne ogrinjače.

Člani konveksne ogrinjače so žebljički A, B, D, G in F.

Za reševanje konveksne ogrinjače 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

V nadaljevanju si bomo ogledali Grahamov pregled.

Bilo je prelepo popoldne in Janezek se je odločil, da bo odšel na sprehod. Po enourni hoji je prišel na ogromno jaso, na kateri so rasli grmovi malin. Poizkusil je te slastne sadeže in zdeli so se mu naravnost odlični. Na njegovo žalost pa je opazil tudi sledi medvedov. Odločil se je, da bo maline zavaroval pred medvedi. Pomagaj mu ograditi maline.

Predstavljajmo si, da so grmovi malin točke neke množice. Če okoli te množico postavimo konveksno ogrinjačo bo to ravno ograda, ki jo Janezek potrebuje. Maline bodo znotraj ograde in medvedi ne bodo mogli do sadežev.

To je naša jasa z grmovi malin.

• Najprej poiščemo pivotno točko. To je točka, ki ima najmanjšo / največjo y koordinato ali najmanjšo / največjo x koordinato. Poimenujemo jo P.

V naših primerih bo, za pivotno točko, vedno izbrana točka z najmanjšo y koordinato.

• Skozi vse točke in točko P potegnemo premice. Nato točke med seboj povežemo, da dobimo mnogokotnik. Pričnemo v točki P in povezujemo glede na naklone premic.

Pa si oglejmo, kako to povezovanje točk izgleda v praksi.

• Naš primer je po povezovanju točk videti tako:

• Sedaj pa pričnemo z našim pregledom. Pregled se bo izvajal v smeri urinega kazalca. Lahko bi začeli tudi v obratni smeri, a takšno različico si bomo ogledali v naslednjem primeru. Začnemo v točki P, ki jo preimenujemo v p. Naslednji dve točki mnogokotnika pa preimenujemo v q in r. Ta trojica točk bodo vedno zaporedne točke.

• Če te točke določajo levi obrat oz. zasuk izbrišemo točko q iz mnogokotnika in povežemo točki p in r.
  Če pa te točke določajo desni obrat oz. zasuk samo nadaljujemo s pregledom ter poimenovanja točk p, q in r premaknemo za eno točko naprej.

Levi obrat

Desni obrat

V našem primeru imamo desni obrat, zato nadaljujemo s pregledom. Prejšnja točka q postane p, r postane q in naslednja točka v mnogokotniku postane r.

V tem primeru pa točke p, q in r določajo levi zasuk. Zato točko q odstranimo iz mnogokotnika. Sedaj točka p postane predhodna točka, točka q postane točka p, točka r pa ostane ista.

Imamo nove točke p, q in r. Te nam določajo desni zasuk, zato samo nadaljujemo s pregledom. Poimenovanje točk premaknemo za eno točko naprej.

Spet imamo desni zasuk.

Pri trenutnem pregledu naletimo na levi zasuk, zato točko q odstranimo iz mnogokotnika. Popravimo poimenovanja točk.

Naleteli smo na desni zasuk, samo nadaljujemo s pregledom.

Trenutna trojica določa levi obrat, zato moramo točko q odstraniti iz mnogokotnika. Popravimo tudi poimenovanje točk.

Naleteli smo na desni obrat, zato samo nadaljujemo s pregledom.

Levi obrat, zato točko q odstranimo iz mnogokotnika.

Desni obrat, zato samo nadaljujemo s pregledom.

Z Grahamovim pregledom nadaljujem na preostalih točkah. Končamo šele takrat, ko je točka r enaka točki P.

Končni rezultat je videti tako:

Janezku smo pomagali, da je maline zaščitil pred medvedi. Člani konveksne ogrinjače so tisti grmi, ki se dotikajo ograde.

Sedaj pa si v celoti oglejmo nekoliko manjši primer.
Za pivot izberemo najnižjo točko iz naše množice.

Skozi točko P in ostale točke narišemo premice, ter točke povežemo glede na kot v mnogokotnik.

Z Grahamovim pregledom lahko začnemo tudi v nasprotni smeri urinega kazalca. Vendar v tem primeru izbrišemo tisto točko, pri kateri naredimo desni zasuk.

Točke p, q in r določajo levi zasuk, zato samo nadaljujemo s pregledom. Točka q postane točka p, točka r postane q, naslednja točka v mnogokotniku pa postane r.

Pri tem pregledu nam točke določajo desni zasuk, zato bomo točko q odstranili iz mnogokotnika. Popraviti moramo tudi imena točk.

Spet imamo levi zasuk, zato samo nadaljujemo s pregledom. Prestavimo se na naslednjo trojico točk.

Imamo levi zasuk, zato nadaljujemo.

Zopet imamo levi zasuk. S točko r smo prišli do pivota P, zato s pregledom zaključimo.

Pri iskanju konveksne ogrinjače lahko naletimo tudi na primer, ko imamo več najnižjih točk (več točk ima enako y koordinato).

V tem primeru vzamemo tisto, ki ima tudi koordinato x najmanjšo. Takšna točka bo zagotovo ležala na konveksni ogrinjači, saj hkrati pod njo in levo od nje ni nobene druge točke. (Seveda levo od nje so točke, ampak imajo vse večjo y koordinato.)

V splošnem lahko izberemo pivotno točko na 8 načinov. Med tistimi, ki imajo:

• najmanjšo y koordinato izberemo tisto z najmanjšo x koordinato
• najmanjšo y koordinato izberemo tisto z največjo x koordinato
• največjo y koordinato izberemo tisto z najmanjšo x koordinato
• največjo y koordinato izberemo tisto z največjo x koordinato
• najmanjšo x koordinato izberemo tisto z najmanjšo y koordinato
• najmanjšo x koordinato izberemo tisto z največjo y koordinato
• največjo x koordinato izberemo tisto z najmanjšo y koordinato
• največjo x koordinato izberemo tisto z največjo y koordinato

Točki A in B imata enako koordinato y.

Konveksna ogrinjača, kjer sta dve točki najnižji.

(Grahamov pregled)

Razlaga algoritma

Imamo množico točk P. V njem poiščemo pivotno točko p* (tista, ki ima najmanjšo koordinato y). Množico točk, brez pivotne točke, uredimo glede na naklon premic v smeri urinega kazalva (kot smo si ogledali na začetku). Ustvarimo prazen sklad S. Nanj damo p* in p1. Z zanko gremo po preostalih točkah v množici. Za točko q določimo točko, ki je na vrhu sklada, za točko p pa določimo točko, ki je pod vrhom. Če določa trojica p, q in i-ta točka obrat na desno, damo i-to točko na sklad S. V nasprotnem primeru pa točko q izbrišemo iz sklada. Ko se zanka zaključi, vrnemo sklad S, v katerem so člani konveksne ogrinjače.

Imamo množico točk P = {(1.9,1.1),(2.9,-1.7),(5.7,0.4),(7,-1.2),(4,0),(4.2,-2.3)}.

Najprej poiščemo pivotno točko. To je točka p* = (4.2,-2.3).

Nato preostale točke uredimo glede na naklon premic, ki potekajo skozi pivotno točko in ostale točke v množici. P = {(2.9,-1.7),(1.9,1.1),(4,0),(5.7,0.4),(7,-1.2)}.

Ustvarimo prazen sklad S. Vanj dodamo p* in p1 = (2.9,-1.7).

Gremo v zanko, ki bo pregledala celotno urejeno množico točk. Za spremenljivko q določimo vrh sklada (v našem primeru točko p1), za spremenljivko p pa določimo točko pod vrhom sklada (v našem primeru p*).

Ker trojica p, q in p2 določa obrat na desno, damo p2 na sklad. Tako imamo v našem skladu točke p*, p1 in p2.

Sedaj gledamo trojico p1, p2 in p3. Ta spet določa desni obrat, zato točko p3 dodamo na sklad. Naš sklad je sedaj videti tako: S = {p*,p1,p2,p3}.

Naslednja trojica bo sedaj p2, p3 in p4. Ta določa levi obrat, zato točko p3 odstranimo iz sklada. S = {p*,p1,p2}.

Trojica p1, p2 in p4 spet določa desni obrat, zato točko p4 damo na sklad. S = {p*,p1,p2,p4}.

Trojica p2, p4 in p5 določa desni obrat, zato točko p5 vstavimo v sklad. S = {p*,p1,p2,p4,p5}.

Ko indeks povečamo, se zanka ne izvede več, zato samo vrnemo sklad. Ta nam predstavlja točke, ki sestavljajo konveksno ogrinjačo.

Izris točk uporabljenih v algoritmu in pravilnost rešitve.

Časovna zahtevnost algoritma je O(n log(n)).

• O(n) za iskanje P "pivot"
• O(n log(n)) za ureditev po naklonih premic
• O(n) za sprehod (ali gre za levi ali desni obrat)

Na prvi pogleda izgleda, da je časovna zahtevnost za sprehod O(n), ker gre algoritem preveriti ali se je ob odstranitvi točke mogoče pojavil še kakšen levi obrat. V resnici pa gre pri sprehodu 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 in enkrat kot točka v desnem obratu.

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

Problem iskanja konveksne ogrinjače najdemo v različnih praktičnah primerih:

• v prepoznavanju oblik
• v obdelavi slik
• v statistiki
• v geografskih informacijskih sistemih

Praktičen primer

Na nekem območju imamo veliko število varnostnih kamer. Vse kamere vidijo ena drugo. Te kamere želimo nadomestiti z eno samo, ki pa ima ceno v odvisnosti od kota gibanja. Ker želimo najceneje rešiti problem, nas zanima, na katero mesto naj postavimo novo kamero.

Ideja bi bila, da poiščemo konveksno ogrinjačo vseh varnostnih kamer in izberemo tisto kamero, ki je članica konveksne ogrinjače in ima najmanjši kot rotacije.

Katere točke so člani konveksne ogrinjače?

Ali smo mnogokotnik pravilno povezali, glede na naklone premic oz. glede na način, ki smo ga povedali na začetku prosojnic?

Z Grahamovim pregledom obiskujemo točke v smeri urinega kazalca. Ali točko q odstranimo iz mnogokotnika ali ne?

• Grahamov pregled - MaFiRa Wiki (26.2.2012)

• Konveksna ovojnica - Graham (26.2.2012)

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Second Edition