Dinami£nost

Ob£asno se dogajajo spremembe v vhodnih podatkih, saj se spremenijo ali uvedejo nove proge in spremenijo ali dodajo nove postaje. Ve£ina dozdaj²njih pristopov je osredoto£ena na izdelavo stati£ne risbe. Risbo generirajo v celoti in se ne ozirajo na to ali bi sprememba v vhodnih podatkih vodila do zelo podobne ali izrazito druga£ne risbe. Nadgraditev teh pristopov za dinami£no generiranje risb je malo raziskano podro£je. Izjema je Chivers [5], ki je svoj pristop z vzmetmi in magnetnimi silami raz²iril na dinami£no razli£ico.

3 Algoritem

Predstavili bomo nov algoritem za oktilinearno shematizacijo. Ta vhodno risbo transformira v dveh korakih. V prvem koraku vsa vozli²£a vhodnega grafa pusti na istih koordinatah in transformira le potek povezav, da postanejo oktilinearna.

S tem se zagotovi oktilinearnost povezav, pri £emer se ohranja cikli£ni vrstni red povezav okrog vsakega vozli²£a in relativne pozicije vozli²£. Pomankljivost dobljene risbe je predvsem neenakomerna dolºina povezav. S tem se ukvarja drugi korak algoritma. Ta poda kombinatori£ni opis pogojev, ki morajo veljati, £e ºelimo dolºino neke povezave spremeniti in ob tem ohranjati oktilinearnost in izgled preostalega dela risbe. Te pogoje formuliramo v obliki linearnega celo²tevilskega programa, katerega re²itev inducira podgraf, ki ga je moºno translirati in ohranjati vse zaºeljene lastnosti.

Oba koraka kot podrutino uporabljata razdelitev ravnine na trapeze. To je ta-k²na mnoºica trapezov, ki pokrije ravnino in ima povezave vhodnega grafa na osnov-nicah ali krakih trapezov. Tak²no konstrukcijo je moºno uporabiti na ve£ na£inov.

V prvem koraku je uporabljena tako, da se s pomo£jo pomikanja po osnovnicah trapezov, ki leºijo v vodoravni, navpi£ni ali diagonalni smeri, pride do oktilinearnih poligonalnih poti. V drugem koraku pa je uporabljena tako, da s pomo£jo sosedno-sti trapezov posku²amo najti cikel (pod dolo£enimi pogoji), ki razdeli risbo grafa na dva dela. Povezava, ki ji ºelimo spremeniti dolºino poteka iz zunanjosti cikla v notranjost. Vozli²£a znotraj cikla dolo£ajo podgraf, ki ga je moºno translirati, pri

£emer se oktilinearnost in cikli£ni vrstni red povezav okrog vozli²£ ohranja. Vozli²£a in povezave, ki leºijo v zunanjosti cikla, ostanejo nespremenjene.

V nadaljevanju je najprej denirana trapezna dekompozicija ravnine in nato opisana oba koraka algoritma.

3.1 Trapezna dekompozicija

Osnovna ideja trapezne dekompozicije je, da s pomo£jo ravninske risbe grafa G rav-nino razdelimo na trapeze na tak na£in, da so osnovnice od vseh trapezov vzporedne.

Kraki trapezov leºijo na povezavah, razen kadar je kak²na od povezav vzporedna z osnovnicami (v tem primeru je del osnovnic). Naklon osnovnic je lahko poljuben.

Zaradi tega so trapezi lahko zarotirani in zato tudi dekompozicija ni enoli£na.

Denicija 3.1. Naj bo G ravninski graf z risbo Γ, kjer je vsaka povezava daljica.

