Vaje iz računske geometrije Sergio Cabello
9. november 2010
naslov: Vaje iz računske geometrije
avtorske pravice: Sergio Cabello
izdaja: prva izdaja
založnik: samozaložba
avtor: Sergio Cabello
leto izida: 2010 (v Ljubljani)
natis: elektronsko gradivo
http://www.fmf.uni- lj.si/~cabello/gradiva/vajeracgeom.pdf
CIP - Kataložni zapis o publikaciji Narodna in univerzitetna knjiznica, Ljubljana
514.17(075.8)(076.1) 519.852(075.8)(076.1)
CABELLO, Sergio
Vaje iz racunske geometrije [Elektronski vir] / Sergio Cabello. - 1. izd. - El. knjiga. - V Ljubljani : samozal., 2010
Nacin dostopa (URL): http://www.fmf.uni-lj.si/~cabello/gradiva/vajeracgeom.pdf
ISBN 978-961-276-043-4
253228800
Kazalo
1	Osnovne naloge	4
2	Algoritmi pometanja	5
3	VeCkotniki in subdivizije	11
4	Konveksnost	16
5	Podatkovne strukture za toCke	22
6	DCEL, razporeditve in dualnost	24
7	Linearno programiranje	29
8	Voronojev diagram in Delaunayeva triangulacija	32
Naloge so grobo organizirane po temah, vendar je klasifikacija včasih težka. V vsaki nalogi lahko predpostavis smiseln splošen položaj, ki pa ga moras natančno opisati. Ko opises algoritem, moras vedno pokazati pravilnost in nadalje opisati in utemeljti časovno zahtevnost algoritma. Časovna zahtevnost se lahko nanasa na najslabsi primer (worst-case analysis) ali na pričakovani primer (average-case analysis). Dobro je, da vsaj za nekatere vaje napises psevdokodo.
Za studiranje priporočam knigo
M. de Berg, M. van Kreveld, M. Overmars, O. Sčhwarzkopf: Computational Geometry, Algorithms and Appličations. Springer.
Zahvala. Zahvaljujem se Mitji Trampusu za stevilne popravke. Seveda pa je avtor odgovoren za vse preostale napake.
1 Osnovne naloge
1.1.	Naj bo T(1) = O(1). Dokazi:
(a)	Ce je T (n) = O(n) + 2T (n/2), potem je T (n) = O(n log n).
(b)	Ce je T (n) = O(n) + T (n/2), potem je T (n) = O(n).
1.2.	Opisi algoritem, ki dobi seznam tock p1,p2,... ,pn v R2 in zbrise ponovljene tocke, torej vrne mnozico {pi,p2,... ,pn}. Algoritem mora imeti casovno zahtevnost O(n log n).
Opisi algoritem za isti problem v Rd. Koliko casa potrebuje?
1.3.	Podanih je n daljic v ravnini. Vemo, da so daljice robovi veckotnika, vendar niso nujno nasteti v "pravem" vrstnem redu. Opisi algoritem, ki rekonstruira veckotnik kot seznam nastetih oglisc v casu O(n log n).
1.4.	Za 3 tocke p = (px,py),q = (qx, qy), r = (rx, ry) v ravnini definiramo
	1	px	py
D(p, q, r) =	1	qx	qy
	1	rx	ry