Naj bo α ∈ [0,2π). Naj bo risba Γ vsebovana v dovolj velikem pravokotniku R, ki je zarotiran za kotα. ƒe iz vsakega vozli²£av ∈Gnari²emo pomoºni ravni £rti pod kotom α, dokler ne zadanemo neko povezavo grafa G, vozli²£e grafa G ali stranico pravokotnikaR, potem dobimo risbo nekega grafa. Lica tega grafa razdelijo ravnino na disjunktne mnoºice. Vsako lice je trapez, pravokotnik ali trikotnik (slika 17), razen zunanjega lica, ki je ravnina brez R. Na pravokotnike in trikotnike gledamo kot na poseben primer trapezov. Dobljeno razdelitev ravnine imenujemo trapezna dekompozicija ravnine glede na graf G in risboΓ v smeriα. Kadar je kontekst jasen uporabljamo skraj²an izraz trapezna dekompozicija ravnine.

V nadaljevanju se omejimo na primer, ko so osnovnice trapezov navpi£ne. V

Slika 17: Trapezna dekompozicija ravnine glede na grafG, kjer so osnovnice trapezov navpi£ne.

drugih primerih lahko risbo zarotiramo in sledimo istim argumentom kot za ta pri-mer.

Opomba 3.2. Vedno obstaja enoli£no dolo£en najbolj levi in najbolj desni trapez.

Dokaz. Ker ima G kon£no mnogo vozli²£, v njegovi risbi obstaja mnoºica tak²nih, ki imajo najmanj²o x-koordinato. Ozna£imo jo zLV. Naj bo mnoºica LE mnoºica povezav iz G med vozli²£i iz L_V. Na levi od L_V in L_E ni nobenega vozli²£a ali povezave. Naj bo K mnoºica ravnih £rt, £e iz vozli²£ L_V nari²emo £rte navzgor in navzdol do prvega vozli²£a v LV ali stranice pravokotnika R (kot v deniciji trapezne dekompozicije). Tedaj unija £rtL_E∪K poteka od spodnjega do zgornjega roba pravokotnika R in predstavlja desno stranico najbolj levega trapeza. Podobno za najbolj desni trapez.

Opomba 3.3. Vsako vozli²£e v trapezni dekompoziciji ima stopnjo vsaj2.

Dokaz. Naj bo v poljubno vozli²£e. Po konstrukciji je v bodisi vozli²£e grafa G, bodisi ogli²£e pravokotnika R, bodisi kon£na to£ka navpi£ne £rte do neke povezave grafa G ali stranice pravokotnika R. V prvem primeru je deg(v) ≥ 2, saj v de-kompoziciji obstajata vsaj povezavi navzgor in navzdol, lahko pa ²e kak²na iz grafa G. V drugem primeru je deg(v) = 2, saj gre za ogli²£e pravokotnika R. V tretjem primeru je bodisideg(v) = 3, kadar je kon£na to£ka navpi£ne £rte v notranjosti neke povezave grafa G ali stranice R, bodisi deg(v) ≥ 2, £e sovpada z nekim vozli²£em grafaG. Sledi, da je deg(v)≥2.

Opomba 3.4. Vsako (notranje) lice trapezne dekompozicije je konveksno.

Dokaz. Potreben in zadosten pogoj za konveksnost mnogokotnika je, da ima vse notranje kote manj²e ali enake π. Premislimo, da je ta pogoj je izpolnjen. ƒe gre za ogli²£e, ki izhaja iz vozli²£a grafa G, potem po deniciji trapezne dekompozicije iz njega izhajata vsaj povezavi navzgor in navzdol. Torej je notranji kot vsakega sosednjega lica manj²i ali enakπ. ƒe gre za ogli²£e pravkotnikaR, potem je notranji

kot enak ^π₂. ƒe gre za ogli²£e, ki je kon£na to£ka navpi£ne £rte, potem ta razdeli povezavo grafa G ali stranico R na dve (kolinearni) povezavi in notranji koti sose-dnjih lic so ponovno manj²i ali enaki π. Sledi, da so (notranja) lica dekompozicije konveksna.

Trditev 3.5. Vsako notranje lice trapezne dekompozicije je trapez. Pri tem na trikotnike in pravokotnike gledamo kot na poseben primer trapezov.

Dokaz. Naj bo f notranje lice. Najprej premislimo, da je na levo in desno stran omejeno z navpi£nima £rtama (lahko dolºine 0) in da na robu ne vsebuje drugih navpi£nih £rt. Vozli²£a na robu od f so podmnoºica vozli²£ izG in vozli²£ na koncu pomoºnih navpi£nih £rt. Ker jih je kon£no mnogo, obstajata vozli²£i z najve£jo in najmanj²oxkoordinato, ki sta tudi vozli²£i grafaG. To drºi, saj ima vsaka navpi£na pomoºna povezava ali povezava grafaG, vsaj na enem izmed kraji²£ vozli²£e grafaG. Ozna£imo ju z v_min in v_max in za£asno predpostavimo, da sta enoli£no dolo£eni. Po deniciji trapezne dekompozicije iz v_min in v_max izhajata navpi£ni povezavi. Lahko sta del lica f, vendar ne nujno. Premislimo, da nobena druga navpi£na povezava e_vert ne more biti del lica f. ƒe bi bila, potem leºi na koordinati med v_min inv_max. Po opombi 3.4 vemo, da jef konveksno. Torej mora notranjost odf leºati bodisi na levi bodisi na desni strani ode_vert. Vendar od tod sledi, da daljica od notranje strani povezave e_vert do vsaj enega izmed vozli²£ v_min ali v_max pre£ka zunanjost (slika 18).

Torej tak²na navpi£na povezava ne more obstajati. V primeru, dav_min inv_max nista enoli£ni, potem so preostala vozli²£a z isto x koordinato povezana z navpi£nimi povezavami. Res, saj bi v nasprotnem primeru v okolici dveh tak²nih vozli²£ na²li notranji to£ki, med katerima daljica pre£ka zunanjost (podobno kot na sliki 18), kar je v protislovju s konveksnostjo.

v_min v_max

e_vert

Slika 18: Lice lahko vsebuje navpi£ne povezave le skrajno levo ali desno, sicer kr²i konveksnost.

šelimo ²e videti, da sta leva in desna navpi£na £rta zgoraj in spodaj povezani z ravno £rto. Od tod bo sledilo, da je f trapez. Naj bo l_max vozli²£e, ki ima med najbolj levimi vozli²£i najve£jo y koordinato. Podobno naj bo r_max vozli²£e, ki ima med najbolj desnimi vozli²£i najve£joykoordinato. Vemo, da morata bitil_maxinr_max povezani in da mora biti notranjost na spodnji strani povezav med njima. šelimo videti, da sta povezani zgolj z ravno £rto. Recimo, da nista. To pomeni, da vmes obstaja vsaj eno dodatno vozli²£e iz grafa G. Po deniciji trapezne dekompozicije morata iz njega izhajati navpi£ni £rti. To je protislovje, saj ima lice f navpi£no £rto na robu zgolj skrajno levo in skrajno desno in nobenih drugih.

Sledi, da ima f na levi in desni navpi£no £rto, ki sta zgoraj in spodaj povezani z ravno £rto. Torej je f trapez (navpi£ni £rti sta osnovnici, povezavi med njima pa kraka).

Trditev 3.6. Naj bo f poljubno lice trapezne dekompozicije. Potem leva in desna osnovnica vsebujeta (vsaka) vsaj eno vozli²£e iz G, kraka pa ne vsebujeta nobenega vozli²£a iz G, razen morda v kraji²£u.

Dokaz. Naj bo f poljubno lice. Opazimo, da je osnovnica unija povezav iz G, vozli²£ iz G in pomoºnih £rt. ƒe je pomoºna £rta del osnovnice, potem je vozli²£e od koder pomoºna £rta izhaja tudi del osnovnice. ƒe je povezava del osnovnice, potem sta tudi njeni kraji²£i del osnovnice. Sledi, da je v uniji vsaj eno vozli²£e iz G. V notranjosti krakov ne nastopa nobeno vozli²£e, saj bi sicer med levo in desno osnovnico po deniciji trapezne dekompozicije obstajala navpi£na £rta.