Dokazi, daje D(p, q,r) > 0 natanko tedaj, ko je zaporedje p, q, r zasuk na levo. Dokazi, da je D(p, q, r) = 0 natanko tedaj, ko so p, q, r kolinearne. Dokazi, da je |D(p, q, r)| dvakrat ploscina trikotnika Apqr.
1.5.	Opisi algoritem, ki izracuna presecisca med podano premico in podano kroznico.
1.6.	Naj bo P mnozica n tock v ravnini. Predpostavimo naslednji splosni polozaj: nobene 3 tocke niso kolinearne. Opisi algoritem, ki skonstruira v casu O(n log n) veckotnik, ki ima mnozico P kot mnozico oglisc.
Pokazi primer mnozice tock P z naslednjo lastnostjo: obstaja eksponentno stevilo veckotnikov, ki imajo mnozico P kot mnozico oglisc. To je, obstajati mora najmanj 1.0000001|P 1 takih veckotnikov.
1.7.	Podani sta enako veliki mnozici tock R (rdec) in B (modri) v ravnini. Predpostavimo, da je R n B = 0 in da niso nobene 3 tocke kolinearne. Prirejanje M c R x B med R in B je disjunktno prirejanje, ce so daljice rb, (r, b) G M, paroma disjunktne. Glej sliko 1.1.
(a)	Naj bo M * prirejanje med R in B, ki je najkrajse (vsota dolzin daljic). Dokazi, da je M * disjunktno prirejanje.
(b)	Ali lahko uporabljamo (a) za algoritem, ki vrne disjunktno prirejanje.
1.8.	Podana sta mnozica tock P moci n in premica t v ravnini. Zanima nas najmanjsi krog Dmin, ki vsebuje P in ima svoje sredisce na premici t. Opisi algoritem, ki najde Dmin v polinomskem casu. (Cas O(n log n) je dosegljiv, ampak pretezek na zacetku predmeta.)
1.9.	Podana je mnozica n tock P v ravnini. Zanima nas, ali obstajata 2 unitarna kvadrata (obseg je 4), ki vsebujeta P in imata robove vzporedne z x-osjo ali z y-osjo.
^ J
X
Slika 1.1: Zgled za vajo 1.7.
Opisi algoritem, ki resuje ta problem v polinomskem času. Kakšne podatkovne strukture bi bile koristne za bolj učinkovit algoritem?
1.10.	Naj bo P mnoZica n točk v ravniti, in naj bo L mnoZica premic, ki grejo skozi 2 točki iz P. Opisi algoritem, ki vrne v času o(n2) premico iz L z največjim naklonom.
1.11.	Naj bo D krog polmera 1 v ravnini in naj bo P mnozica n točk v D.
(a)	Predpostavimo, da za vsak par p, q G P velja \pq\ > 5, kjer je 5 > 0 parameter. Dokazi zgornjo mejo za \P\, ki je tesna z O-notacijo. (Namig: uporabi argument s plosčino krogov.)
(b)	Predpostavimo, da za vsako točko p G P velja \{q G P \ \pq\ < 5}\ < 20. Dokazi tesno zgornjo mejo za \P\. (Namig: ali lahko uporabimo (a) 20 krat?)
2 Algoritmi pometanja
Za algoritme pometanja opisi vedno glavno idejo, strukturo stanja, dogodke (ter kako jih algoritem obravnava) in invarianto zanke.
2.1. Na slikah 2.2-2.4 so podane mnozice daljic S. Njihova presečisča bi radi poiskali z uporabo algoritma pometanja, ki si ga spoznal na predavanjih. Navedi seznam parov daljic {s, s'}, s, s' G S, za katere algoritem preveri, ali je s n s' prazen ali ne. Pari morajo v seznamu nastopati v istem vrstnem redu, kot jih algoritem preveri. Ce algoritem isti par daljic preveri večkrat, potem naj natančno tolikokrat nastopa tudi v seznamu.
Slika 2.2: Vaja 2.1.
k V
x
A V
x
2.2.	Naj bo S
krajišča: si = (0, 0)(20,10), s2 = (9,19)(9, 6), S3 = (2, 7)(14, 4), S4 = (3, 2)(15, 2), S5 = (5, 4)(8,10), s6 = (1,10)(16, 5). Za iskanje presečisč iz S uporabimo algoritem pometanja, ki ga smo opisali na predavanjih.
(a)	Koliko dogodkov je?
(b)	Na katerih dogodkih najdemo nova presečišča, ki bodo zdaj dogodki? (č) Opisi strukturo stanja po dogodku (0, 0) in pred dogodkom (8,10).
2.3.	Podana je mnoZiča paroma disjunktnih daljič S moči n. Vsaka daljiča iz S ima eno skrajno točko na premiči y = 0 in drugo skrajno točko na y = 1. Daljiče v S razdelijo prostor med y = 0 in y = 1 na kose. Podrobno opisi (psevdokoda) podatkovno strukturo, ki jo lahko konstruiramo v času O(n log n) in odgovori v času O(log n) na poizvedbe naslednjega tipa: katere daljiče definirajo kos, v katerem je poizvedbalna točka p(px,py),
0 <py < 1.
2.4.	Na predavanju smo spoznali algoritem pometanja, ki najde v času O((n + k) log n) pare daljič, ki se sekajo, kjer je k stevilo vrnjenih parov. Algoritem, ki ga smo opisali, porabi za delovanje O(n + k) prostora. Opisi spremembe v algoritmu, s katerimi bi algoritem porabil samo O(n) prostora. Torej algoritem vrne presečisča takoj, ko jih najde, in porabi samo O(n) dodatnega prostora.
2.5.	Podana je mnoziča premič L moči n v ravnini. Naj bo I mnoziča presečisč premič iz L. Opisi algoritem, ki v času O(n log n) vrne najmanjsi pravokotnik, ki vsebuje I in ima robove vzporedne koordinatnim osem. Glej sliko 2.5.
= {s1,s2,... ,s6} mnoziča daljič v ravnini. Daljiče imajo naslednja
Slika 2.5: Zgled za vajo 2.5.
2.6.	Naj bo S mnoziča n kroznič v ravnini. (Krozniča je krivulja, in sičer meja kroga.) Opisi output-sensitive algoritem pometanja, ki vrne presečisča med pari kroznič v času O((n + k) log n), kjer je k stevilo vrnjenih presečisč.
2.7.	Naj bo P mnoziča n točk v ravnini. Označimo x- oziroma y-koordinato točke p s px in py. Točka p G P je maksimalna, če ne obstaja druga točka q G P s lastnostmi px < qx in py < qy. Opisi algoritem, ki v času O(n log n) vrne podmnozičo maksimalnih točk.
2.8.	Naj bosta P in Q x-monotoni poti z n oziroma m oglisči. Predpostavimo, da niso nobena 3 oglisča kolinearna.
(a)	Dokazi, da je moč P n Q največ O(n + m).
(b)	Opisi algoritem, ki vrne P n Q v linearnem času.
2.9.	Naj bo S mnoziča n paroma disjunktnih daljič v ravnini in naj bo p točka, ki ni na nobeni daljiči iz S. Naj bo S (p) podmnoziča daljič iz S, ki so delno vidne iz p. To je, daljiča s G S je v S (p), če in samo če obstaja točka q G s z lastnostjo pq n s' = 0 za vsak s' G S \ {s}. Opi s i algoritem, ki vrne S(p). (Nasvet: algoritem pometanja lahko pometa z nečim, kar ni premiča ...)
2.10.	Naj bo M = {mi, m2,..., mn} mnoziča n modrih trikotnikov v ravnini in naj bo R = {r1, r2,..., rn} mnoz iča n rdečih trikotnikov v ravnini. Za parameter t G R označ imo z Nt navpično premičo {(x,y) G R2 | x = t} in z Dt diagonalno premičo {(x, y) G R2 | x + y = t}. Zanima nas naslednji optimizačijski problem:
0(M, R) := max |{m, G M | Nt n m^ = 0}| • |{r» G R | Dt n r, = 0}|
tER
Opi s i algoritem, ki vrne 0(M, R) v č asu O(n log n).
2.11.	Podana je mnoz iča P z n točkami v ravnini, dodatno pa se točki q, q' G P. Isčemo krog Dmin, ki vsebuje q, q', pa čim manjse stevilo točk mnoziče P.
(a)	Dokazi naslednjo trditev: če obstaja krog, ki vsebuje q, q' in se k točk iz P, potem obstaja tudi krog, ki ima q, q' na svojem robu in vsebuje največ k točk iz P.
(b)	Za podano točko p naj bo C (p) mnozica sredisč krogov, ki imajo q,q' na svojem robu in vsebujejo p. Kaksna je C (p)?
(c)	Opisi algoritem, ki vrne krog Dmin v času O(n log n).
2.12.	Naj bo S mnozica n intervalov na realni osi R. Predpostavimo naslednji splosni polozaj: vse skrajne točke intervalov so različne. Opisi algoritem, ki v času O(n log n) presteje elemente mnozice {(I, J) G S2 \ I C J or J c I}.
2.13.	Podana je mnozica S z n paroma disjunktnimi trikotniki v ravnini. Zelimo najti n — 1 daljic z naslednjimi lastnostmi:
•	Vsaka daljica povezuje točko na robu trikotnika s točko na robu nekega drugega trikotnika.
•	Notrajnosti daljic so paroma disjunktne in disjunktne s trikotniki.
•	Daljiče povezujejo vse trikotnike, to je, obstaja pot od poljubnega trikotnika do vsakega drugega trikotnika, ki gre samo po daljicah in trikotnikih.
Ideja je, da zelimo najti daljice, ki definirajo vpeto drevo vhodnih trikotnikov brez krizanja. Glej sliko 2.6 Opisi algoritem, ki resuje ta problem v času O(n log n).
Slika 2.6: Zgled za vajo 2.13.
2.14.	Naj bo S mnozica n premic in naj bo D krog v ravnini. Opisi algoritem, ki v času O(n log n) steje, koliko parov premic ima presečisče v notranji D. (Nasvet: kdaj se dve premiči sekata v notranji D?)
2.15.	Naj bo S mnozica n daljic v ravnini, ki niso nujno disjunktne, in naj bosta p, q točki v ravnini. Opisi algoritem, ki določi, ali obstaja točka x v ravnini, ki vidi p in q. Glej sliko 2.7.
2.16.	Naj bo M mnozica n modrih trikotnikov v ravnini, ki so paroma disjunktni. Naj bo R mnozica n rdečih trikotnikov v ravnini, ki so tudi paroma disjunktni. Naj bo X unija trikotnikov iz R. To je X = UreR r. Opisi algoritem pometanja, ki v času O(n log n) izračuna
{m G M \ m n X = 0}. Torej isčemo trikotnike iz M, ki so disjunktni z R. Glej sliko 2.8.
x, ki vidi p, r.
Slika 2.8: Zgled za vajo 2.16, pri čemer bi bil izhod {m3, m4}.
2.17.	Naj bo M = {T\,T2,..., Tn} mnoZica n trikotnikov v ravnini. Zanima nas naslednji optimizacijski problem.
0(M) := max |{T G M | li n Ti = 0 ali l2 n Ti = 0}| p.p. li,l2 sta navpični premici
razdalja med l1 in l2 je enaka 1
Opi s i algoritem, ki vrne 0(M) v č asu O(n log n).
2.18.	Naj bo P mnozica n točk v ravnini. Zanima nas naslednji optimizacijski problem.
0(P) := min ploščina(Ri) + ploččina(R2)
p.p. R1, R2 sta pravokotnika
Px < Qx za vse (Px,Py) G Ri, (Qx,Qy) G R2 P C Ri U R2
Glej sliko 2.9 za zgled. Opisi algoritem pometanja, ki vrne 0(P) v casu O(n log n).
2.19.	Naj bo R mnoz ica n rdec ih kvadratov v ravnini in naj bo M mnoz ica n modrih kvadratov v ravnini. Vsi kvadrati iz R in M imajo isto velikost in imajo robove vzporedne s koordinatnima osema. Kvadrati iz R so paroma disjunktni in kvadrati iz M so paroma disjunktni. Zanima nas mnozica
Pre(R, M) = {(r, m) G R x M | r n m = 0}.
Glej sliko 2.10.
Ri
R2
• •
Slika 2.9: Točke P in pravokotnika R1,R2, ki definirata dopustno rešitev pri vaji 2.18.
(a)	Dokaži, da je moč množice Pre(R, M) največ O(n).
(b)	Opiši algoritem pometanja, ki vrne Pre(R,M) v času O(n log n).
R = {a, b, c}
M = {a',b',c'}
Pre(R, M) = {(a, a'), (a, b'), (a, c'), (b, b'), (c, b'), (c, c')} c
Slika 2.10: Zgled za vajo 2.19.
c
2.20. Vertikalna razdalja dv(s, s') med daljicama s, s' je
dv (s, s') = min{|py - p'y | | (a,py) G s, (a,p'y) G s' ,a G R}.
Povedano drugače, vertikalna razdalja med s, s' je dolžina najkrajše navpične daljice, ki seka s in s'. Ce s in s' nimata točk z isto x-koordinato, potem je dv(s, s') nedefinirana (ali +rc>).
Naj bo S množiča n daljič v ravnini. Daljiče iz S so paroma disjunktne. Opisi output-sensitive algoritem, ki vrne mnozičo
{(s, s') G S2 | dv (s, s') < 1}.
2.21.	Podana je mnoziča P = {pi,p2,p3,...,pn} n točk v ravnini. Označimo z R najmanjsi pravokotnik, ki ima straniče vzporedne s koordinatnimi osmi in vsebuje P. Opisi algoritem pometanja, ki v času O(n log n) najde kvadrat velikosti 1, ki je vsebovan v R, vendar sam ne vsebuje nobene točke iz P; če pa tak kvadrat ne obstaja, naj algoritem to javi. Straniče kvadrata morajo biti vzporedne koordinatnim osem.
2.22.	Imamo 42 enako velikih pravokotnih rezin sira; vsaka rezina ima n kvadratnih lukenj velikosti 1, vzporednih straničam rezine. Rezine zlozimo na sendvič eno na drugo tako, da so njihovi robovi skladni in da natanko prekrijejo kruh. Polozaji lukenj glede na
globalen koordinatni sistem so pri tem znani. Na vrh sendviča namazemo majonezo. Ali obstaja kaksna točka, v kateri imajo vse rezine luknjo in lahko zato majoneza pričurlja do kruha? Opi s i postopek, ki najde odgovor v času O(n log n).
2.23. Podana je smer v v ravnini ter m disjunktnih konveksnih večkotnikov s skupno n ogli s č i. Opis i algoritem, ki v času O(n log n) določi vse večkotnike, ki so vsaj delno vidni z neskončne razdalje v smeri v. Večkotnik P je delno viden, če obstaja poltrak v smeri v s kraji s čem na robu P, ki ne seka nobenega drugega ve čkotnika.
3 Večkotniki in subdivizije
Ko nič ne rečemo, so večkotniki podani kot seznam oglišč, naštetih v smeri urinega kazalca. Predpostaviš lahko, daje seznama implementiran s poljem (array) ali pa s kazalci - kar ti pri reševanju bolj ustreza.
3.1. V slikah 3.11-3.12 narisi diagonale, ki jih izračuna algoritem za triangulačijo, ki ga si spoznal na predavanjih.
3.2. Podan je mnogokotnik z naslednjimi oglisči:
p[0] = (a 4), p[4] = (4,6), p [8] = (14,10),
p[1] = (6, 0), p[5] = (7, 5), p[9] = (15, 0),
p[2] = (3, 0), p[6] = (10, 5), p[10] = (12, 4),
p[3] = (2, 9), p[7] = (13, 6), p[11] = (8, 0),
pri čemer velja a G [5,11]. Pomagaj si s sliko 3.13.
Triangulačijo mnogokotnika izračunamo z uporabo algoritma, ki si ga spoznal na predavanjih. Poisči 3 vrednosti parametra a (točke mnogokotnika morajo biti v splosnem polo zaju) pri katerih vrne algoritem razli čne triangulačije. Opazi, da lahko algoritem isto triangulačijo izračuna na različne načine. Za te 3 izbrane vrednosti parametra a narisi diagonale, ki jih algoritem izračuna. Naris i tri ločene slike!
3.3.	Večkotnik na sliki 3.14 zelimo triangulirati z algoritmom s predavanj. Narisi maksimalno območje, za katerega velja: če premikamo točko p znotraj tega območja, bo rezultat algoritma za triangulacijo ostal nespremenjen, vključno z vrstnim redom, v katerem algoritem vstavlja diagonale.
3.4.	Podan je večkotnik kot seznam ogli sč, vendar ni znano, ali so oglisč a nasteta v smeri urnega kazalca ali nasprotni smeri. Opi s i algoritem, ki v linearnem času ugotovi smer.
3.5.	Kaj je narobe v naslednjem dokazu obstoja diagonale v večkotniku?
Z uporabo zasuka lahko predpostavimo, da imajo ogli s ča večkotnika razli čne x-koordinate. Naj bo p ogli sče več kotnika, ki ima najmanj so x-koordinato. Torej je p konveksno oglisče večkotnika. Naj bo p- oglisče pred p v seznamu oglisč večkotnika, in naj bo p+ oglisče po p. Ce je daljica p_p+ diagonala, smo konč ali. Sicer naj bo q ogli s če več kotnika, ki je v trikotniku A(p,p_,p+) in minimizira razdaljo od p, pa ni p. Potem je daljica pq diagonala.
3.6.	Zapi s i psevdokodo algoritma, ki izračuna 3-barvanje vhodne triangulacije večkotnika v linearnem času.
3.7.	Opi s i algoritem, ki vrne diagonalo vhodnega več kotnika v linearnem č asu.
3.8.	Dokazi ali ovrz i:
(a)	Naj bo P x-monoton večkotnik in naj bo T triangulacija večkotnika P. Potem je dualen graf od T pot.
(b)	Naj bo P x-monoton večkotnik. Potem za P obstaja triangulačijo, katere dualen graf je pot.
(c)	Za vsako drevo D obstaja večkotnik s triangulacijo, ki ima D kot dualen graf.
(d)	Za vsako drevo D, ki ima največjo stopnjo 3, obstaja konveksen večkotnik s trian-gulačijo, ki ima D kot dualen graf.
(e)	Kaksno lastnost drevesa lahko dodamo v (d), da je trditev pravilna.
(f)	Obstajajo večkotniki, ki imajo samo eno triangulacijo.
(g)	Obstajajo večkotniki, ki so monotoni za samo eno smer.
(h)	Vsako konveksno ogli sče x-monotonega večkotnika, različno od x-skrajnih točk, je vogal u sesa.
(i)	Ali je (h) pravilen za mountain polygons, to je, za x-monoton večkotnik, pri katerem je spodnja poligonalna pot daljiča.
(j) Vsak večkotnik, ki ima sodo stevilo robov, lahko z diagonalami razdelimo na četve-rokotnike.
(k) Zbodno Stevilo triangulacije več kotnika je največje Stevilo diagonal, ki jih lahko preseka poljubna premica v ravnini. Ali obtajajo večkotniki, pri katerih ima vsaka triangulacija zbodno stevilo reda Q(n)?
3.9.	Naj bo P večkotnik in naj bo S mnoZica točk. Opisi algoritem pometanja, ki v času O(n log n) vrne S n P, kjer je n velikost vhoda (stevilo oglisč P plus |S|).
3.10.	Večkotnik P je zvezden, če obstaja točka p G P, ki vidi cel večkotnik. Podana sta zvezden večkotnik P in točka p, ki vidi cel P. Opisi algoritem, ki vrne v linearnem času triangulačijo ve čkotnika P.
3.11.	Podani so večkotnik P in točki s, t G P. Opi s i algoritem, ki vrne najkraj so pot, vsebovano v P, od s do t. (Namig: razmisli prej, kako izgleda najkrajsa pot.)
3.12.	Naj bo D poligonalna domena s n ogli sč in h luknjami. Koliko trikotnikov ima triangulacija domene D? Podrobno dokazi pravilnost odgovora. Glej sliko 3.15.
Slika 3.15: Zgled za vajo 3.12, pri čemer ima domena n = 11 oglisč in h = 2 lukenj.
3.13. Naj bosta P in Q x-monotona mnogokotnika s skupno n ogli s č i. Glej sliko 3.16.
(a)	Dokaz i, da ima P n Q največ O(n) povezanih komponent.
(b)	Opi s i algoritem, ki presteje, koliko povezanih komponent ima P n Q.
(b) Ce P je x-monoton in Q y-monoton (in ne nujno tudi x-monoton), koliko povezanih komponent ima lahko P n Q? Zakaj?
Slika 3.16: Zgled za vajo 3.13, pri čemer ima presek 3 povezane komponente.
3.14. Podana sta večkotnik P z n ali manj oglisč in mnozica S daljič moči manjsi ali enako n. Vemo, da so daljice v S paroma disjunktne. Opis i algoritem pometanja, ki v času O(n log n) vrne daljice iz S, ki so vsebovane v P.
Slika 3.17: Pravokotna piramida.
3.15.	Opis i ucinkovit algoritem za naslednji problem: podana sta veckotnik P in notranja tocka p G P, nas pa zanima konstrukcija obmocja znotraj veckotnika P, ki je vidno iz tocke p.
3.16.	Veckotnik je pravokoten, ce je vsak rob vodoraven ali navpicen. Pravokotna piramida je pravokoten veckotnik, ki je x-monoton in pri katerem je spodnja pot daljica, zgornja pot pa sestavljena iz dveh y-monotonih poti. Glej sliko 3.17. Predpostavimo, da noben par robov ni kolinearen.
(a)	Dokazi naslednjo trditev: vsako pravokotno piramido lahko razdelimo z diagonalami na konveksne cetverokotnike.
(b)	Opisi algoritem, ki v linearnem c asu najde diagonale iz tocke (a).
3.17.	Podana sta n-kotnik P ter tocka po, ki sovpada z enim od P-jevih ogli sc. Opisi algoritem, ki v c asu O(n log n) najde tak s no triangulacijo vec kotnika P, ki maksimizira s tevilo diagonal z enim od krajisc v p0.
3.18.	Veckotnik P je viden z roba e, ce vidi vsaka tocka q G P kaks no tocko na e. Glej sliko 3.18. Podan je veckotnik P in rob e, s katerega je P viden. Opisi algoritem, ki v linearnem casu vrne triangulacijo vec kotnika P. Razloz i vlogo vidnosti z roba.
3.19. Cilj te vaje je algoritem, ki najde diagonalo, ki razdeli vec kotnik na dva kosa, ki sta velika.
(a)	Naj bo T drevo z m vozli sc ami in najvecjo stopnjo 3. Pokaz i, da obstaja povezava e tako, da ima vsako drevo v T — e najvec m/3 vozlisc.
(b)	Naj bo P podan veckotnik z n oglisc ami. Pokaz i, da obstaja diagonala, ki deli P na dva veckotnika, ki imata najvec 2n/3 + 2 oglisc.
Slika 3.18: Zgled za vajo 3.18, pri cemer je veckotnik viden iz roba e.
(c) Opisi algoritem, ki najde diagonalo točke (b) v času O(n log n).
3.20. Podani so konveksni disjunktni večkotniki Pi, P2,..., Pk v ravnini. Vsi več kotniki skupaj imajo n ogli s č. Opisi algoritem, ki v č asu O(n log n) najde navpično premico i z naslednjo lastnostjo: plosčina dela P1 U ■ ■ ■ U Pk levo od premice i in plosčina dela P1 U ■ ■ ■ U Pk desno od premice i sta enaki. Glej sliko 3.19.
Ali je v tvojem algoritmu pomembno, da so podani večkotniki konveksni in disjunktni?
3.21.	Naj bo P večkotnik v ravnini z n oglisč. Opi s i algoritem, ki v času O(n log n) najde navpično premico i z naslednjo lastnostjo: plosč ina dela več kotnika levo od premice i in plosčina dela večkotnika desno od premice i sta enaki.
3.22.	(Tezje) Opisi algoritem, ki v linearnem času določi, ali obstaja smer, v kateri je vhodni več kotnik monoton.
4 Konveksnost
4.1.	Mnozica desetih točk P = (a, b,..., j} je podana na slikah 4.20 in 4.21. Uporabljamo prirastni algoritem za računanje zgornje lupine točk P. Navedi trojke točk (X, Y, Z) G P3, za katere algoritem preveri, ali je zaporedje X, Y, Z zasuk na desno. V seznamu morajo biti trojke v istem vrstnem redu, kot jih algoritem preveri.
Povej tudi seznam trojk pri Grahamovem algoritmu.
4.2.	Naj bosta A,B c Rd konveksni mnozici. Ugotovi, ali X konveksna mnoz ica, ko je
•	X = A \ B,
•	X = A U B,
•	X = A + B = (a + b | a G A, b G B},
•	X = A x B.
4.3. Določi konveksno lupino mnoz ice ((0,0)} U ((1, t) G R2 | t G (0,1)} in nato se mnoz ice {(x, y) G R2 | x2 + y2 < 1 ali (x — 3)2 + y2 < 1}.
Slika 3.19: Zgled za vajo 3.20.
											
											
	--<	c r			•	-i	S				*
P '	h		-i	>e			-i	i			
											
L				4	f						
Slika 4.20: Za vajo 4.1. d	g
		*	•						*	»	
											
	'b		-i	>e						-i	>h
P" " ■											
		c									
	*										
L							*				
Slika 4.21: Za vajo 4.1.
d
j
a
x
j
a
x
4.4.	Za splošen n opiši primer množice n točk, v katerem vsaj eno njegovo oglišče nastopa v O(n) trojicah, ki jih preveri prirastni algoritem za izračun konveksne lupine.
4.5.	Videli smo Grahamov algoritem, ki je sestavljen iz dveh korakov: (1) iz podanih točk na poseben način zgradimo večkotnik M in se potem (2) sprehajamo po M in ga spreminjamo, dokler ne dobimo CH(P). Dokazi, da samo korak (2) ni dovolj za izračun konveksne lupine večkotnika: najdi tak večkotnik N, da ne dobimo CH (N), če na njem direktno uporabimo korak (2) Grahamovega algoritma.
4.6.	Naj bo P mnoziča točk v ravnini. Za vsako točko p G P definiramo
cell(p) = {x G R2 | d(x,p) < d(x,pr) za vsak p' G P},
kjer je d(■, ■) evklidska razdalja. Pokazi, da je cell(p) konveksna mnoziča za vsako točko p G P.
4.7.	Opisi podatkovno strukturo za hranjenje konveksnega večkotnika P, ki omogoča v času O(log n) ugotoviti, ali je poizvedbena točka vsebovana v P. Konstrukčija podatkovne strukture mora biti izvedena v linearnem času.
4.8.	Naj bo P končna mnoziča točk v ravnini. Dokazi naslednjo trditev: CH (P) je konveksna mnoziča, ki vsebuje P in ima najmanjso plosčino.
4.9. Podana je končna množica točk P v ravnini. Naj bo M najkrajši večkotnik, ki vsebuje P.
(a)	Dokazi, da je M konveksen večkotnik.
(b)	Dokazi, da je M C Q za poljubno konveksno množico Q, ki vsebuje P.
(c)	Dokazi, da je C H (P) = M.
4.10.	Konveksen večkotnik M je podan kot seznam oglisč, nastetih v smeri urinega kazalca. Opisi algoritem, ki uredi oglisča od M po ^-koordinatah v linearnem času. Ali se da tvoj algoritem ustrezno dopolniti, da bo (se vedno v linearnem času) deloval za poljuben večkotnik M?
4.11.	Naj bo P mnozica oglisč večkotnika M. Ali je res, da C H (P) = C H (M)?
4.12.	Podana sta dva konveksna večkotnika P, Q. Opisi algoritem, ki izračuna C H (P UQ) v linearnem času. (Ce ne gre drugače, lahko predpostavis, da sta P in Q disjunktna.)
4.13.	Podani sta mnozica točk L na levi od premice x = 0 in mnozica točk D na desni od x = 0. Mnozici L in D imata isto moč n. Predpostavimo, da niso nobene 3 točke iz D U L na isti premici. Prirejanje M c L x D med L in D je disjunktno prirejanje, če so daljice Id, (l, d) G M paroma disjunktne. Glej sliko 4.22. Opisi algoritem, ki vrne disjunktno prirejanje M v času O(n2 log n).
x = 0
x = 0
Vhod	Primer izhoda
Slika 4.22: Zgled za vajo 4.13.
4.14.	Opazujemo problem v prvem delu vaje 1.2. Pokazi, da je spodnja meja računske zahtevnosti problema Q(n log n).
4.15.	Podan je konveksen večkotnik P kot polje (array) oglisč p[1,..., n].
(a)	Opisi algoritem, ki v času O(log n) vrne najvisje oglisče iz P.
(b)	Opisi algoritem, ki v času O (log n) vrne obe tangenti od podane točke p G R2 \ P. Glej levo stran slike 4.23.
(c)	Opisi algoritem, ki v času O (log n) vrne presečisče med P in podano premico £. Glej desno stran slike 4.23.
Slika 4.23: Zgled za vajo 4.15.
(d) Opisi algoritem, ki v casu O (log n) vrne tocko od P, ki je najbljZje podani premici i.
4.16.	Podani sta mnoZ ica toCk P in toCka q v ravnini. Opi S i algoritem, ki v linearnem Casu odloČi, ali je q v notranji CH(P).
4.17.	Premer A(P) mnoZice točk P je A(P) = max{d(p, q) | p, q G P}, kjer je d(-, ■) evklidska razdalja. Naj bo P koncna mnoZica n tock.
•	DokaZi, da je A(P) = A(Q), kjer je Q mnoZica oglisc iz CH(P).
•	DokaZ i, da se pojavi vrednost A(P) najvec O(n)-krat v seZnamu d(p, q),p, q G P.
•	Opisi algoritem, ki iZracuna A(P) v casu O(n log n).
4.18.	Naj bodo P1, P2,..., Pt mnoZ ice tock v Rd, in Ki = CH(Pi) (i = 1, 2,..., t) njihove konveksne ovojnice. Definirajmo se
t t P = U Pi in K = U Ki.
i=1 i=1
Ugotovi, ali je CH (P) = CH (K).
4.19.	Naj bo P veckotnik, in naj bo
K (P) = {p G P | p vidi cel veckotnik P}. PokaZi, da je K(P) konveksna mnoZica.
4.20.	Naj bo P mnoZica tock v R3. Definiramo
U (P) = {x G R3 | d(x,p) < 1 Za vsak p G P}, kjer je d(-, ■) evklidska raZdalja. PokaZi, da je U (P) konveksna mnoZica.
4.21.	Naj bo P = {p1,... ,pn} mnoZica tock v R2. CH (P) smo definirali kot mnoZico tock x G R2, ki Zadovolji
nn
x = E ^ipi, E ^i = 1, ^1, . . . , ^n > 0.
i=1 i=1
Kaj se zgodi, če odstranimo pogoj A1,..., An > 0? Vedno?
4.22.	Naj bo P mnoziča točk v R2. CH*(P) definiramo kot mno zičo
(x G R2 | x = Ap + (1 — A)q, A G [0,1], p, q G P}. Navedi primer, ki pokaze CH(P) = CH*(P). Ali je CH(P) = CH*(CH*(P))?
4.23.	Naj bo P kon č na mnoz ica toč k v ravnini in naj bo M konveksen več kotnik, ki vsebuje P in ima oglisča iz P. Dokazi, da je M = CH(P).
4.24.	Naj bosta P, Q konveksna večkotnika. Opisi algoritem, ki vrne P n Q v linearnem času.
4.25.	Podana sta dva konveksna večkotnika M, M' kot seznama ogli sč. Opis i algoritem, ki v linearnem času odloči, ali velja M c M'.
4.26.	Opazujemo problem v vaji 1.6. Pokazi, da je spodnja meja računske zahtevnosti problema Q(n log n).
4.27.	Opazujemo problem v vaji 1.10. Pokaz i, daje spodnja meja računske zahtevnosti problema Q(n log n).
4.28.	Podana sta krog D ter konveksen n-kotnik P, ki je v celoti vsebovan v D. Isčemo toč ko x G D\P (torej znotraj kroga, vendar zunaj več kotnika), iz katere je vidno največje mozno stevilo P-jevih oglisč. S psevdokodo opisi algoritem, ki najde toč ko x v času O(n).
4.29.	Podan je konveksen n-kotnik P. I s čemo diagonalo d, ki razdeli P na dva kosa, katerih razlika plo s čin je po absolutni vrednosti najmanj sa mo zna. Zapi si psevdokodo za algoritem, ki najde taks no diagonalo v linearnem času.
4.30.	Naj bo L = (i1,i2,... ,in) mnozica n premic v ravnini v splosnem poloz aju (nobeni 2 premici nista vzporedni in presek poljubnih 3 premic je prazen). Naj bo I mnoz ica preseči sč premic iz L, to je I = (i n ij | i G L, i j G L, i = j}. Glej sliko 4.24. Opisi (s psevdokodo) algoritem, ki vrne konveksno lupino CH (!) v času O(n log n).
4.31.	Podan je konveksen večkotnik P. Naj bosta E(P) in V (P) mnoz ica robov oziroma oglisč večkotnika P. Naj bo T mnozica trikotnikov, ki imajo oglisča v V (P) in najmanj en rob v E (P). Opi s i algoritem, ki v linearnem č asu vrne trikotnik v T z največjo plos č ino.
4.32.	Podana je mnoz ica P z n točkami v ravnini. Zanima nas algoritem, ki najde pravokotnik, ki vsebuje P in ima najmanjso plosčino. Glej sliko 4.25.
(a)	Pokazi, da pravokotnik vsebuje P natanko tedaj, ko vsebuje CH (P).
(b)	Pokazi, da je dovolj, če isčemo samo med pravokotniki, ki imajo en rob istolezen z enim od robov konveksne lupine C H (P). Nasvet: trigonometrija.
(č) Pokazi, da v času O(n log n) lahko razdelimo S1 na intervale I1,I2,... z naslednjo lastnostjo: skrajni točki v smeri u in —u sta isti za vsak u G I j.
(d) Opisi algoritem, ki v času O(n log n) vrne pravokotnik, ki vsebuje P in ima najmanj so plosčino
Slika 4.25: Pravokotnik, ki vsebuje mnozičo točk P.
4.33. Podana je mnoziča n točk P v ravnini. Naj bo M-1 večkotnik, ki vsebuje vse točke iz P razen ene točke (lahko izberemo, katera točka ni vključena) in ima najmanjsi obseg. Glej sliko 4.26.
Primer vhoda	Izhod
Slika 4.26: Zgled za vajo 4.33.
Opisi algoritem, ki najde M-1 v času O(nh log n), kjer je h stevilo skrajnih točk v P. (V času O(n2 log n) je lazje.)
(Tezje) Predpostavimo, da imamo naslednji podprogram: vhod je n disjunktnih trikotnikov in n točk in podprogram vrne v času O(n log n), katere točke so v vsakem trikotniku. (Tak podprogram lahko implementiramo z uporabo algoritma pometanja.) Dokazi, da lahko najdemo M-1 v času O(n log n).
4.34.	Naj bo T (n) s tevilo razli č nih triangulačij konveksnega več kotnika z n ogli s č i. Opi s i rekurzivno enačbo za T (n).
(Tezje) Kaks na je res itev rekurzivne enačbe?
4.35.	Zbodno .število triangulačije večkotnika je največje stevilo diagonal, ki jih lahko preseka poljubna premiča v ravnini. Opi si algoritem, ki za vhodni konveksni večkotnik z n ogli s či konstruira triangulačijo z zbodnim s tevilom O(logn).
4.36.	Zanimajo nas konveksne lupine mnoz ič n krogov.
(a) Predpostavi, da imajo vsi krogi isto velikost. Dokaz i, da se lahko pojavi vsak krog najve č enkrat na robu konveksne lupine.
(b)	Dokazi, da se lahko posamezen krog v konveksni ovojnici pojavi n — 1 krat, če imamo kroge različnih velikosti.
(c)	(Tezje) Dokazi, da ima konveksna lupina krogov različnih velikosti zahtevnost O(n), to je, ima O(n) daljic in kroznih lokov.
(d)	(Tezje) Opisi algoritem, ki v času O(n log n) skonstruira konveksno ovojnico n krogov različnih velikosti.
5 Podatkovne strukture za točke
V tem razdelku imajo vsi pravokotniki in kvadrati robove vzporedne s koordinatnimi osmi.
5.1.	Podana je mnozica n točk P v ravnini. Poiskati zelimo dinamično podatkovno strukturo, ki hrani podmnozico Q C P. Na začetku je Q = P. Podatkovna struktura mora podpirati naslednje operacije v času O(log2 n):
•	Brisanje točke p G Q iz Q.
•	Vstavljanje točke p G P \ Q v Q.
•	Stetje |Q n R| za vhodni pravokotnik R (poizvedba).
5.2.	Podana je mnoz ica n točk P v Rd, kjer je d konstanta. Poiskati zelimo podatkovno strukturo, ki hrani P in isče delne zadetke. Poizvedba za delne zadetke ima kot vhod vrednosti nekaterih koordinat, podatkovna struktura pa mora vrniti točke iz P, ki se v podanih koordinatah ujemajo s poizvedbo.
(a)	Razlozi, kako lahko delne zadetke v R2 najde 2-dimenzionalno območno drevo. Kaksen čas je potreben za odgovor?
(b)	Opisi podatkovno strukturo, ki uporablja linearno mnogo prostora in najde delne zadetke v č asu O(logn + k). Ne pozabi, da lahko porabimo O(d2dn) prostora, ker je d konstanta.
5.3.	Naj bo H mnozica največ n vodoravnih daljic in naj bo V mnoz ica največ n navpičnih daljic. Cilj vaje je algoritem, ki v času O(n log n) določi stevilo parov iz H x V, ki se sekajo. Glej sliko 5.27.
(a)	Naj bo P mnoz ica n toč k v R. Pokaz i, da obstaja dinamična podatkovna struktura, ki shrani podmnoz ico Q C P in v času O(log n) lahko dela naslednje operacije: vstavljanje elementa iz P \ Q, brisanje elementa iz Q, stetje točk Q n I za podan interval I.
(b)	Opi s i algoritem, ki v času O(n log n) določi stevilo parov iz H x V, ki se sekajo.
5.4.	Naj bo P mnozica n točk v ravnini. Opisi podatkovno strukturo za hranjenje P z naslednjimi lastnostmi:
•	čas gradnje podatkovne strukture je O(n log n);
Slika 5.27: Zgled Za vajo 5.3, pri cemer mora vrniti algoritem 26.
•	Za pravokotnik R (poiZvedba) vrne podatkovna struktura v casu O(log2 n) najmanjsi pravokotnik, ki vsebuje vse tocke iZ P n R.
5.5.	Naj bo R mnoZica trikotnikov v ravnini, ki so doloceni z neenacbami tipa x > a, y > b, x + y < c, a, b, c G R. Opi s i podatkovno strukturo, ki hrani P in odgovarja na naslednje poizvedbe: za podan T G R vrne T n P. Cas gradnje podatkovne strukture mora biti O(nlog2 n) in c as odgovarjanja na posamezno poizvedbo mora biti O(|T n P| + log3 n). Nasvet: uporabljaj vec kot 2 dimenZiji.
5.6.	DokaZ i, daje analiza casa odgovora v kd-drevesu tesna. To je, opis i mnoZ ico tock P in pravokotnik R tako, da potrebuje kd-drevo ^(v7^) casa Za odlocanje, ali je P n Q = 0.
5.7.	Koliko casa potrebuje kd-drevo, ce ga vprasamo za tocke v obmocju [a,a] x [b,b]? In koliko potrebuje obmoc no drevo?
5.8.	Naj bo Q mnoZica enako velikih kvadratov v R2. Opisi ucinkovito podatkovno strukturo, ki hrani Q in hitro odgovori na poiZvedbe naslednje oblike: kateri kvadrati iZ Q vsebujejo podano vhodno tocko.
5.9.	Podana je mnoZica n tock P na premici R. Opi s i podatkovno strukturo z lastnostmi:
•	cas gradnje je O(n log n);
•	podatkovna struktura porabi O(n) prostora;
•	za podani interval I vrne podatkovna struktura nakljucno tocko iz P n I v casu O(logn). To je, vsaka tocka iz P n I ima isto verjetnost, da je v odgovoru.
Opis i podobno strukturo za R2 z malo vecjo porabo prostora in casa.
5.10.	Podana je mnoZica n tock P v R. Vsaka tocka p G P ima teZo wp G R. Zelimo podatkovno strukturo za hraniti P, ki ga lahko konstruiramo v c asu O(n log n) in ki vrne za vhodni interval R (poizvedba) tocke P n R urejene po teZi. Brez teZ ave lahko dobimo c asovno zahtevnost O(k log n + log n) za posamezno poizvedbo. Brez teZ ave lahko dobimo casovno zahtevnost O(k log n + log n) za posamezno poizvedbo. DokaZ i, da se lahko to naredi v casu O(k log log n + log n) za posamezno poizvedbo. Nasvet: najprej dokaZi, da
lahko dobimo urejen seznam stevil iz t urejenih seznamov stevil v času O(m log t), kjer je m s tevilo elementov v vseh seznamih skupaj.
Mozen je tudi čas O(k + log n) za posamezno poizvedbo, vendar rabi hude ideje.
5.11.	Opi s i psevdokodo za vstavljenje in brisanje toč ke iz kd-drevesa. Ni nujno paziti na poravnavanje drevesa.
5.12.	kd-drevesa lahko uporabljamo tudi za iskanje točk, ki so v drugih tipih območij, na primer v krogih ali trikotnikih.
(a)	Zapi s i psevdokodo za iskanje točk, ki so v vhodnem trikotniku.
(b)	Dokaz i, da je čas odgovora v najslabej sem primeru linearen. (č) Naredi (a) in (b) se za kroge.
5.13. Videli smo, da 2-dimenzionalna območna drevesa porabijo O(n log n) prostora. Porabo zelimo zmanjsjati s povečanjem časa odgovorjanja na poizvedbe.
(a)	Predpostavimo, da imajo 'associated' strukture samo vozlisča na sodnih nivojih. Kak sna je adaptačija algoritma za pravilno odgovarjanje na poizvedbe.
(b)	Koliko prostora porabi ideja iz točke (a)?
(c)	Predpostavimo, da imajo 'associated' strukture samo vozlisča na nivojih 0, |_ j log nj, L2 log nj,..., kjer je j > 2 konstanta. Koliko prostora porabi taksna podatkovna struktura in koliko traja odgovor na posamezno poizvedbo?
5.14.	Podana je mnoz ica n točk P v ravnini. Vsaka točka p G P ima tezo wp G R. Za vsako podmnozico Q C P definiramo w(Q) =	wp in w'(Q) = maxp€Q wp. Opisi podatkovno strukturo za hrambo P, ki vrne w(P n R) in w'(Pn R) za vhodni pravokotnik R (poizvedba) v času O(log2 n). Podatkovna struktura sme porabiti O(n log n) prostora, in mora biti konstruirana v času O(n log n).
5.15.	Podana je mnozica n intervalov S na premici R. Opisi algoritem, ki v času O(n log n) najde moč mnoz ice ((!, J) G S2 | ! c J ali J c !}.
5.16.	Danih je n intervalov na R, ! = ([a1, b1], [a2, b2],..., [an, bn]}. V času O(n) pred-procesiraj podatke, da bos znal nato v č asu O(1) za poljuben dani interval [p, q] povedati, v koliko intervalih iz ! je vsebovan. Opisi oba postopka, tako predprocesiranje kot odgovarjanje na poizvedbe.
6 DCEL, razporeditve in dualnost
6.1. Naj bo H mnozica n premic v ravnini, ki se sekajo v isti točki p, in naj bo H' mnoz ica m premic v ravnini, ki se sekajo v drugi točki p' = p. Premice iz H ne potekajo skozi p', premice iz H' pa ne potekajo skozi p.
(a)	Koliko ogli s č , robov in lic ima razporeditev A(H)?
(b)	Koliko oglisč, robov in lic ima razporeditev A(H U H')?
Slika 6.28: Delna slika za n = 4 v vaji 6.3.
(c) Naj bo R mnoZica n ravnin v R3. Vsaka ravnina iz R vsebuje točko (0,0,0) in nobena trojka ravnin se ne seka na premici. Koliko ogliSč , robov, lic in celic ima razporeditev A(R)?
6.2. Naj bosta Lh mnoZica n vodoravnih premic v ravnini in Lv mnoZ ica n navpičnih premic v ravnini. Naj bo Lp mnoZica n premic v ravnini, ki se sekajo v isti točki p. Nobena premica iz Lp ni vodoravna ali navpič na in nobena izmed vodoravnih ali navpičnih premic ne vsebuje točke p. Poleg tega se nobene tri premice £h G Lh,£v G Lv ,£p G Lp ne sekajo v isti točki.
(a)	Koliko oglisč, robov in lic ima razporeditev A(Lh U Lv U Lp)?
(b)	Opisite, kako izgledajo toč ke, dualne premicam Lh U Lp.
6.3.	Za vsak i naj bo £i premica {(x,y) G R2 | x = i}, naj bo vi premica {(x,y) G R2 | y = i} in naj bo di premica {(x, y) G R2 | y = x + i}. Za naravno stevilo n, naj bo
L = {4,4, . . . , £n} U {vi, v2, . . . , vn} U {di, d2, . . . , dn}.
Glej sliko 6.28. Koliko oglisč, robov in lic ima razporeditev A(L)?
6.4.	Naj bo S = {C1,... ,Cn} mnoz ica n kroz nic polmera 1. Predpostavimo, da so v splosnem poloz aju: nobene 3 kroznice se ne sekajo v isti točki in nobeni 2 kroz nici se ne dotikata. Lice razporeditve A(S) je maksimalna povezana mnoz ica v R2 \ (Ui Ci). Dokaz i naslednje trditve.
(a)	Ce seka vsaka kroz nica iz S največ k kroz nic iz S, potem ima A(S) največ O(n(k+1)) lic.
(b)	Ce za vsako toč ko p velja {Ci | Ci vsebuje p}| < k, potem ima A(S) največ O(nk) lic.
6.5. Podan je DCEL povezane subdivzije v ravnini. Vsako lice subdivizije, ki ni zunanjo lice, je konveksno. Opi si (učinkovito) psevdokodo za naslednje naloge.
(a)	Podano je liče f . Navedi oglisča liča f .
(b)	Podano je liče f. Določi, ali je f zunanje liče.
(č)	Podano je oglisče v. Navedi liča, ki imajo v na robu.
(d)	Podano je oglisče v. Najdi oglisče DCELa, ki ima najmanj so x-koordinato.
(e)	Podano je liče f. Navedi liča, ki imajo vsaj eno oglisče skupno s f.
(f)	Podana je daljiča pq, ki seka robove DCELa, in liče f, ki vsebuje p. Predpostavimo, da pq ne vsebuje oglisč DCELa. Az uriraj DCEL, da bo imel novo subdivizijo s pq. (Glej sliko 6.30.)
6.6.	Kaks naje mnoz iča premič, ki so dualne točkam trikotnika Apqr?
6.7.	Naj bo P mnoz iča n toč k v ravnini. Točka x G R2, ne nujno v P, je osrednja tocka za P, če ima naslednjo lastnost: vsaka polravnina, ki vsebuje x, vsebuje vsaj n/3 točk iz P.
•	Kaj to pomeni v dualnem prostoru?
•	Opisi algoritem, ki najde osrednjo točko, če obstaja.
6.8.	Naj bo S podana mnoziča n daljič v ravnini.
(a)	Opisi algoritem, ki v času O(n2) odloči, ali obstaja premiča, ki seka vsako daljičo v S.
(b)	Opisi algoritem, ki vrne premičo, ki seka največje stevilo daljič v S.
6.9.	Naj bo P mnoziča n točk v ravnini in naj bo w G P točka. Za vsako premičo t naj bo 0(t) = maxpeP d(p,t), kjer je d(p,t) razdalja med p in t. Opi s i algoritem, ki vrne premičo t*, ki vsebuje w in maksimizira 0(t).
6.10.	Naj bo L mnoz iča n premič in naj bo P mnoz iča n točk v ravnini. Zanima nas, ali obstajata točka p G P in premiča t G L tako, da je p G t. Opisi algoritem, ki resuje ta problem grobo v č asu O(n3/2). (Namig: naredimo skupine, ki vsebujejo y/n premič.)
Kako hitro lahko resujemo ta problem za n premič in k točk?
6.11.	Naj bo P mnoz iča n toč k v ravini. Opi s i podatkovno strukturo, ki ga lahko konstruiramo v času O(n2) in v času O (log n) določi, koliko točk iz P so nad vhodno premičo (poizvedba).
6.12.	Naj bosta P in Q mnoz iča toč k v ravnini. P in Q imata isto moč . Predpostavimo, da je P n Q = 0 in da nobene 3 točke iz P U Q niso kolinearne. Za P in Q velja naslednja pogoja:
Slika 6.29: Mnoz iča kroz nič S polmera 1 in dve liči razporeditve A(S).
•	vsaka točka iz P je ogli s če konveksne lupine CH (P U Q);
•	vsaka točka iz Q je ogli sče konveksne lupine CH(Q).
Opisi, kako izgledajo in kaksne lastnosti imajo premice dualne točkam P U Q.
6.13.	Podana je mnoz ica ravnin H v splos nem poloz aju v R3: ne obstajajo 4 ravnine, ki se sekajo v isti točki. Celica razporeditve A(H) je maksimalna povezana podmnozica v R3 \ U H. Lica, robovi, oglisča razporeditve A(H) so lica, robovi, oglisča razporeditve A({h' n h | h' G H}) na vsakem h G H.
Koliko celic, lic, robov, oglisč ima A(H)?
6.14.	Naj bo L mnozica premic v ravnini. Ogli sče v razporeditve A(L) je na nivoju 0, če nobena premica iz L ni pod v. Ce je vsako ogli sče iz A(L) na nivoju 0, kaks na je L?
6.15.	Podana sta subdivizija ravnine v DCEL in lice f te subdivizije. Predpostavimo, da je subdivizija taka, da je vsako liče definirano s čiklom brez ponovljenih povezav. Zelimo zbrisati vse povezave, ki definirajo f, to je D = {e | e je povezava na robu lica f}. Predpostavimo, da subdivizija ostane povezana, ko zbrisemo D. Glej sliko 6.31. Zapisi psevdokodo, ki zbri se D in a zurira DCEL. Kak sna je časovna zahtevnost algoritma?
6.16.	Opis i drugo definicijo dualnosti, kjer je vodoravna razdalja invariantna. Dokaz i, da ne obstaja dualnost med točkami in premicami, pri kateri sta tako vodoravna kot navpična razdalja invariantni.
6.17.	Kak s naje povezava med diagramom normal konveksnega več kotnika P in zgornjo ali spodnjo ovojnico premic, ki so dualne oglisčem večkotnika P?
Slika 6.32: Primer mnoZice D v vaji 6.24.
6.18.	Naj bodo P1, P2,..., Pk konveksni veckotniki v ravnini. Ce obstaja premica, ki seka vse veckotnike P^ ..., Pk, kaksna je situacija v dualnem prostoru?
6.19.	Naj bosta R, B mnoZici rdecih oziroma modrih tock v ravnini. Opisi algoritem, ki vrne polravnino, ki vsebuje vse modre to cke in cim manj rde cih to ck.
6.20.	Dana je mnoZ ica n modrih in n rdecih tock v ravnini. Opi s i algoritem, ki v casu O(n2) ugotovi, ali obstaja pas sirine 1, ki vsebuje vse modre in nobene rdece tocke.
6.21.	Zbodno s tevilo triangulacije veckotnika je najvecje stevilo diagonal, ki jih seka poljubna premica v ravnini. Opisi algoritem, ki izracuna zbodno stevilo podane triangulacije vec kotnika v c asu O(n2), kjer je n s tevilo ogli s c vec kotnika.
6.22.	Pravimo, daje veckotnik k-konveksen, ce poljubna premica njegov rob seka najvec k-krat. 2-konveksnost je torej ekvivalentna "navadni" konveksnosti. Opisi algoritem s c asovno zahtevnostjo O(n2), ki za podani n-kotnik P in s tevilo k ugotovi, ali je P k-konveksen.
6.23.	Naj bo P mnoZ ica n tock v ravnini. Za premico i v ravnini, ki ni navpicna, naj bo 0(i) = max{dvert(p,i) | p G P}, kjer je dvert(p,i) navpicna razdalja med toč ko p in premico i. Naj bo i* premica, ki minimizira vrednost 0(i). Opi s i algoritem, ki v casu O(n log n) vrne premico i*.
6.24.	Naj bo D mnoZ ica n pravokotnikov, ki so translacije pravokotnika [0, 3] x [0,1]. Ni nujno, da so pravokotniki disjunktni. Glej sliko 6.32 za primer. Zanima nas, ali obstaja premica s pozitivnim naklonom, ki seka vsak pravokotnik iz D.
(a)	Kak sen je problem v dualnem prostoru?
(b)	Opisi algoritem, ki res uje tak problem v linearnem casu.
(c)	Opisi algoritem, ki v linearnem casu odloci, ali obstaja premica z naklonom med 10 in 15, ki seka vsak pravokotnik iz D.
(d)	Opisi algoritem, ki v linearnem casu odloci, ali obstaja premica, ki seka vsak pra-vokotnik iz D. Pazi, naklon je zdaj povsem neomejen.
Naklon premice {(x,y) G R2 | y = ax + b} definiramo za potrebe te naloge kar kot njen smerni koeficient a.
6.25.	Naj bo R mnoZica n rdecih daljic v ravnini, in naj bo M mnoZica n modrih daljic v ravnini. Premica i je akrobatska za R in M, ce seka CH (R) in velja
|{s G R | i n s = 0}| = |{s G M | i n s = 0}|.
Opisi algoritem, ki v času O(n2) odloči, ali obstaja akrobatska premica za R in M. 6.26. Naj bo S mnoz ica n toč k v ravnini.
(a)	Opisi podatkovno strukturo, ki lahko v času O (log n) odloči, ali je neka točka iz P nad podano premico £. (Premica £ nikoli ni navpična.)
(b)	Opisi podatkovno strukturo, ki lahko v času O(log2 n) odloči, ali je neka točka iz P nad podano daljico e. (Točka p je nad daljico e, ko je p nad premico, ki vsebuje e, in navpična premica skozi p seka e.)
(Namig: Za (b) lahko uporabis večnivojsko podatkovno strukturo, kjer je prvi nivo za x-koordinate, drugi nivo pa za ugotavljanje poloz aja glede na premico, ki vsebuje e.)
7 Linearno programiranje
7.1.	Večkotnik P je zvezden, če obstaja točka p G P, ki vidi cel večkotnik. Opi s i algoritem, ki v linearnem času odloči, ali je podan večkotnik P zvezden. Ce je podan večkotnik P zvezden, ali lahko najdemo v linearnem času točko, ki vidi cel P? Pa mnoz ico točk, ki vidijo cel večkotnik?
7.2.	Naj bo S podana mnozica navpičnih daljic v ravnini. Opisi algoritem, ki v linearnem času odloči, ali obstaja premica, ki seka vsako daljico v S.
7.3.	Naj bodo c1,...,cn avtomobili, ki se premikajo po premici R. Polozaj avta ci v č asu t je podan s formulo xi(t), ki je afina, t.j. oblike xi(t) = ait + bi; parametra ai, bi sta znana. Diameter avtomobilov A(t) v času t je definiran kot
A(t) := max{x1(t), x2(t),..., xn(t)} — min{x1(t), x2(t),..., xn(t)}.
Opisi algoritem, ki najde minimalni diameter, ko je t G [0,1000]. Opis i algoritem, ki najde maksimalni diameter, ko je t G [0,1000]. Kdaj obstaja maksimalni diameter, ko je t > 0?
7.4.	Naj bo S mnoz ica daljic v ravnini. Opi s i algoritem, ki v linearnem času odloči, ali obstaja vertikalna daljica dolzine 1, ki seka vsako daljico iz S.
7.5.	Naj bosta R in B mnozici rdečih oziroma modrih točk v ravnini. Opisi algoritme, ki resujejo naslednje probleme v linearnem času:
(a)	Najti premico, če obstaja, ki loči R in B.
(b)	(tezje) Najti krog, če obstaja, ki ima R noter in B zunaj.
7.6.	Naj bo P monotona poligonalna pot, ki ima n oglisč . Naj bosta a in b minimalna in maksimalna x-koordinata ogli sč poti P. Pot P si lahko predstavljamo kot relief terena; glej sliko 7.33. Stolp je navpič na daljica, ki ima bazo v poti P. Stolp vidi pot P, če je vsaka točka poti P vidna z vrha stolpa.
(a)	Opi s i algoritem, ki najde stolp, ki vidi P in minimizira y-koordinato vrha.
(b)	Opisi algoritem, ki najde najkrajsi stolp, ki vidi pot P.
7.7. Naj bo P konveksen večkotnik, ki je podan s tabelo oglisč p[1,... ,n], nastetih v smeri urinega kazalča.
(a)	Opisi algoritem, ki odloči, ali obstaja krog polmera r znotraj večkotnika P.
(b)	Opi s i algoritem, ki najde največji krog znotraj večkotnika P. (Glej sliko 7.34.)
7.8.	Obroček v ravnini je mnoziča točk, ki imajo razdaljo med a in b od neke točke (sredisče). Glej sliko 7.35. Podana je mnoziča točk P v ravnini. Opisi algoritem, ki najde v linearnem času obro ček, ki vsebuje P in ima najmanj so plo s čino.
7.9.	Naj bo P mnoz iča točk v ravnini in naj bo q G P točka v ravnini.
(a)	Z uporabo linearnega programiranja opisi algoritem, ki v linearnem času odloči, ali je toč ka q znotraj C H (P).
(b)	Opisi algoritem, ki v linearnem času določi interval I z naslednjo lastnostjo: t G I natanko tedaj, ko je točka (t, 0) znotraj CH (P).
7.10.	Podane so konveksni večkotniki P1,P2,...,Pk v ravnini. Vsi več kotniki skupaj imajo n oglisč. Opi s i algoritem, ki v linearnem času odloči, ali obstaja navpična daljiča dol z ine 1, ki je znotraj vsakega ve č kotnika.
7.11.	Zivimo na omejenem intervalu I = [a, b] C R. Na intervalu I je n mest, ki jih označimo M1}M2,... ,Mn. Mesto Mi je na polozaju pi G I in ima parameter wi > 0,
Slika 7.35: Obroček.
ki meri, kako pomembno je mesto. Večja vrednost Wj pomeni, da je mesto Mj bolj pomembno.
Isčemo prostor za novo bolni s nico, ki seveda mora biti znotraj intervala I. Ce postavimo novo bolnisnico na polozaj x G I, potem lahko definiramo razdaljo od mesta Mj do bolnis nice kot Wj ■ |x — pj|. Zanima nas poloz aj bolni s nice, ki minimizira razdaljo do najbolj oddaljenega mesta. Na primer, recimo da je I = [0,4], mesto Mi je na poloz aju p1 = 0 s parametrom w1 = 3, mesto M2 pa je na poloz aju p2 = 3 s parametrom w2 = 1. Ce postavimo bolnisnico na polozaj x = 1, je razdalja od M1 enaka 3 in razdalja od M2 enaka 2. V tem poloz aju je M1 bolj oddaljen od bolni s nice kot M2.
Opisi algoritem, ki najde najboljsi polozaj nove bolnisnice v času O(n).
7.12.	V ravnini lezita dva konveksna večkotnika z nepraznim presekom. Opi s i algoritem, ki v linearnem času izra čuna najmanj so razdaljo, za katero moramo premakniti P v podani smeri v, da bosta P in Q disjunktna.
7.13.	Naj bo M konveksen sedemkotnik v ravnini z ogli s č i p1;p2,... ,p7, nastetimi v smeri urinega kazalca. nastetimi v smeri urinega kazalca. Translacija večkotnika M za vektor (tx,ty) je mnoz ica točk {(x + + ty) | (x,y) G M}. Za a G R, a > 0, z Ma označimo sedemkotnik, ki ga dobimo iz M z raztegom ravnine za parameter a. Torej je Ma = {(a ■ x, a ■ y) | (x, y) G M}.
Naj bo Q mnoz ica n toč k v ravnini.
(a)	Opi s i algoritem, ki v linearnem času odloči, ali obstaja translacija večkotnika M, ki vsebuje Q.
(b)	Opisi algoritem, ki v linearnem času poi sče najmanjsi a, za katerega obstaja neka translacija večkotnika Ma, ki vsebuje Q.
7.14.	Po noč nem nebu se premika n kometov. Astronom Arne bi jih rad posnel s svojim fotoaparatom, in sicer s čim večjo povečavo. Ce nekoliko poenostavimo, lahko nebo predstavimo z ravnino, komete s premočrtno premikajočimi se toč kami, kos neba, ki ga zajame fotoaparat, pa s pravokotnikom s stranicami v razmerju 4:3. Velikost pravokotnika je odvisna od povečave, in to lahko Arne poljubno spreminja. Ravnino neba opremimo s koordinatnim sistemom tako, da je pravokotnik fotoaparata poravnan s koordinatnimi osmi; stojalo aparatu dopusča poljubno premikanje po ravnini neba, ne pa tudi sukanja. V trenutku, ko Arne začne opazovati nebo, je i-ti komet na poloz aju (xi; y) in se premika s hitrostjo (vx,i,vy,i) enot na sekundo. Ob katerem času ima Arne priloznost narediti
sliko vseh kometov hkrati z največjo možno povečavo? Opisi postopek, ki najde odgovor v casu O(n).
8 Voronojev diagram in Delaunayeva triangulacija 8.1. V sliki 8.36 vrisi Delaunayevo triangulacijo podane množice točk.
Slika 8.36: Za vajo 8.1 Levo: točke in eno povezavo Delaunayeve triangulacije. Desno: Podatke
8.2.	Konstruiraj Voronojev diagram tock (0,0), (3,2), (1, 5), (4,4), (5, 8), (6,1) glede na razdaljo Li. Zapisi koordinate tock, ki so pomembne v diagramu.
8.3.	Konstruiraj Voronojev diagram tock (0,1), (2, 2), (4, 5), (6,3), (1,9) glede na razdaljo L^,. Zapisi koordinate tock, ki so pomembne v diagramu.
8.4.	Mnozica sedmih tock P = {A, B, C, D, E, F, G} je vrisana na sliki 8.37. Na sliki je za vsak par tock X, Y G P, X = Y, narisana in ustrezno oznacena tudi simetrala daljice XY. Navedi povezave Delaunayeve triangulacije tock P.
8.5.	Za i = 1,..., 100 izberi koordinate tocke pi G R2 na tak nacin, da sta v Delaunayevi triangulaciji mnozice {pi,p2,... ,pioo} najmanj 2 tocki stopnje 99. Tocke morajo biti v splosnem polozaju: nobene tri tocke niso kolinearne in nobene stiri tocke niso kocirkularne. Natancno utemelji, da ima tvoja izbrana mnozica tock zelene lastnosti.
8.6.	Naj bo P mnozica n tock v ravnini. Najti zelimo najbljzjo tocko qp G P za vsako tocko p G P, to je tocko pq, ki zadovolji |pqp| = min{|pq| | q G P \ {p}}. Opisi algoritem, ki vrne qp za vsako p G P v casu O(n log n).
8.7.	Naj bo P mnozica n tock v ravnini. Naj bo K (P) poln evklidski graf na P; to je, P je mnozica vozlisc grafa K (P) in za vsak par p, q G P obstaja povezava pq s tezo |pq|. Naj bo T minimalno vpeto drevo grafa K (P). Dokazi, da je T podgraf Delaunyeve triangulacije mnozice P in da lahko izracunamo T v casu O(n log n).
8.8.	Naj bo P mnozica tock v ravnini. Opisi algoritem, ki v O(n log n) casu vrne najvecji krog D, ki ima svoje sredisce v CH (P) in ne vsebuje nobene tocke iz P.
Kaj se zgodi, ce odstranimo pogoj, da mora biti sredisce kroga v CH (P)?
AD AC AE CE BD AF BE	AG	BF
Slika 8.37: Za vajo 8.4.
8.9.	Naj bo M mnoz iča n modrih točk v ravnini in naj bo R mnoz iča n rdečih točk v ravnini. Opi s i algoritem, ki v č asu O(n log n) izrač una
min{d(m, r) | m G M,r G R},
pri čemer je d(■) evklidska razdalja.
8.10.	Naj bo P mnoziča n točk v ravnini, ki jih vidimo kot "ovire". Naj bo D(x) krog polmera 1 s sredisčem v točki x G R2. Naj bosta s, t točki v R2 z lastnostjo P n D(s) = P n D(t) = 0. Opi s i algoritem, ki v času O(n log n) odloč i, ali obstaja zvezna krivulja x(t) z lastnostmi: x(0) = s in x(1) = t ter D(x(t)) n P = 0 za vsak t G [0,1]. Manj formalno, zanima nas, ali obstaja premik za krog polmera 1 od poloz aja s do poloz aja t, pri katerem se ne dotaknemo to čk iz P. Nasvet: Voronojev diagram lahko pomaga.
8.11.	Naj bo P mnoz iča točk {pi(i/n, 0,0) | i = 1.. .n}U {qj (0,j/n, 1)i = 1.. .n} v R3. Dokazi, da je Q(n2) kombinatorična zahtevnost Voronojevega diagrama mnoziče P.
8.12.	Podan je Voronojev diagram Vor(P) brez mnoziče točk P, ki ga je definiral. Glej sliko 8.38. Ali lahko najdemo P v linearnem času?
8.13.	Naj bo P mnoziča n točk v ravnini. Zanima nas najoddajenejši Voronojev diagram: Za vsako toč ko p G P naj bo
cel(p) = {x G R2 | d(p, x) > d(q, x) za vsako q G P \ {p}}.
(a) Ali je cel (p) konveksna mnoz iča? In v Rd?
Slika 8.38: Zgled za vajo 8.12. Kje pa je P?
(b)	Dokazi, da je cel (p) = 0 natanko tedaj je p skrajna točka iz CH (P).
(c)	Naj bo E mnoz ica robov diagrama, to je, točke v ravnini, ki so v cel(p) in cel (p'), p = p'. Dokazi, da E ne vsebuje sklenjene krivulje, to je, E je po strukturi drevo.
(d)	Dokazi spodnjo mejo Q(n log n) za časovno zahtevnost računanja najoddaljenejsega Voronojevega diagrama.
(e)	Opisi algoritem, ki izračuna najoddaljenejsi Voronojev diagram v č asu O(n log n).
8.14.	Naj bo P mnoz ica točk v ravnini. Zanima nas 2-Voronojev diagram Vor2(P). Za vsak par p, q G P naj bo
ce1({p, q}) = {x G R2 | d(x,p), d(x, q) < d(x, r) za vsako r G P \ {p, q}}.
2-Voronojev diagram Vor2(P) je mnoz ica celic ce1({p,q}), ki niso prazne. Kaks ne lastnosti imajo celice ce1({p, q}) G Vor2(P)? So povezane ali konveksne? Opisi kvadratičen algoritem, ki konstruira Vor2(P).
8.15.	Spomni se na metriko L1 v R2, kjer je razdalja med točkama (x,y) in (x',y') definirana kot |x — x'| + |y — y'|.
(a)	Ali so celice Voronojevega diagrama pod metriko L1 konveksne?
(b)	Ali so povezane?
(c)	Ali je kombinatorič na zahtevnost Voronojevega diagrama pod metriko L1 linearna?
(d)	Konstruiraj Voronojev diagram točk (0, 0), (1, 2), (5, 5), (6, 5), (0, 9) pod metriko L1.
(e)	Opisi algoritem, ki konstruira Voronojev diagram pod metriko L1.
8.16.	Naj bo P mnozica n točk v ravnini. Koliko trikotnikov ima vsaka triangulacija točk P? (Namig: potreboval bos se en parameter.)
8.17.	Naj bo P mnozica točk v ravnini. Njena najkrajša triangulacija je tista, ki min-imizira vsoto dolzine robov. Dokazi, da najkraj sa triangulacija ni nujno Delaunayeva triangulačija.
8.18.	Naj bo P = {p1 ,p2,...pn} mnozica n točk v ravnini. Predpostavimo naslednji splosni polozaj: če je {pi,pj} = {pi',p/}, potem velja d(pi,pj) = d(pi',pj'), kjer je d(-, ■) evklidska razdalja. Najmansja razdalja dmin v P je
dmin = min{d(pj,pj) | pi = p j }.
Drugo najmanj so razdaljo d2.min v P definiramo kot
d2 .min — min ({d(pi,pj) | pi = pj} \ {dmin}) •
Opi s i algoritem, ki v času O(n log n) vrne drugo najmanj so razdaljo d2.min.
8.19.	Naj bo P mnoz ica n točk v ravnini. Gabrielov graf G(P) za P ima P kot mnoz ico vozli s č in vključuje povezavo med točk p, q iz P natanko tedaj, ko krog s premerom pq ne vsebuje nobene toč ke iz P \ {p, q}.
(a)	Pokaz i, da je graf G(P) podgraf Delaunayeve triangulacije za P.
(b)	Pokaz i, da je pq povezava v grafu G(P) natanko tedaj, ko imata lici Voronojevega diagrama za p in q skupni rob e in daljica pq seka e.
(c)	Opi s i algoritem, ki vrne G(P) v č asu O(n log n).
(d)	Dokaz i, da porabi izračunanje Gabrielova grafa najmanj Q(n log n) časa.
8.20.	Naj bo P mnoz ica n toč k v ravnini in naj bo q G P dodatna toč ka znotraj CH (P). Opisi algoritem, ki v času O(n log n) vrne največji krog D, ki pokrije q, vendar v notranjosti ne vsebuje nobene točke iz P. (Točke iz P lahko so na robu kroga.)
8.21.	Naj bo P mnoz ica n toč k v splo s nem poloz aju v ravnini. V č asu O(n log n) poi sč i najmanjsi krog, ki ima na svojem robu natanko tri točke iz P, v strogi notranjosti pa natanko eno točko s P.
8.22.	Naj bo D mnozica n krogov polmera 1 v ravnini. Opisi podatkovno strukturo, ki hrani D in omogoča poizvedbe naslednje oblike: za podano točko p odloči, ali v D obstaja krog, ki vsebuje p. Cas gradnje podatkovne strukture mora biti O(n log n). Podatkovna struktura mora odgovoriti na poizvedbo v času O (log10 n).
Opisi drugo podatkovno strukturo za enak problem, kjer je D mnoz ica n pravokot-nikov, ki so translacije pravokotnika [0,3] x [0,1].
8.23.	Naj bo P mno ziča n točk v ravnini. Isčemo podatkovno strukturo, ki hrani P in omogo ča poizvedbe naslednje oblike: za podan krog D odlo či, ali je mno ziča P n D prazna ali ne.
(a)	Opisi taksno podatkovno strukturo, ki jo lahko konstruiramo v času O(n log n) in v č asu O(log n) odgovori na posamezno poizvedbo, če uporabljamo evklidsko razdaljo.
(b)	Opisi podatkovno strukturo, ki jo lahko konstruiramo v času O(n log n) in v času O(log2 n) odgovori na posamezno poizvedbo, če uporabljamo metriko L1.
Pazi: (zaprt) krog D je mno ziča to čk, ki so od sredi s ča oddaljene za najve č polmer kroga; pri tem je razdalja bodisi evklidska bodisi L1.