Trditev 3.7. Naj bo Gravinski graf z n vozli²£i. Ozna£imo trapezno dekompozicijo grafaG z T(G)in nanjo gledamo kot na graf. Potem je T(G)ravninski graf z O(n) vozli²£i in povezavami.

Dokaz. Ravninskost sledi iz denicije, saj se navpi£ne £rte ne kriºajo in zato ne morejo inducirati minorja ali subdivizije odK₅aliK_3,3. Premislimo koliko je vT(G) vozli²£. Po deniciji trapezne dekompozicije iz vsakega vozli²£a grafa G nari²emo pomoºno £rto navzgor in navzdol. Torej vsako vozli²£e iz G inducira najve£ 2novi vozli²£i vT(G). Zato je vT(G)kve£jemun+ 2n+ 4 vozli²£, pri £emer se²tevanec4 nastopa zaradi ²tirih ogli²£ pravokotnikaR. Premislimo kak²no je ²tevilo povezav v T(G). Naj bom ²tevilo povezav v grafu G. Po deniciji trapezne dekompozicije iz vsakega vozli²£a v Gpoteka navpi£na £rta navzgor in navzdol. Kraji²£e te navpi£ne

£rte je na vozli²£u grafaG, povezavi grafa Gali stranici pravokotnika R. V zadnjih dveh primerih navpi£na £rta razdeli povezavo vGoz. stranico odR na dve povezavi v T(G). Sledi, da v T(G) nastopa kve£jemu m + 2n+ 2n + 4 povezav. Ker je m∈ O(n), je ²tevilo povezav vT(G) tudi v O(n).

Trapezna dekompozicija se pogosto uporablja v povezavi s poizvedbo v katerem licu leºi dana to£ka. V tem primeru nam pomaga izdelati naklju£nostno podat-kovno strukturo, ki na to vpra²anje odgovori v pri£akovanem O(logn) £asa (knjiga [7], poglavje 6). V na²em primeru nas ne bodo zanimale poizvedbe to£k, temve£

informacija o tem kateri trapezi so sosednji. V ta namen deniramo (multi)graf trapezne dekompozicije.

Denicija 3.8. Naj boGravninski graf s trapezno dekompozicijo, ki ima osnovnice trapezov v navpi£ni smeri. Graf trapezne dekompozicije je (multi)graf, ki ima za vozli²£a notranja lica trapezne dekompozicije, povezave pa potekajo med tistimi sosednjimi lici, ki imajo skupno navpi£no £rto.

Zgled lahko vidimo na sliki 19. V zgornji deniciji nastopa sosednost le v primeru skupne navpi£ne £rte, na kateri sta osnovnici trapezov, ne pa tudi drugih skupnih

£rt, na katerih leºijo kraki. To denicijo je moºno raz²iriti tudi za primere skupnih krakov. To bomo storili kasneje v poglavju 3.3, ko bomo tak²no raz²irjeno denicijo tudi potrebovali.

Na podoben na£in lahko deniramo graf trapezne dekompozicije v smeri, ki ni navpi£na.

Slika 19: Levo: trapezna dekompozicija grafa G. Desno: graf trapezne dekompozi-cije.

Opomba 3.9. Graf trapezne dekompozicije ni nujno povezan (npr. slika 19).

Opomba 3.10. V splo²nem je graf trapezne dekompozicije pravi multigraf, saj imamo med dvema trapezoma lahko ve£ kot eno povezavo. Primer je graf poti P_n narisan navpi£no (slika 20). Ta primer pokaºe tudi, da je stopnja vozli²£ lahkoO(n).

R

Pn

Slika 20: Graf trapezne dekompozicije potiP_n.

Trditev 3.11. Naj boG ravinski graf zn vozli²£i inT_G graf trapezne dekompozicije.

Potem je TG ravninski graf z O(n) vozli²£i in povezavami.

Dokaz. Ravninskost lahko premislimo tako, da nari²emo ravninsko risbo. Po deni-ciji 3.8 so vozli²£a odT_Glica trapezne dekompozicije. Ta so po trditvi 3.5 trapezi. V vsakem trapezu si izberemo poljubno to£ko v notranjosti in ker so trapezi konveksni lahko nari²emo ravno £rto do katerekoli to£ke na robu. V posebnem primeru, ko si dva sosednja trapeza delita del osnovnice, lahko iz notranjosti enega in drugega nari²emo ravni £rti do neke to£ke na skupnem delu roba. To storimo za vse sosednje

trapeze, vedno iz iste to£ke v notranjosti, da se £rte ne sekajo. Tako dobimo rav-ninsko risbo odT_G. Ker je ²tevilo lic trapezne dekompozicije O(n)je ²tevilo vozli²£

in povezav v T_G tudi O(n). 3.1.1 Algoritem

Navedli bomo algoritem za u£inkovit izra£un trapezne dekompozicije. Uporabili bomo algoritem pometanja. Njegova osnovna ideja je naslednja. Z navpi£no pre-mico p pometamo od leve proti desni. Dogodki so to£ke vhodnega grafa, urejene leksikografsko. Vsi dogodki so znani vnaprej, vendar se jih obravnava po blokih.

Blok dogodkov je mnoºica zaporednih dogodkov z isto x koordinato, ki leºijo med dvema povezavama vG(slika 21). Ti dve povezavi nimata nobeno kraji²£e na tej x koordinati. Med dogodki iz istega bloka ne poteka nobena druga povezava iz G, ki pre£ka xkoordinato dogodkov (je nima na kraji²£u) in ki bi imela en del dogodkov na eni strani in drug del na drugi strani. V tem primeru bi se blok razdelil na dva manj²a bloka. Stanje je urejeno binarno iskalno drevo in hrani trapeze, ki sekajo premico p. Trapezi v stanju so urejeni glede na nara²£ajo£oykoordinato prese£i²£a zgornjega roba trapeza s premicop. Stanje se posodablja po obravnavi bloka dogod-kov. Na izhod vrnemo seznam vozli²£, ki predstavljajo trapeze, in seznam povezav med njimi. Vsak trapez hrani kazalce na vozli²£a in povezave, ki tvorijo njegovi osnovnici, in dva kazalca na povezavi, ki tvorita njegova kraka.

Slika 21: Blok dogodkov leºi na isti x-koordinati med dvema povezavama.

Na za£etku dodamo na izhod najbolj levi trapez, nato sledi obravnava blokov dogodkov. Ta poteka v dveh zankah. Zunanja zanka obravnava prvi dogodek v bloku in pri tem na izhod doda novo vozli²£e, ki predstavlja trapez desno spodaj pod trenutnim dogodkom. Hkrati doda tudi novo povezavo s trapezom levo spodaj, ki ga prebere iz stanja. Pri dodajanju nove povezave se posodobita oba trapeza, levi in desni, saj hranita informacijo o sosedih.

Nato notranja zanka nadaljuje z obravnavo tega dogodka in vseh preostalih do-godkov v tem bloku. Za vsak dogodek se sprehodi £ez njegove inciden£ne daljice na desni strani in vsaki£ na izhod doda en nov trapez. Pri tem shrani informacijo o zgornji in spodnji daljici, ki ga omejuje, saj to predstavlja njegova kraka. Ob za-dnji (najvi²ji) inciden£ni daljici na izhod doda tudi povezavo z najvi²jim trapezom

na levi strani dogodka, ki ga prebere iz stanja. Nato nadaljuje isto obravnavo pri naslednjem dogodku.

Ko zanka pride do zadnjega dogodka v bloku se posodobi stanje. Posodobi se tako, da se odstranijo vsi trapezi, ko so bili na levi strani bloka dogodkov, in dodajo vsi novi, ki so na desni.

Psevdokoda je napisana v algoritmu 4.

Algoritem 4 Trapezna dekompozicija

1: procedure TrapeznaDekompozicija(V, E)

2: ▷ Inicializacija

3: V_out, E_out ← prazna seznama ▷ Vozli²£a in povezave izhodnega grafa

4: D ←seznam vozli²£ V ▷ Dogodki

5: D.sort() ▷Leksikografsko sortiramo

6: l₀ ← nov trapez ▷ Najbolj levi trapez

7: S ← prazno dvoji²ko iskalno drevo ▷ Trenutno stanje

8: S.insert(l₀)

9: V_out.push(l₀)

10: ▷ Obravnava dogodkov

11: for i= 1; i≤D.size(); i+ + do

12: l_start ←S.upper_bound(D[i]) ▷Trapez spodaj levo, ki vsebuje D[i]

13: r_start← nov trapez ▷Nov trapez spodaj desno, ki vsebuje D[i]

14: e← nova povezava med l_start inr_start

15: E_out.push(e)

16: V_new ← prazen seznam trapezov ▷Novi trapezi na desni

17: V_new.push(r_start)

18: l_cur ←l_start ▷ Trenutni levi trapez

19: current_block ←True

20: while current_block do ▷ Obravnava bloka

21: I_l ←leve inciden£ne povezave od D[i]

22: if ¬I_l.empty()then

23: l_cur←I_l.upper() ▷ Trapez levo zgoraj odD[i]

24: end if

25: I_r ←desne inciden£ne povezave od D[i]

26: for j = 1, . . . , I_r.size() do ▷Novi trapezi na desni

38: current_block ←False

39: end if

40: i←i+ 1

41: end while

42: V_out.append(V_new) ▷Dodajanje novih trapezov na izhod

43: S.erase_interval(l_start, l_cur) ▷Odstranitev obravnavanih trapezov

44: S.insert_list(V_new) ▷Dodajanje novih trapezov v stanje

45: end for

46: end procedure

3.1.2 Uporabljene strukture in £asovna zahtevnost

Vhod Algoritem na vhod dobi seznam vozli²£ in seznam povezav grafa G. Pri tem je vsako vozli²£e podano s koordinatama (x, y) in hrani mnoºico kazalcev na inciden£ne povezave. Povezave so podane s kazalcema na vozli²£i, ki predstavljata kraji²£i povezave. Ker je grafGravninski, je prostorska zahtevnost vhodnih podat-kov O(n), kjer je n ²tevilo vozli²£.

Stanje Stanje je uravnoteºeno iskalno binarno drevo. Hrani trapeze, ki sekajo navpi£no premico, s katero pometamo, in so urejeni po nara²£ajo£i y koordinati.

Natan£neje, trapez T₁ je nad trapezom T₂, £e je prese£i²£e navpi£ne premice z zgor-njim robom od T₁ nad prese£i²£em navpi£ne premice z zgornjim robom od T₂. Na stanju uporabljamo slede£e operacije:

ˆ insert(·), ki prejme trapez in ga vstavi v drevo v £asu O(logn).

ˆ insert_list(·), ki prejme seznam trapezov dolºinek in ga vstavi v drevo v £asu O(klogn).

ˆ erase_interval(Tf rom, Tto), ki pobri²e vse elemente v drevesu, ki so ve£ji ali enaki kot T_{f rom}, ter manj²i ali enaki kot T_to. Ta operacija se izvede v £asu O(k), kjer je k ²tevilo izbrisanih elementov.

ˆ upper_bound(·), ki prejme to£ko in vrne najmanj²i element v drevesu, ki je ve£ji ali enak kot prejeti argument. To vzame O(logn) £asa.

Dogodki Dogodki so vozli²£a vhodnega grafa G, urejena leksikografsko. Vsi do-godki so znani vnaprej in jih hranimo v seznamu.

Izhod Na izhod algoritem vrne seznam vozli²£, ki predstavljajo trapeze, in se-znam povezav med njimi. Oba sese-znama uporabljata operacijo push(·), ki na konec seznama doda nov element za kar porabi O(1) £asa. Velikost izhoda je O(n) po trditvi 3.11.

3.1.3 Pravilnost delovanja

šelimo se prepri£ati, da algoritem 4 na izhodu vrne graf trapezne dekompozicije iz denicije 3.8. Za laºjo berljivost bomo lica trapezne dekompozicije ena£ili z vozli²£i grafa trapezne dekompozicije.

Lema 3.12. Liki, ki jih denirajo elementi na izhodu algoritma 4 so trapezi.

Dokaz. Vsak lik na izhodu je deniran z zgornjo in spodnjo (nenavpi£no) ravno £rto ter s povezavami, kadar obstajajo, na levo in desno s sosednjimi liki. Recimo, da te povezave obstajajo. Vsaka med njimi vsebuje informacijo o dogodku, ki jo inducira.

To je neko vozli²£e grafa G. Po konstrukciji so vse povezave na levi dodane na izhod v istem bloku dogodkov. Zato je lik na levi strani omejen z navpi£no ravno £rto.

Podobno na desni strani. Sledi, da je trapez. Recimo sedaj, da na levo ali desno stran ni nobene povezave s sosednjimi liki. To se zgodi, kadar imata zgornja in spodnja £rta skupno kraji²£e. V tem primeru to skupno kraji²£e omejuje lik na levo oz. desno in gre za trikotnik, ki ga obravnavamo kot poseben primer trapezov.

Trditev 3.13. Vsak trapez na izhodu algoritma 4 ustreza nekemu licu trapezne de-kompozicije in vsako lice nekemu trapezu.

Dokaz. Vsak trapez na izhodu algoritma 4 je dolo£en s podmnoºico vozli²£ blokov dogodkov, ki inducirajo njegovo levo in desno osnovnico, ter dela zgornje in spodnje daljice, kar predstavlja njegova kraka. Vsak blok dogodkov je po deniciji trape-zne dekompozicije del pomoºnih £rt ali navpi£nih povezav grafa G. Ravno tako je vsaka pomoºna ali navpi£na povezava del bloka dogodkov. Torej se navpi£ne linije v deniciji trapezne dekompozicije ujemajo z osnovnicami trapezov na izhodu algo-ritma 4. Podobno se ujemajo tudi kraki trapezov in nenavpi£ne povezave v trapezni dekompoziciji. Sledi, da gre za isto razdelitev ravnine.

3.2 Oktilinearizacija

Naj bo G ravninski graf z risbo Γ, kjer je vsaka povezava podana kot poligonalna pot. To risbo ºelimo transformirati v novo oktilinearno risboΓ^′ in pri tem ohranjati koordinate vozli²£ nespremenjene. šelimo tudi, da je risbaΓ^′ na nek na£in podobna izvorni risbiΓ. Podobnost je moºno denirati na razli£ne na£ine. Tu jo bomo opisali z izpolnjevanjem naslednjih pogojev:

(P1) Vozli²£em ne spreminjamo koordinat.

(P2) Cikli£ni vrstni red povezav okrog vsakega vozli²£a se ohranja.

(P3) Povezave se ne sekajo.

(P4) Povezave potekajo blizu originalnih povezav. To lahko opi²emo s pogojem d(Γ, x)≤δ ∀x∈Γ^′

kjer je d(Γ, x) razdalja med krivuljo in to£ko terδ izbrana konstanta, ki pred-stavlja najve£jo dovoljeno oddaljenost.

kjer je d(Γ, x) razdalja med krivuljo in to£ko terδ izbrana konstanta, ki pred-stavlja najve£jo dovoljeno oddaljenost.

In document MagistrskodeloMentor:prof.dr.BorutRobi£Ljubljana,2021 ALGORITEMZAOKTILINEARNOSHEMATIZACIJOOMREšIJ UNIVERZAVLJUBLJANIFAKULTETAZAMATEMATIKOINFIZIKOFAKULTETAZARAƒUNALNI’TVOININFORMATIKORa£unalni²tvoinmatematika2.stopnjaDomenKeglevi£ (Strani 29-0)