Geometrie computationala −suport de curs

Mihai-Sorin Stupariu

Sem. I, 2016-2017

Cuprins

1 Preliminarii 31.1 Concepte de algebra liniara, geometrie afina si euclidiana . . . . 31.2 Raportul unor puncte coliniare . . . . . . . . . . . . . . . . . . . 31.3 Coordonate carteziene si coordonate polare . . . . . . . . . . . . 51.4 Testul de orientare . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 6

2 Acoperiri convexe 82.1 Generalitati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Algoritmi lenti (naivi) . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Algoritmi ”clasici” . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1 Algoritmi incrementali: Graham’s scan, Jarvis’ march . . 112.4 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 13

3 Triangulari 143.1 Triangularea poligoanelor. Problema galeriei de arta . . . . . . . 143.2 Triangularea unei multimi arbitrare de puncte . . . . . . . . . . . 163.3 Triangulari unghiular optime . . . . . . . . . . . . . . . . . . . . 173.4 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 19

4 Intersectii 204.1 Intersectia segmentelor (generalitati) . . . . . . . . . . . . . . . . 204.2 Metoda liniei de baleiere . . . . . . . . . . . . . . . . . . . . . . . 214.3 Alte rezultate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.4 Suprapunerea straturilor tematice . . . . . . . . . . . . . . . . . . 234.5 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 25

5 Elemente de programare liniara 265.1 Motivatie: turnarea pieselor ın matrite . . . . . . . . . . . . . . . 265.2 Intersectii de semiplane . . . . . . . . . . . . . . . . . . . . . . . 275.3 Programare liniara . . . . . . . . . . . . . . . . . . . . . . . . . . 285.4 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 295.5 Anexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1

6 Probleme de localizare 326.1 Localizarea punctelor − Harti trapezoidale . . . . . . . . . . . . 326.2 Aplicatie: miscarea unui robot-punct . . . . . . . . . . . . . . . . 366.3 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 37

7 Diagrame Voronoi 387.1 Generalitati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.2 Proprietati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.3 Diagrame Voronoi si triangulari Delaunay . . . . . . . . . . . . . 397.4 Un algoritm eficient . . . . . . . . . . . . . . . . . . . . . . . . . 407.5 Exercitii, probleme, aplicatii . . . . . . . . . . . . . . . . . . . . . 41

Bibliografie 42

A Proiecte 43

2

Capitolul 1

Preliminarii

1.1 Concepte de algebra liniara, geometrie afinasi euclidiana

Notiuni de algebra liniara: spatiu vectorial, vector, combinatie liniara, liniar(in)dependenta, sistem de generatori, baza, reper, dimensiune a unui spatiu vec-torial, componentele unui vector ıntr-un reper, matrice de trecere ıntre repere,repere orientate la fel (opus), reper drept (stramb), produs scalar, norma unuivector, versorul unui vector nenul, spatiu vectorial euclidian, vectori ortogonali,baza ortonormata, reper ortonormat.

Notiuni de geometrie afina: vectorul determinat de doua puncte, combinatieafina, afin (in)dependenta, acoperirea afina a unei multimi de puncte, dreaptadeterminata de doua puncte distincte, reper cartezian, coordonatele unui punctıntr-un reper cartezian, sistem de axe asociat unui reper cartezian din Rn, ra-portul a trei puncte coliniare (detalii ın sectiunea 1.2), segmentul determinatde doua puncte, multime convexa, ınchiderea (ınfasuratoarea) convexa a uneimultimi, aplicatie afina (exemple: translatie, omotetie, proiectie, simetrie).

Notiuni de geometrie euclidiana: distanta dintre doua puncte, reper carte-zian ortonormat, izometrie, proiectie centrala.

Detalii pot fi gasite ın [6], [8], [13] [14].

1.2 Raportul unor puncte coliniare

Lema 1.1 Fie A si B doua puncte distincte ın Rn. Pentru orice punct P ∈ AB,

P 6= B exista un unic scalar r ∈ R\{−1} astfel ca−−→AP= r

−−→PB. Reciproc, fiecarui

scalar r ∈ R \ {−1}, ıi corespunde un unic punct P ∈ AB.

Definitia 1.2 Scalarul r definit ın lema 1.1 se numeste raportul punctelorA,B, P (sau raportul ın care punctul P ımparte segmentul [AB]) si estenotat cu r(A,P,B).

Observatia 1.3 In calcularea raportului, ordinea punctelor este esentiala. Mo-dul ın care este definita aceasta notiune (mai precis ordinea ın care sunt consi-derate punctele) difera de la autor la autor.

3

O x

y

Combinatii liniare

αv + βw (α, β ∈ R)

v

w

v + w

A 12A+ 1

2B

B

O x

y

Combinatii afine

λA+ µB (λ, µ ∈ R si λ+ µ = 1)

Figura 1.1: Vectori si puncte: combinatii liniare si combinatii afine

Exemplul 1.4 (i) In R3 consideram punctele A = (1, 2, 3), B = (2, 1,−1),C = (0, 3, 7). Atunci punctele A,B,C sunt coliniare si avem r(A,C,B) = − 1

2 ,r(B,C,A) = −2, r(C,A,B) = 1, r(C,B,A) = −2.

(ii) Fie A,B doua puncte din Rn si M = 12A+ 1

2B. Atunci r(A,M,B) = 1,r(M,A,B) = − 1

2 .

Propozitia 1.5 Fie A,B, P trei puncte coliniare, cu P 6= B. Atunci:

(i) P = 1r+1A+ r

r+1B, unde r = r(A,P,B);

(ii) P = (1− α)A+ αB daca si numai daca r(A,P,B) = α1−α ;

(iii) P = αα+βA+ β

α+βB daca si numai daca r(A,P,B) = βα .

Observatia 1.6 Fie P ∈ AB \ {A,B}. Atunci:

(i) r(A,P,B) > 0 daca si numai daca P ∈ (AB);

(ii) r(B,P,A) = 1r(A,P,B) .

4

1.3 Coordonate carteziene si coordonate polare

Coordonate carteziene (x, y) si coordonate polare (ρ, θ) (pentru puncte din pla-nul R2 pentru care relatiile au sens), Figura 1.2:{

x = ρ cos θy = ρ sin θ

{ρ =

√x2 + y2

θ = arctg yx

O x

y

P (x, y)

ρ

θ

Figura 1.2: Punctul P are coordonatele carteziene (x, y) si coordonatele polare(ρ, θ).

1.4 Testul de orientare

• Fie vectorii v = (v1, v2, v3), w = (w1, w2, w3) ∈ R3.Produsul vectorial v×w se calculeaza dezvoltand determinantul for-mal

v × w =

∣∣∣∣∣∣v1 w1 e1v2 w2 e2v3 w3 e3

∣∣∣∣∣∣• Notatie Fie P = (p1, p2), Q = (q1, q2) doua puncte distincte din planul

R2, fie R = (r1, r2) un punct arbitrar. Notam

∆(P,Q,R) =

∣∣∣∣∣∣1 1 1p1 q1 r1p2 q2 r2

∣∣∣∣∣∣ .• Lema. Fie P,Q,R puncte din R2 ' {x ∈ R3|x3 = 0}. Atunci

−→PQ ×

−→PR= (0, 0,∆(P,Q,R)).

Propozitia 1.7 Fie P = (p1, p2), Q = (q1, q2) doua puncte distincte din planulR2, fie R = (r1, r2) un punct arbitrar si

∆(P,Q,R) =

∣∣∣∣∣∣1 1 1p1 q1 r1p2 q2 r2

∣∣∣∣∣∣ .5

O x

y

P

Q

R1

R2

Figura 1.3: Pozitia relativa a doua puncte fata de un vector / o muchie orientata

Atunci R este situat:(i) pe dreapta PQ ⇔ ∆(P,Q,R) = 0 (”ecuatia dreptei”);

(ii) ”ın dreapta” segmentului orientat−→PQ ⇔ ∆(P,Q,R) < 0;

(iii) ”ın stanga” segmentului orientat−→PQ ⇔ ∆(P,Q,R) > 0.

Observatia 1.8 Testul de orientare se bazeaza pe calculul unui polinom degradul II (∆(P,Q,R)).

Aplicatii.

• daca un punct este ın dreapta / stanga unei muchii orientate;

• natura unui viraj ın parcurgerea unei linii poligonale (la dreapta / lastanga);

• natura unui poligon (convex / concav);

• daca doua puncte sunt de o parte si de alta a unui segment / a unei drepte.

1.5 Exercitii, probleme, aplicatii

Exercitiul 1.9 Calculati rapoartele r(A,P,B), r(B,P,A), r(P,A,B) (stabilitimai ıntai daca punctele sunt coliniare), pentru: (i) A = (3, 3), B = (2, 4), C =(5, 1); (ii) A = (1, 4,−2), P = (2, 3,−1), B = (4, 1, 1).

Exercitiul 1.10 Determinati α, β astfel ca punctele A,P,B din planul R2, cuA = (6, 2), P = (α, β), B = (2,−2), sa fie coliniare si r(A,P,B) = 2.

Exercitiul 1.11 Determinati coordonatele carteziene ale punctului M de coor-donate polare ρ = 6; θ = π

6 , respectiv cooronatele polare ale punctului N(−4, 4).

Exercitiul 1.12 Ordonati punctele A = (2, 0), B = (3, 2), C = (4, 2), D =(0,−4), E = (−3, 1), F = (0, 5), G = (−1,−1), H = (0, 4) (i) folosind coordo-nate carteziene; (ii) folosind coordonate polare.

Exercitiul 1.13 Calculati produsul vectorial v×w pentru vectorii v = (1,−1, 0),w = (−2, 1, 3).

6

Exercitiul 1.14 Fie v, w ∈ R3 doi vectori necoliniari. Folosind produsul vec-torial, construiti o baza ortonormata {b1, b2} a planului π generat de vectorii vsi w, astfel ca b1 sa fie coliniar cu v.

Exercitiul 1.15 Fie P = (2, 2), Q = (4, 4). Stabiliti, folosind testul de orien-tare, pozitia relativa a punctelor R1 = (8, 8), R2 = (6, 0), R3 = (−2,−1) fata

de muchia orientata−−→PQ. Care este pozitia acelorasi puncte fata de muchia

orientata−−→QP ?

Exercitiul 1.16 Dati exemplu de puncte coplanare P,Q,R1, R2 din R3, nesi-tuate ıntr-un plan de coordonate, astfel ca R1 si R2 sa fie de o parte si de altaa segmentului [PQ].

Exercitiul 1.17 Fie MNP un triunghi cu varfurile M = (xM , yM ), N =(xN , yN ), P = (xP , yP ) si fie δ o dreapta de ecuatie ax+ by+ c = 0. Stabiliti sijustificati care este complexitatea algebrica a calculelor pentru:

a) a stabili daca dreapta intersecteaza laturile triunghiului;b) a stabili daca dreapta trece prin centrul de greutate al triunghiului.

Exercitiul 1.18 Fie ABC un triunghi cu varfurile A = (xA, yA), B = (xB , yB),C = (xC , yC) si fie P = (xP , yP ), Q = (xQ, yQ) alte doua puncte, distincte, dinplan. Care este complexitatea algebrica a calculelor pentru:

a) a stabili daca dreapta PQ este paralela cu una dintre laturile triunghiuluiABC;

b) a stabili daca punctul P coincide cu centrul cercului circumscris triun-ghiului ABC.

7

Capitolul 2

Acoperiri convexe

2.1 Generalitati

Conceptul de multime convexa:

Definitia 2.1 (i) Pentru P,Q ∈ Rm, segmentul [PQ] este multimea combinatiilorconvexe dintre P si Q:

[PQ] = {(1− t)P + tQ|t ∈ [0, 1]} = {αP + βQ|α, β ∈ [0, 1], α+ β = 1}.

(ii) O multime M ⊂ Rm este convexa daca oricare ar fi P,Q ∈ M, seg-mentul [PQ] este inclus ın M.

Problematizare:Multimile finite cu cel putin doua elemente nu sunt convexe −→ necesara aco-perirea convexa.

Acoperire convexa a unei multimi finite P: caracterizari echivalente

− Cea mai ”mica” (ın sensul incluziunii) multime convexa care contine P.

− Intersectia tuturor multimilor convexe care contin P.

− Multimea tuturor combinatiilor convexe ale punctelor din P. O combinatieconvexa a punctelor P1, P2, . . . , Pn este un punct P de forma

P = α1P1 + . . .+ αnPn, α1, . . . , αn ∈ [0, 1], α1 + . . .+ αn = 1.

Acoperire convexa a unei multimi finite P: problematizare

− Daca P este finita, acoperirea sa convexa, Conv(P) este un politop con-vex.

− Cazuri particulare: m = 1 (segment); m = 2 (poligon); m = 3 (poliedru).

− Cazul m = 1: acoperirea convexa este un segment; algoritmic: parcurgerea punctelor (complexitate O(n)).

− In continuare: m = 2.

− Problema: Cum determinam, algoritmic, varfurile acoperirii convexe (camultime, ca lista)?

8

2.2 Algoritmi lenti (naivi)

Determinarea punctelor extreme si ordonarea lor

Definitia 2.2 Un punct M al unei multimi convexe S este punct extrem allui S daca nu exista A,B ∈ S astfel ca M ∈ [AB].

Propozitia 2.3 (Caracterizarea punctelor extreme). Fie P o multimefinita si Conv(P) acoperirea sa convexa. Un punct M ∈ P nu este punct extrem⇔ este situat ıntr-un triunghi avand varfurile ın P (sau ın interiorul acestuitriunghi), dar nu este, el ınsusi, varf al triunghiului.

Propozitia 2.4 (Ordonarea punctelor extreme). Fie P o multime finitasi Conv(P) acoperirea sa convexa. Ordonand punctele extreme ale lui Conv(P)dupa unghiul polar (format ıntr-un sistem de coordonate polare avand origineaıntr-un punct interior al lui Conv(P)), se obtin varfurile consecutive ale luiConv(P).

Comentarii

− Cum se stabileste daca un punct P apartine unui triunghi ABC sau interi-orului acestuia? (folosind arii, verificand daca P situat pe laturi sau situatde aceeasi parte a fiecarei laturi ca si varful opus − ”Testul de orientare”,etc.)

− Coordonate carteziene (x, y) si coordonate polare (ρ, θ) (pentru punctepentru care relatiile au sens):{

x = ρ cos θy = ρ sin θ

{ρ =

√x2 + y2

θ = arctg yx

− Pentru a ordona / sorta punctele nu este nevoie ca unghiurile polare safie calculate explicit! Are loc relatia θ(Q) > θ(P ) ⇔ Q este ”ın stanga”

muchiei orientate−→OP (v. ”Testul de orientare”).

− Daca M1, . . . ,Mq sunt puncte extreme ale lui Conv(P), atunci centrul degreutate 1

qM1 + . . .+ 1qMq este situat ın interiorul Conv(P).

Algoritmul lent 1

Input: O multime de puncte P din R2.

Output: O lista L care contine varfurile ce determina frontiera acoperirii convexe,parcursa ın sens trigonometric.

1. M← ∅ /*M este multimea punctelor extreme*/

2. for P ∈ P

3. do valid ← true

4. for (A,B,C) ∈ P × P × P distincte 2× 2, distincte de P

5. do if P ın interiorul ∆ABC sau pe laturile sale

6. then valid ← false

7. if valid=true then M =M∪ {P}

8. do calculeaza centrul de greutate al lui M

9

9. do sorteaza punctele din M dupa unghiul polar, obtinand lista L

Comentarii

− Complexitatea: O(n4) (pasii 1-7: O(n4); pasul 8: O(n); pasul 9: O(n log n)).

− Complexitatea algebrica: necesare polinoame de gradul II

− Trateaza corect cazurile degenerate (daca A,B,C sunt coliniare pe fron-tiera, cu C ∈ [AB], doar A si B sunt detectate ca fiind puncte extreme)!

Determinarea muchiilor frontierei

− Sunt considerate muchiile orientate.

− Q: Cum se decide daca o muchie orientata fixata este pe frontiera?

− A: Toate celelalte puncte sunt ”ın stanga” ei (v. ”Testul de orientare”).

Algoritmul lent 2

Input: O multime de puncte P din R2.Output: O lista L care continte varfurile ce determina frontiera acoperirii convexe,parcursa ın sensul trigonometric.

1. E ← ∅, L ← ∅ /*E este lista muchiilor orientate*/

2. for (P,Q) ∈ P × P cu P 6= Q

3. do valid ← true

4. for R ∈ P \ {P,Q}

5. do if R ”ın dreapta” lui−→PQ

6. then valid ← false

7. if valid=true then E = E ∪ {−→PQ}

8. din E se construieste lista L a varfurilor acoperirii convexe /*este necesar caE sa fie coerenta*/

Comentarii

− Complexitatea: O(n3).

− Complexitatea algebrica: necesare polinoame de gradul II

− Tratarea cazurilor degenerate: poate fi adaptat. Pasul 5 trebuie rafinat:

5. do if R ”ın dreapta” lui−→PQ or (P,Q,R coliniare and r(P,R,Q) < 0)

6. then valid ← false

− Robustetea: datorita erorilor de rotunjire este posibil ca algoritmul sa nureturneze o lista coerenta de muchii.

10

2.3 Algoritmi ”clasici”

2.3.1 Algoritmi incrementali: Graham’s scan, Jarvis’ march

Graham’s scan [1972]

− Punctele sunt mai ıntai sortate (lexicografic, dupa unghiul polar si distantapolara) si renumerotate.

− Algoritm de tip incremental, punctele fiind adaugate unul cate unul lalista L a frontierei acoperirii convexe. Pe parcurs, anumite puncte sunteliminate - actualizare locala a listei varfurilor acoperirii convexe.

− Q: Cum se decide daca trei puncte sunt varfuri consecutive ale acopeririiconvexe (parcursa ın sens trigonometric)?

− A: Se efectueaza un ”viraj la stanga” ın punctul din mijloc.

Graham’s scan (algoritm)

Input: O multime de puncte P din R2.Output: O lista L care contine varfurile ce determina frontiera acoperirii convexe,parcursa ın sens trigonometric.

1. Determinarea unui punct interior din Conv(P) /* de ex. baricentrul

2. Efectuarea unei translatii, punctul interior de la 1. devine originea O

3. Sortare si ordonare ın raport cu unghiul polar si distanta polara, renumerotareP1, P2, . . . , Pn conform ordonarii

4. L ← (P1, P2)

5. for i← 3 to n

6. do adauga Pi la sfarsitul lui L

7. while L are mai mult de doua puncteand ultimele trei nu determina un viraj la stanga

8. do sterge penultimul punct

9. return L

Graham’s scan, varianta lui Andrew [1979]

− Punctele sunt mai ıntai sortate (lexicografic, dupa coordonatele carte-ziene) si renumerotate.

− Algoritmul determina doua liste, reprezentand marginea inferioara si ceasuperioara a frontierei, pentru a le determina sunt folosite la initializarepunctele P1, P2, respectiv Pn, Pn−1. In final, aceste liste sunt concatenate.

− Principiul: asemanator celui de la Graham’s scan: punctele sunt adaugateunul cate unul la lista. Seefectueaza testul de orientare pentru ultimeletrei puncte si este eliminat penultimul punct, ın cazul ın care ultimele treipuncte nu genereaza un viraj la stanga.

11

Comentarii - Graham’s scan

− Algoritm specific pentru context 2D. Nu este on-line, fiind nevoie de toatepunctele.

− Complexitatea: O(n log n); spatiu: O(n); complexitate algebrica: poli-noame de gradul II.

− Tratarea cazurilor degenerate: corect.

− Robustetea: datorita erorilor de rotunjire este posibil ca algoritmul sareturneze o lista eronata (dar coerenta) de muchii.

− Graham’s scan este optim pentru ”cazul cel mai nefavorabil”.

− Problema sortarii este transformabila ın timp liniar ın problema acopeririiconvexe.

Jarvis’ march / Jarvis’ wrap [1973]

− Algoritm de tip incremental. Nu necesita sortare prealabila.

− Initializare: un punct care este sigur un varf al acoperirii convexe (e.g.punctul cel mai de jos / din stanga / stanga jos).

− Lista se actualizeaza prin determinarea succesorului: ”cel mai la dreapta”punct.

− Implementare: doua abordari (i) ordonare; (ii) testul de orientare.

− Complexitate: O(hn), unde h este numarul punctelor de pe frontiera aco-peririi convexe.

Jarvis’ march (algoritm)

Input: O multime de puncte necoliniare P = {P1, P2, . . . , Pn} din R2 (n ≥ 3).Output: O lista L care contine varfurile ce determina frontiera acoperirii convexe,parcursa ın sens trigonometric.

1. Determinarea unui punct din P care apartine frontierei (de exemplu cel maimic, folosind ordinea lexicografica); acest punct este notat cu A1.

2. k ← 1; L ← (A1); valid ← true

3. while valid= true

4. do alege un pivot arbitrar S ∈ P, diferit de Ak

5. for i← 1 to n

6. do if Pi este la dreapta muchiei orientate AkS

7. then S ← Pi

8. if S 6= A1

9. then k ← k + 1;Ak = Sadauga Ak la L

10. else valid ← false

11. return L

12

2.4 Exercitii, probleme, aplicatii

Exercitiul 2.5 Fie M = {P1, P2, . . . , P7}, unde P1 = (1, 11), P2 = (2, 7),P3 = (3, 8), P4 = (4, 10), P5 = (5, 7), P6 = (6, 7), P7 = (7, 11). Detaliaticum evolueaza lista varfurilor care determina marginea inferioara a frontiereiacoperirii convexe a lui M, obtinuta pe parcursul Graham’s scan / Graham’sscan varianta Andrew. Justificati!

Exercitiul 2.6 Consideram punctele A = (−6, 6), B = (1, 6), C = (1,−1),D = (−6, 0), E = (6, 0), F = (3, 2), G = (−4,−2), H = (−1,−2), I = (−2,−2).Precizati care este numarul maxim de elemente pe care ıl contine L pe parcursulparcurgerii Graham’s scan, indicand explicit punctele respective din L (L estelista varfurilor care determina frontiera acoperirii convexe a lui M, iar punctul”intern” considerat este O). Justificati!

Exercitiul 2.7 Dati un exemplu de multime M din planul R2 pentru care,la final, Li are 3 elemente, dar, pe parcursul algoritmului, numarul maximde elemente al lui Li este egal cu 5 (Li este lista varfurilor care determinamarginea inferioara a frontierei acoperirii convexe a luiM, obtinuta pe parcursulGraham’s scan, varianta Andrew). Justificati!

Exercitiul 2.8 Fie punctele P1 = (2, 0), P2 = (0, 3), P3 = (−4, 0), P4 = (4, 2),P5 = (5, 1). Precizati testele care trebuie efectuate, atunci cand este aplicatJarvis’ march, pentru determinarea succesorului M al ”celui mai din stanga”punct si a succesorului lui M . Cum decurg testele daca se ıncepe cu ”cel maide jos” punct?

Exercitiul 2.9 Dati un exemplu de multime cu 8 elemente M din planul R2

pentru care frontiera acoperirii convexe are 3 elemente si pentru care, la gasireasuccesorului ”celui mai din stanga” punct (se aplica Jarvis’ march), toate cele-lalte puncte sunt testate. Justificati!

Exercitiul 2.10 Scrieti ın pseudocod Graham’s scan - varianta Andrew si Jar-vis’ march.

Exercitiul 2.11 Explicati daca Graham’s scan / Jarvis’ march indica rezulta-tul dorit atunci cand toate punctele sunt situate pe o aceeasi dreapta.

Exercitiul 2.12 Date n puncte ın plan, scrieti un algoritm de complexitateO(n log n) care sa determine un poligon care are toate aceste puncte ca varfuri.Explicati cum este aplicat acest algoritm pentru punctele P1 = (4, 2), P2 =(7, 1), P3 = (−3, 5), P4 = (3, 6), P5 = (−4,−4), P6 = (−1, 1), P7 = (2,−6).

Exercitiul 2.13 Fie punctele A = (3,−3), B = (3, 3), C = (−3,−3), D =(−3, 3), M = (2 − λ, 3 + λ), λ ∈ R. Scrieti un algoritm care sa indice numarulde puncte de pe frontiera acoperirii convexe a multimii {A,B,C,D,M}.

13

Capitolul 3

Triangulari

3.1 Triangularea poligoanelor. Problema gale-riei de arta

Supravegherea unei galerii de artaCamera din P poate supraveghea A, dar nu B.

����

rJJJJJJJ

P

rA

rB

Formalizare

− O galerie de arta poate fi interpretata (ın contextul acestei probleme) ca unpoligon simplu P (adica un poligon fara autointersectii) avand n varfuri.

− O camera video (vizibilitate 3600) poate fi identificata cu un punct dininteriorul lui P; ea poate supraveghea acele puncte cu care poate fi unitaprintr-un segment inclus ın interiorul poligonului.

− Problema galeriei de arta: cate camere video sunt necesare pentru asupraveghea o galerie de arta si unde trebuie amplasate acestea?

Numarul de camere vs. forma poligonului

14

− Se doreste exprimarea numarului de camere necesare pentru supraveghereın functie de n (sau controlarea acestuia de catre n).

− Pentru a supraveghea un spatiu avand forma unui poligon convex, estesuficienta o singura camera.

− Numarul de camere depinde si de forma poligonului: cu cat forma estemai ”complexa”, cu atat numarul de camere va fi mai mare.

− Principiu: Poligonul considerat: descompus ın triunghiuri (triangulare).

Definitii

− Fie P un poligon plan.

− (i) O diagonala a lui P este un segment ce uneste doua varfuri ale acestuiasi care este situat ın interiorul lui P.

− (ii) O triangulare TP a lui P este o descompunere a lui P ın triunghiuri,data de o multime maximala de diagonale ce nu se intersecteaza.

− Teorema. Orice poligon simplu admite o triangulare. Orice triangularea unui poligon cu n varfuri contine exact n− 2 triunghiuri.

Rezovlarea problemei galeriei de arta

− Amplasarea camerelor se poate face ın varfurile poligonului.

− Data o pereche (P, TP ) se considera o 3-colorare a acesteia: fiecarui varfıi corespunde o culoare dintr-un set de 3 culori si pentru fiecare triunghi,cele 3 varfuri au culori distincte.

− Observatie. Daca P este simplu, o astfel de colorare exista, deoarecegraful asociat perechii (P, TP ) este arbore.

Teorema galeriei de arta

− Teorema. [Chvatal, 1975; Fisk, 1978] Pentru un poligon cu n varfuri,[n3

]camere sunt uneori necesare si ıntotdeauna suficiente pentru ca

fiecare punct al poligonului sa fie vizibil din cel putin una din camere.

Metode de triangulare: ear cutting / clipping / trimming

− Concepte:

– varf principal,

– ear (varf / componenta de tip E) [Meisters, 1975];

– mouth (varf / componenta de tip M) [Toussaint, 1991].

− Orice varf de tip E este convex; orice varf de tip M este concav (reflex).Reciproc nu neaparat!

− Teorema. (Two Ears Theorem [Meisters, 1975]) Orice poligon cu celputin 4 varfuri admite cel putin doua componente de tip E care nu sesuprapun.

− Corolar. Orice poligon simplu admite (cel putin) doua diagonale.

− Algoritmul de triangulare bazat de metoda ear cutting: complexitateO(n2).

15

− Link despre triangulariLink pentru algoritmul Ear cutting

Metode de triangulare: descompunerea ın poligoane monotone

− Concept: poligon y-monoton

− Algoritmi de triangulare eficienti: complexitate O(n) pentru poligoaney-monotone [Garey et al., 1978].

− Descompunerea unui poligon oarecare in componente y-monotone poate firealizata cu un algoritm de complexitate O(n log n) [Lee, Preparata, 1977].

− Exista si alte clase de algoritmi mai rapizi; [Chazelle, 1990]: algoritmliniar.

− Link pentru alte abordari

Triangularea poligoanelor monotone

Input: Un poligon y-monoton P.

Output: O triangulare a lui P.

1. Lantul varfurilor din partea stanga si al celor din partea dreapta suntunite ıntr-un singur sir, ordonat descrescator, dupa y (daca ordonata esteegala, se foloseste abscisa). Fie v1, v2, . . . , vn sirul ordonat.

2. Initializeaza o stiva vida S si insereaza v1, v2.

3. for j = 3 to n− 1

4. do if vj si varful din top al lui S sunt ın lanturi diferite

5. then extrage toate varfurile din S

6. insereaza diagonale de la vj la vf. extrase, exceptand ultimul

7. insereaza vj−1 si vj ın S

8. else extrage un varf din S

9. extrage celelalte varfuri din S daca diagonalele formate cu vjsunt ın interiorul lui P; insereaza aceste diagonale; insereazaınapoi ultimul varf extras

10. insereaza vj ın S

11. adauga diagonale de la vn la vf. stivei (exceptand primul si ultimul)

3.2 Triangularea unei multimi arbitrare de puncte

Problematizare

− Triangularea unui poligon convex (lista ordonata de puncte (P1, P2, . . . , Pn).

− Are sens sa vorbim de triangulare pentru multimea {P1, P2, . . . , Pn}?

− Comentariu: Triangularile multimilor de puncte sunt esentiale ın graficape calculator.

16

− Definitie. O triangulare a unei multimi P din plan este o subdivizaremaximala a acoperirii convexe Conv(P) a lui P cu triunghiuri ale carorvarfuri sunt elemente ale lui P (fara autointersectii!)

− Trebuie facuta distinctie ıntre triangulare a unui poligon (P1, P2, . . . , Pn)si triangulare a multimii subdiacente {P1, P2, . . . , Pn} (coincid daca poli-gonul este convex!)

Elemente ale unei triangulari

− Data o multime de puncte P si o triangulare TP a sa:varfuri, muchii, triunghiuri.

− Legatura ıntre aceste elemente?

− Propozitie. Fie P o multime de n puncte din plan nesituate toate pe oaceeasi dreapta. Notam cu k numarul de puncte de pe frontiera acopeririiconvexe Conv(P). Orice triangulare a lui P are (2n − k − 2) triunghiurisi (3n− k − 3) muchii.

− Demonstratie: Se bazeaza pe formula lui Euler / numarul de incidente.

− Exemplu: Cazul unui poligon convex cu n varfuri (k = n): n− 2 triun-ghiuri si 2n− 3 muchii.

3.3 Triangulari unghiular optime

Problematizare

− Problema. Problema. Se fac masuratori ale altitidinii pentru un teren.Se doreste reprezentarea tridimensionala (cat mai sugestiva). Alternativ:se doreste generarea unui teren pentru o aplicatie.

−

− Problema (reformulata). Cum ”comparam triangularile” unei multimide puncte fixate?

− Exemplu. Masuratori ale altitudinii.

Triangulare 1

1000

980

990

1005

640

620

630

580

570

590

Triangulare 2

1000

980

990

1005

640

620

630

580

570

590

17

− Intrebari naturale: (i) Exista o triangulare “convenabila” a unei multimide puncte? (ii) Cum poate fi determinata eficient o astfel de triangulare?

Terminologie

− Fixata: o multime de puncte P.

− Fie T o triangulare a lui P cum triunghiuri. Fie α1, α2, . . . , α3m unghiurilelui T , ordonate crescator. Vectorul unghiurilor lui T este A(T ) =(α1, α2, . . . , α3m).

− Relatie de ordine pe multimea triangularilor lui P: ordinea lexico-grafica pentru vectorii unghiurilor. Fie T si T ′ doua triangulari ale lui P.Atunci A(T ) > A(T ′) daca ∃i astfel ca αj = α′j , ∀1 ≤ j < i si αi > α′i.

− Triangulare unghiular optima: T astfel ca A(T ) ≥ A(T ′), pentruorice triangulare T ′.

− Exemplu: Cazul unui patrulater convex.

Muchii ilegale, triangulari legale

− Fixata: o multime de puncte P.

− Conceptul de muchie ilegala. Fie A,B,C,D ∈ P fixate astfel caABCD sa fie un patrulater convex; fie TAC , TBD triangularile date dediagonalele AC, respectiv BD. Muchia AC este ilegala daca

minA(TAC) < minA(TBD).

− Concluzie: Muchia AC este ilegala daca, printr-un flip (ınlocuirea ei cuBD), cel mai mic unghi poate fi marit (local).

− Concluzie (reformulare): Fie T o triangulare cu o muchie ilegala e,fie T ′ triangularea obtinuta din T prin flip-ul muchiei e. Atunci A(T ′) >A(T ).

− Criteriu geometric pentru a testa daca o muchie este legala.

Triangulari unghiular optime vs. triangulari legale

− Triangulare legala: nu are muchii ilegale.

− O triangulare legala poate fi determinata pornind de la o triangulare ar-bitrara.

− Propozitie. Fie P o multime de puncte din plan.

(i) Orice triangulare unghiular optima este legala.

(ii) Daca P este ın pozitie generala (oricare patru puncte nu sunt conci-clice), atunci exista o unica triangulare legala, iar aceasta este un-ghiular optima.

− Teorema. Fie P o multime de n puncte din plan, ın pozitie generala.Triangularea unghiular optima poate fi construita, folosind un algoritmincremental randomizat, ın timp mediu O(n log n), folosind O(n) memoriemedie.

18

3.4 Exercitii, probleme, aplicatii

Exercitiul 3.1 Fie P poligonul dat de punctele P1 = (6, 0), P2 = (2, 2), P3 =(0, 7), P4 = (−2, 2), P5 = (−8, 0), P6 = (−2,−2), P7 = (0,−6), P8 = (2,−2) .Indicati o triangulare TP a lui P si construiti graful asociat perechii (P, TP).

Exercitiul 3.2 Aplicati metoda din demonstratia teoremei galeriei de arta,indicand o posibila amplasare a camerelor de supraveghere ın cazul poligonu-lui P1P2 . . . P12, unde P1 = (4, 4), P2 = (5, 6), P3 = (6, 4), P4 = (7, 4), P5 =(9, 6), P6 = (11, 6) iar punctele P7, . . . , P12 sunt respectiv simetricele punctelorP6, . . . , P1 fata de axa Ox.

Exercitiul 3.3 Fie poligonul P = (P1P2P3P4P5P6), unde P1 = (5, 0), P2 =(3, 2), P3 = (−1, 2), P4 = (−3, 0), P5 = (−1,−2), P6 = (3,−2). Aratati caTeorema Galeriei de Arta poate fi aplicata ın doua moduri diferite, asa ıncat ınprima varianta sa fie suficienta o singura camera, iar ın cea de-a doua varianta safie necesare si suficiente doua camere pentru supravegeherea unei galerii avandforma poligonului P.

Exercitiul 3.4 Fie poligonul P = (P1P2 . . . P10), unde P1 = (0, 0), P2 = (6, 0),P3 = (6, 6), P4 = (3, 6), P5 = (3, 3), P6 = (4, 4), P7 = (4, 2), P8 = (2, 2),P9 = (2, 6), P10 = (0, 6). Stabiliti natura varfurilor lui P (varf principal sau nu/ varf convex sau concav).

Exercitiul 3.5 Fie n ≥ 2 un numar natural par fixat. Consideram multimeaM = {A0, . . . , An, B0, . . . , Bn, C0, . . . , Cn, D0, . . . , Dn}, unde Ai = (i, 0), Bi =(0, i), Ci = (i, i), Di = (n− i, i), pentru orice i = 0, . . . , n. Determinati numarulde triunghiuri si numarul de muchii al unei triangulari a lui M.

Exercitiul 3.6 Dati exemplu de poligon care sa aiba mai multe varfuri princi-pale concave decat varfuri principale convexe.

Exercitiul 3.7 Dati exemplu de multime de puncte din R2 care sa admita otriangulare avand 3 triunghiuri si 7 muchii.

Exercitiul 3.8 Dati exemplu de multime M = {A,B,C,D,E, F,G} din R2

astfel ca M sa admita o triangulare ce contine 14 muchii.

Exercitiul 3.9 Dati exemplu de doua multimi de puncteM1,M2 din R2 avandnumar diferit de puncte, dar care admit triangulari ce contin exact 3 fete de tiptriunghi. Pentru fiecare din cele doua multimi precizati: (i) numarul de muchiidin triangularile corespunzatoare; (ii) numarul muchiilor de tip semidreapta alediagramei Voronoi asociate.

Exercitiul 3.10 Dati exemplu de multime M cu 6 elemente din R2 care saadmita o triangulare ce contine 12 muchii, iar una dintre submultimile sale cu 4elemente sa admita o triangulare ce contine 5 muchii. Justificati alegerea facuta.

Exercitiul 3.11 Fie ABCD un patrulater convex. Fie C cercul circumscristriunghiului ∆ABC. Demonstrati ca diagonala AC este ilegala daca si numaidaca D este ın interiorul lui C.

Exercitiul 3.12 Fie punctele A = (1, 1), B = (1,−1), C = (−1,−1), D =(−1, 1), E = (0,−2),M = (0, λ), unde λ ∈ R este un parametru real. Scrietiun algoritm care sa indice numarul de triunghiuri si numarul de muchii ale uneitriangulari asociate multimii {A,B,C,D,E,M}.

19

Capitolul 4

Intersectii

4.1 Intersectia segmentelor (generalitati)

Motivatie (Probleme geometrice ın context 2D)

− Problema 1. Data o lista (multime ordonata) de puncte P = (P1, P2, . . . , Pm),sa se stabileasca daca ea reprezinta un poligon simplu (fara autointersectii).

− Problema 2. Date doua poligoane simple P si Q, sa se stabileasca dacase intersecteaza (interioarele lor se intersecteaza).

− Problema 3. Data o multime S = {s1, . . . , sn} de n segmente ınchise dinplan, sa se determine toate perechile care se intersecteaza.

− Problema 3’. Data o multime S = {s1, . . . , sn} de n segmente ınchisedin plan, sa se determine toate punctele de intersectie dintre ele.

Algoritmul trivial

− Idee de lucru: Sunt considerate toate perechile de segmente si se deter-mina cele care se intersecteaza / se calculeaza punctele de intersectie.

− Complexitate:

– timp: O(n2)

– memorie: O(n)

– algebric: polinoame de gradul II (Problema 3), rapoarte de polinoamede gradul II (Problema 3’)

− Comentariu: In anumite cazuri: optim (daca toate segmentele se inter-secteaza).

− Algoritmi mai eficienti (output / intersection sensitive)?

Rezolvarea problemei ın context 1D

− Ordonarea lexicografica a extremitatilor segmentelor / intervalelor ıntr-olista P.

− Lista P este parcursa (crescator); lista L a segmentelor care contin punctulcurent din P este actualizata:

– daca punctul curent este marginea din stanga a unui segment s,atunci s este adaugat la lista L

20

– daca punctul curent este marginea din dreapta a unui segment s,atunci s este sters din L si se rapoarteaza intersectii ıntre s si toatesegmentele din L

− Teorema. Algoritmul are complexitate O(n log n + k) si necesita O(n)memorie (k este numarul de perechi ce se intersecteaza).

4.2 Metoda liniei de baleiere

Un prim algoritm

− Linia de baleire l: orizontala, astfel ca toate intersectiile situate deasupraliniei de baleiere au fost detectate.

− Statutul (sweep line status): multimea segmentelor care intersecteazal.

− Evenimente (event points): capetele segmentelor −→ actualizarea sta-tutului

− Obs. 1. Sunt testate pentru intersectie segmente care intersecteaza, laun moment dat, l −→ (sunt testate segmentele care sunt ”aproape” de-alungul axei Oy) −→ ınca ineficient.

− Obs. 2. Linia de baleiere are, de fapt, o variatie ”discreta”, nu continua.

Un algoritm eficient [Bentley si Ottmann, 1979; Mehlhorn si Naher,1994]

− Idee de lucru: ordonare (segmente, evenimente).

– Segmentele: ordonate folosind extremitatile superioare (lexicografic,x apoi y).

– Evenimente (puncte): (lexicografic, y apoi x).

– Statutul: lista (multime ordonata)

− Avantaj: ın momentul modificarii statutului, sunt testate intersectiiledoar ın raport cu vecinii din lista (sunt testate segmentele care sunt”aproape” de-a lungul axei Ox).

− Fundamental: Punctele de intersectie devin, la randul lor, evenimente,deoarece schimba ordinea segmenetelor care le determina −→ chiar dacanu sunt determinate explicit, trebuie inserate ın lista de evenimente (com-pararea coordonatelor poate necesita utilizarea unor polinoame de gradulV)

3 tipuri de evenimente

− Marginea superioara a unui segment

– apare un nou segment ın statutul liniei de baleiere, ce trebuie inseratcorespunzator

– testat, ın raport cu vecinii, daca au puncte de intersectie sub linia debaleiere −→ vor deveni ulterior evenimente

− Marginea inferioara a unui segment

21

– eliminat un segment din statutul liniei de baleiere

– testare pentru segmentele vecine nou aparute

− punctele de intersectie (inserate ın mod corespunzator pe parcurs)

– segmentele care le determina trebuie ”inversate” ın statutul liniei debaleiere

– testare pentru segmentele vecine nou aparute

Implementare: structuri de date utilizate

− Q coada de eveniment (event queue): puncte, ordonate lexicografic, y apoix

− T arbore binar de cautare echilibrat (balanced binary search tree): seg-mente −→ este retinuta ordinea segmentelor

Algoritm Intersectii

− Input. O multime de segmente din planul R2.

− Output. Multimea punctelor de intersectie (explicit sau doar formal);pentru fiecare punct precizeaza segmentele pe care se gaseste.

1. Q ← ∅. Insereaza extremitatile segmentelor ın Q; ımpreuna cu margineasuperioara a unui segment memoreaza si segmentul

2. T ← ∅.

3. while Q 6= ∅

4. do determina evenimentul p care urmeaza ın Q si ıl sterge

5. Analizeaza (p)

Analizeaza (p)

1. Fie U(p) multimea segmentelor a caror extremitate superioara este p (pen-tru cele orizontale este marginea din stanga) - stocata cu p ın Q.

2. Determina toate segmentele care contin p: sunt adiacente ın T (de ce?)Fie D(p), respectiv Int(p), multimea segmentelor care au p drept margineinferioara, respectiv contin p ın interior.

3. if U(p) ∪D(p) ∪ Int(p) contine mai mult de un segment

4. then raporteaza p ca punct de intersectie, ımpreuna cusegmentele din U(p), D(p), Int(p)

5. sterge segmentele din D(p) ∪ Int(p) din T

6. insereaza segmentele din U(p)∪ Int(p) ın T (ordinea segmentelor pe frun-zele lui T coincide cu ordinea ın care sunt intersectate de o linie de baleieresituata imediat sub p)

7. if U(p) ∪ Int(p) = ∅

8. then fie sl si sr vecinii din stanga/dreapta ai lui p din T

9. DeterminaEveniment (sl, sr, p)

22

10. else fie s′ din U(p) ∪ Int(p) cel mai ın stanga ın T

11. fie sl vecinul din stanga al lui p

12. DeterminaEveniment (sl, s′, p)

13. fie s′′ din U(p) ∪ Int(p) cel mai ın dreapta ın T

14. fie sr vecinul din dreapta al lui p

15. DeterminaEveniment (s′′, sr, p)

DeterminaEveniment (sgtl, sgtr, p)

1. if sgtl si sgtr se intersecteaza sub linia de baleiere sau pe liniade baleiere, dar la dreapta lui p si punctul de intersectie nueste deja ın Q

2. then insereaza punctul de intersectie ca eveniment ın Q

Rezultatul principal (intersectii de segmente) Teorema. Fie S o

multime care contine n segmente din planul R2. Toate punctele de intersectie alesegmentelor din S, ımpreuna cu segmentele corespunzatoare, pot fi determinateın O(n log n+ I log n) timp, folosind O(n) spatiu (I este numarul punctelor deintersectie).

4.3 Alte rezultate

Red-blue intersections [Mairson si Stolfi, 1988; Mantler si Snoeyink,2000]

Teorema. Pentru doua multimi R si B de segmente din R2 avand interi-oare disjuncte, perechile de segmente ce se intersecteaza pot fi determinate ınO(n log n + k) timp si spatiu liniar, folosind predicate (polinoame) de grad celmult II (n = |R|+ |B|) si k este numarul perechilor ce se intersecteaza).

4.4 Suprapunerea straturilor tematice

Subdiviziuni planare

− Conceptul de subdiviziune planara: varfuri, muchii, fete.

− Lista dublu ınlantuita [Muller si Preparata, 1978] (trei ınregistrari:varfuri, fete, muchii orientate (semi-muchii)).

23

– Varf v: coordonatele lui v ın Coordinates(v), pointer IncidentEdge(v)spre o muchie orientata care are v ca origine

– Fata f : pointer OuterComponent(f) spre o muchie orientata co-respunzatoare frontierei externe (pentru fata nemarginita este nil);lista InnerComponents(f), care contine, pentru fiecare gol, un po-inter catre una dintre muchiile orientate de pe frontiera

– Muchie orientata→e : pointer Origin(

→e ), pointer Twin(

→e ) pointer

IncidentFace(→e ), pointer Next(

→e ), pointer Prev(

→e ).

− Oricarei subdiviziuni planare S i se asociaza o lista dublu ınlantuita DS .

Algoritm Overlay (S1,S2)

− Input. Doua subdiviziuni planare S1, S2 memorate ın liste dublu ınlantuiteDS1 ,DS2

− Output. Overlay-ul O(S1,S2) dintre S1,S2, memorat ıntr-o lista dubluınlantuita DO(S1,S2)

1. Copiaza listele D1,D2 ıntr-o noua lista dublu ınlantuita DO(S1,S2)

2. Calculeaza toate intersectiile de muchii dintre S1 si S2 cu algoritmul In-tersectii. La fiecare eveniment, pe langa actualizarea lui Q si T , efec-tueaza:

− Actualizeaza DO(S1,S2), ın cazul ın care evenimentul implica atatmuchii ale lui S1, cat si ale lui S2

− Memoreaza noile muchii orientate adecvat

3. Determina ciclii de frontiera dinO(S1,S2), stabileste natura (exteriori/interiori)

4. Construieste graful G ale carui noduri corespund ciclilor de frontiera si alecarui arce unesc fiecare ciclu corespunzand unui gol cu ciclul de la stangavarfului cel mai din stanga si determina componentele conexe ale lui G

5. for fiecare componenta a lui G

6. do Fie C unicul ciclu de frontiera exterioara acomponentei si fie f fata marginita a ciclului. Creeazao ınregistrare pentru f , seteaza OuterComponent(f)(catre una din muchiile lui C), construieste listaInnerComponents(f) (pentru fiecare gol, pointer catreuna dintre muchiile orientate). Pentru fiecare muchieorientata, IncidentFace() catre ınregistrarea lui f

7. Eticheteaza fiecare fata a lui O(S1,S2)

Rezultate principale

− Teorema. (Overlay-ul hartilor) Fie S1 o subdiviziune de complexitaten1, S2 o subdiviziune de complexitate n2, fie n := n1 + n2. Overlay-ul dintre S1 si S2 poate fi construit ın O(n log n + k log n), unde k estecomplexitatea overlay-ului.

− Corolar. (Operatii boolene) Fie P1 un poligon cu n1 varfuri si P2 unpoligon cu n2 varfuri; fie n = n1 +n2. Atunci P1 ∪P2, P1 ∩P2 si P1 \P2

pot fi determinate ın timp O(n log n+ k log n), unde k este complexitateaoutput-ului.

24

4.5 Exercitii, probleme, aplicatii

Exercitiul 4.1 Fie punctele P1 = (4, 3), P2 = (1, 1), P3 = (6, 2), P4 = (11, 8);Q1 = (4, 5), Q2 = (9, 9), Q3 = (6, 7), Q4 = (11, 0). Pentru fiecare i = 1, . . . , 4notam cu si segmentul [PiQi]. Scrieti cum evolueaza statutul liniei de baleiere,precum si evenimentele care determina modificarea sa (linia de baleiere esteorizontala, iar statutul este o multime neordonata de segmente).

Exercitiul 4.2 Fie punctele A1 = (6, 1), A2 = (3, 2), A3 = (1, 8), A4 = (13, 7);B1 = (6, 6), B2 = (11, 10), B3 = (9, 0), B4 = (13,−1). Scrieti cum evolueazastatutul liniei de baleiere, precum si evenimentele care determina modificareasa (linia de baleiere este orizontala, iar statutul este o multime ordonata desegmente).

Exercitiul 4.3 Fie punctele P1 = (4,−1), P2 = (2, 8), P3 = (3, 3), P4 = (7, 0);Q1 = (4, 11), Q2 = (8, 2), Q3 = (10, 10), Q4 = (7, 4). Pentru fiecare i = 1, . . . , 4notam cu si segmentul [PiQi]. Consideram linia de baleiere l data de ecuatiay = 9. Indicati evenimentele deja eliminate din coada de evenimente Q, celeramase ın Q, cele care urmeaza sa fie incluse ulterior ın Q si precizati statutulcorespunzator lui l (statutul este o multime ordonata de segmente).

Exercitiul 4.4 Explicati cum poate fi parcursa frontiera unei fete si cum pot figasite toate muchiile din jurul unui varf, folosind pointerii asociati elementelorunei subdiviziuni planare.

Exercitiul 4.5 Consideram un dreptunghi D din interiorul caruia este scos undreptunghi ∆. Descrieti subdiviziunea planara asociata.

Exercitiul 4.6 Consideram trei dreptunghiuri D1, D2, D3 astfel ca D3 sa fiesituat ın interiorul lui D2 si D2 ın interiorul lui D1. Descrieti subdiviziuneaplanara asociata.

Exercitiul 4.7 Fie punctele A = (4, 0), B = (0, 4), C = (−4, 0), D = (0,−4).Construiti doua subdiviziuni planare distincte S1, S2 care au A,B,C,D cavarfuri, astfel ca S1 sa aiba doua fete, iar S2 sa aiba trei fete. Indicati numarultotal de semimuchii pentru S1, respectiv S2.

Exercitiul 4.8 Fie punctele A = (1, 6), B = (1, 1), C = (−4, 7), D = (6, 7),E = (1,−1), F = (5, 3), P = (−2, 3), Q = (2 − λ, 3), unde λ ∈ R este un pa-rametru. Scrieti un algoritm care sa calculeze numarul de puncte de intersectiedintre segmentul [PQ] si reuniunea [AB] ∪ [CD] ∪ [EF ]. Algoritmul distingeıntre puncte interioare ale segmentelor si extremitati ale acestora.

Exercitiul 4.9 Fie punctele A = (−2, 1), B = (1, 1), C = (1, 5), D = (5, 1),E = (3 − α, 3 + α), unde α este un parametru real. Scrieti un algoritm caresa determine numarul de fete al subdiziviunii planare determinate de muchiile[AB], [BC], [CA], [BD] si [CE].

25

Capitolul 5

Elemente de programareliniara

5.1 Motivatie: turnarea pieselor ın matrite

− Turnarea pieselor ın matrite si extragerea lor fara distrugerea matritei.

Matrita M

Piesa turnata P

Fata superioara a lui P

Fete standard

− Neajunsuri: unele obiecte pot ramane blocate ın matrite; exista obiectepentru care nu exista o matrita adecvata; extragerea obiectului depindede pozitia matritei.

− Problema studiata. Dat un obiect, exista o matrita din care sa poatafi extras?

− Conventii.

– Obiectele: poliedrale.

– Matritele: formate dintr-o singura piesa; fiecarui obiect P ıi esteasociata o matrita MP

– Obiectul: extras printr-o singura translatie (sau o succesiune detranslatii)

26

Terminologie si conventii

− Alegerea orientarii: diverse orientari ale obiectului pot genera diversematrite.

− Fata superioara: prin conventie, obiectele au (cel putin) o fata supe-rioara (este orizontala, este singura care nu este adiacenta cu matrita).Celelalte fete: standard; orice fata standard f a obiectului corespundeunei fete f a matritei.

− Obiect care poate fi turnat (castable): exista o orientare pentru careacesta poate fi turnat si apoi extras printr-o translatie (succesiune detranslatii): directie admisibila.

− Conventii: Matrita este paralelipipedica si are o cavitate corespunzatoareobiectului; fata superioara a obiectului (si a matritei) este perpendicularacu planul Oxy.

Fundamente geometrice

− Conditie necesara: directia de extragere ~d trebuie sa aiba componentaz pozitiva

− In general: o fata f a matritei pentru care unghiul dintre normala ex-terioara ~ν(f) la fata f si ~d este mai mic de 90◦ ımpiedica translatia ın

directia ~d

− Propozitie. Un poliedru P poate fi extras din matrita sa MP printranslatie ın directia ~d daca si numai daca ~d face un unghi de cel putin90◦ cu normala exterioara a fiecarei fete standard a lui P.

− Reformulare. Dat P, trebuie gasita o directie ~d astfel ıncat, pentrufiecare fata standard f , unghiul dintre ~d si ~ν(f) sa fie cel putin 90◦.

− Analitic: fiecare fata defineste un semiplan

− Concluzie: Fie P un poliedru. Multimea directiilor admisibile este datade o intersectie de semiplane.

− Teorema. Fie P un poliedru cu n fete. Se poate decide daca P reprezintaun obiect care poate fi turnat ın O(n2) timp si folosind O(n) spatiu. Incaz afirmativ, o matrita si o directie admisibia ın care poate fi extras Peste determinata cu aceeasi complexitate timp.

5.2 Intersectii de semiplane

Formularea problemei

− Fie H = {H1, H2, . . . ,Hn} o multime de semiplane din R2; semiplanul Hi

dat de o relatie de formaaix+ biy ≤ ci

− Intersectia H1 ∩ H2 ∩ . . . ∩ Hn este data de un sistem de inecuatii; esteo multime poligonala convexa, marginita de cel mult n muchii (poate fivida, marginita, nemarginita,...)

27

Algoritm IntersectiiSemiplane (H)

− Input. O multime H de semiplane din planul R2

− Output. Regiunea poligonala convexa C = ∩H∈HH

1. if card(H) = 1

2. then C ← H ∈ H

3. else descompune H ın doua multimi H1, H2 avand fiecare [n/2]elemente

4. C1 ← IntersectiiSemiplane (H1)

5. C2 ← IntersectiiSemiplane (H2)

6. C ← IntersecteazaRegiuniConvexe (C1, C2)

Rezultate principale

− Propozitie. Aplicand direct algoritmii de overlay, intersectia dintre douaregiuni convexe (IntersecteazaRegiuniConvexe) poate fi calculata cucomplexitate-timp O(n log n); ın particular algoritmul IntersectiiSemi-plane are complexitate O(n log2 n).

− Teorema. Algoritmul IntersecteazaRegiuniConvexe poate fi ımbunatatit,astfel ıncat complexitatea-timp sa fie liniara.

− Teorema. Intersectia unei multimi de n semiplane poate fi determinatacu complexitate-timp O(n log n) si folosind O(n) memorie.

5.3 Programare liniara

Problematizare

− Formulare generala (ın spatiul d-dimensional):

maximizeaza(c1x1 + c2x2 + . . .+ cdxd)

date constrangerile liniare (inegalitati)a11x1 + a12x2 + . . . a1dxd ≤ b1a21x1 + a22x2 + . . . a2dxd ≤ b2. . .an1x1 + an2x2 + . . . andxd ≤ bn

− Terminologie: date de intrare, functie obiectiv, constrangeri, regiunerealizabila (fezabila)

− Exemple: probleme de programare liniara 1-dimensionala, 2-dimensionala.

Rezultate

− Lema. (Pentru d = 1) Un program liniar 1-dimensional poate fi rezolvatın timp liniar.

− Interpretare a cerintei de maximizare: Maximizarea functiei obiectivrevine la a determina un punct al carui vector de pozitie are proiectia

maxima de directia data de vectorul→c= (c1, c2, . . . , cd).

28

− Pentru o problema de programare liniara ın plan (d = 2) pot fi distinsepatru situatii: (i) o solutie unica; (ii) toate punctele de pe o muchie suntsolutii; (iii) regiunea fezabila este nemarginita si pot fi gasite solutii de-alungul unei semidrepte; (iv) regiunea fezabila este vida.

Algoritm LPMARG2D (H,→c ,m1,m2)

− Input. Un program liniar (H ∪ {m1,m2},→c ) din R2

− Output. Daca (H ∪{m1,m2},→c ) nu e realizabil (fezabil), raporteaza. In

caz contrar, indica punctul cel mai mic lexicografic p care maximizeazaf→c

(p).

1. v0 ← “coltul” lui c0

2. fie h1, h2, . . . , hn semiplanele din H

3. for i← 1 to n

4. do if vi−1 ∈ hi

5. then vi ← vi−1

6. else vi ← punctul p de pe di care maximizeaza f→c

(p) dateconstrangerile din Hi

7. if p nu exista

8. then raporteaza “nefezabil” end

9. return vn

Algoritm aleatoriu

− Pasul 2. este ınlocuit cu:

2’. Calculeaza o permutare arbitrara a semiplanelor, folosind o proce-dura adecvata.

− Algoritmul incremental LPMARG2D are complexitate-timp O(n2), iarvarianta bazata pe alegerea aleatorie a semiplanelor are complexitate-timpmedie O(n) (n este numarul semiplanelor).

5.4 Exercitii, probleme, aplicatii

Exercitiul 5.1 Consideram doua ”piese” poligonale P1 si P2, avand normalelefetelor standard date de vectorii:

P1 : ν1 = (

√2

2,

√2

2); ν2 = (1, 0); ν3 = (0, 1); ν4 = (−1, 0); ν5 = (−

√2

2,

√2

2);

P2 : ν1 = (

√2

2,−√

2

2); ν2 = (1, 0); ν3 = (0, 1); ν4 = (−1, 0); ν5 = (−

√2

2,−√

2

2).

(ın aceasta ordine). Stabiliti care dintre piese poate fi extrasa din matritaasociata prin deplasare ın directia verticala (data de (0, 1). Desenati!

29

Exercitiul 5.2 Consideram semiplanele Sλ, S′, S′′ date de inecuatiile

Sλ : x− y − λ ≤ 0 (λ ∈ R), S′ : x− 1 ≥ 0, S′′ : y − 5 ≥ 0.

Discutati, ın functie de λ, natura intersectiei Sλ ∩ S′ ∩ S′′.

Exercitiul 5.3 Fie punctul p = (−1, 1); dreapta d : (y = 3x+ 4). Verificati cap ∈ d si ca d∗ ∈ p∗.

Exercitiul 5.4 Fie punctele p1 = (2, 5); p2 = (1, 6). Scrieti ecuatia dreapteip1p2 si detaliati (cu calcule explicite!) configuratia din planul dual.

Exercitiul 5.5 Fie dreapta d : (y = 2x + 1) si p = (1, 8). Verificati ca p estedeasupra lui d si ca d∗ este deasupra lui p∗.

Exercitiul 5.6 (i) Fie dreapta d : (y = 2x − 3). Alegeti doua puncte distincteP,Q ∈ d, determinati dualele d∗, P ∗, Q∗ si verificati ca {d∗} = P ∗ ∩Q∗.

(ii) Determinati duala urmatoarei configuratii: Fie trei drepte care trec prinacelasi punct M ; pe fiecare dreapta se ia cate un punct (diferit de M), astfel caaceste puncte sa fie coliniare.

Exercitiul 5.7 Fie configuratia: trei drepte care trec prin acelasi punct; pefiecare dreapta se alege un punct, diferit de punctul comun al celor trei drepte.Descrieti configuratia duala. Desenati!

Exercitiul 5.8 Fie hiperplanele H1, H2, H3, H4 date de inecuatiile

H1 : y ≥ 1; H2 : y ≤ 5; H3 : x ≥ 0; H4 : x− y ≥ λ,

unde λ ∈ R este un parametru. Scrieti un algoritm care sa indice naturaintersectiei H1 ∩H2 ∩H3 ∩H4.

30

5.5 Anexa

Plan primal si plan dual: completare. Configuratia din planul primal cores-punde problemei intersectiei de semiplane. Prin separarea ın semiplane inferi-oare/superioare si dualitate se face transferul la doua probleme distincte (mar-ginea superioara/inferioara a unei acoperiri convexe, ın care sunt consideratedoar punctele corespunzatoare).

31

Capitolul 6

Probleme de localizare

6.1 Localizarea punctelor − Harti trapezoidale

Problematizare

− Cautare cu Google Maps

− Interogare pentru localizarea unui punct: data o harta si un punct p, in-dicat prin cordonatele sale, sa se determine regiunea hartii ın care estesituat p.

− Harta: subdiviziune planara, formata din varfuri, (semi)muchii, fete.

− Necesitati: pre-procesare a informatiei; interogare rapida.

Formalizare

− Fie S o subdiviziune planara cu n muchii. Problema localizarii unui punctrevine la

– a retine informatiile referitoare la S pentru a putea raspunde lainterogari de tipul:

– dat un punct p, se raporteaza fata f care ıl contine pe p; ın cazul ıncare p este situat pe un segment sau coincide cu un varf, este precizatacest lucru.

− Lucrul cu coordonate: folosirea relatiei de ordine!

32

Exemplu - rafinare folosind benzi verticale

p

Exemplu - rafinare eficienta

p

33

Simplificari si ipoteze

− Se considera o multime S de n segmente astfel ca oricare doua dintre ele(i) fie nu au niciun punct comun; (ii) fie au un varf comun.

− Simplificare 1: Se considera un dreptunghi D cu laturile paralele cu axelede coordonate care include toata subdiviziunea initiala.

− Simplificare 2: Se presupune ca nu exista doua varfuri (extremitati alesegmentelor din S) distincte care au aceeasi coordonata x (ın particularnu exista segmente verticale).

− Concluzie: Se considera o multime de n segmente S care verifica ipotezelede mai sus: multime de segmente ın pozitie generala. Harta trapezo-idala / descompunere verticala / descompunere cu trapeze (tra-pezoidal map) T (S) a lui S este subdiviziunea indusa de S, dreptunghiulD si de extensiile verticale inferioare si superioare (concept introdus deSeidel, 1991).

Exemplu - harta trapezoidala

p

Harti trapezoidale − probleme studiate

− Descrierea obiectelor geometrice din care sunt formate − ce informatii seretin?

− Aspecte legate de complexitate?

− Structuri de date adecvate?

− Un algoritm eficient?

34

Descrierea obiectelor

− Lema 1. Fie S o multime de segmente ın pozitie generala. Fiecare fata aunei harti trapezoidale T (S) are una sau doua margini verticale si exactdoua margini ne-verticale.

De fapt: fiecare fata este un trapez, sau un dreptunghi sau un triunghi(ultimele putand fi privite drept cazuri particulare de trapeze).

− Ce informatii geometrice sunt retinute pentru un trapez?

− t(T ), b(T ), lp(T ), rp(T ) determina ın mod unic un trapez fixat T .

t(T ), b(T ) sunt segmente, iar lp(T ), rp(T ) sunt varfuri (extremitatiale segmentelor)

− Exista cinci cazuri posibile pentru marginea stanga lp (analog pentrumarginea dreapta lp).

Exemplu - harta trapezoidala si cazuri posibile pentru margineastanga

p

1

2

3

4

5

Complexitate si alte aspecte cantitative

− Lema 2. Fie S o multime de n segmente ın pozitie generala. Hartatrapezoidala T (S) contine cel mult 6n + 4 varfuri si cel mult 3n + 1trapeze.

− Lema 3. Fie S o multime de n segmente ın pozitie generala. Fiecaretrapez T este adiacent cu cel mult patru trapeze (cel mult un vecin stangasuperior, cel mult un vecin stanga inferior, cel mult un vecin dreaptasuperior, cel mult un vecin dreapta inferior).

Structura de date

− Inregistrari pentru segmentele din S si varfuri (extremitatile segmentelor).

35

− Inregistrari pentru trapeze: pointeri t, b, lp, rp si pointeri catre cei (celmult) patru vecini.

− Structura de cautare: D este un graf orientat aciclic cu o singuraradacina si exact o frunza pentru fiecare trapez din T (S).

− Noduri si teste asociate:

– x-nod, etichetat cu o extremitate a unui segment; pentru un punct ptestul asociat: este punctul p situat la stanga sau la dreapta drepteiverticale care trece prin extremitatea memorata ın acest nod?

– y-nod, etichetat cu un segment; pentru un punct p testul asociat:este punctul p situat deasupra sau dedesubtul segmentului memoratın acest nod?

Algoritm HartaTrapezoidala

− Input. O multime S de n segmente ın pozitie generala.

− Output. Harta trapezoidala T (S) si o structura de cautare D pentruT (S), ıntr-un dreptunghi R cu laturile paralele cu axele.

1. Determina dreptunghiul R.

2. Genereaza o permutare s1, s2, . . . , sn a segmentelor din S.

3. for i← 1 to n

4. do gaseste multimea de trapeze ∆0,∆1, . . . ,∆k care intersec-teaza segmentul si

5. elimina ∆0, . . . ,∆k si le ınlocuieste cu trapezele nou aparute

6. elimina frunzele corespunzatoare din D si creeaza noi frunze, ac-tualizeaza D

Rezultatul principal

Teorema. Fie S o multime de n segmente ın pozitie generala. Algorit-mul HartaTrapezoidala determina harta trapezoidala T (S) si o structurade cautare D pentru T (S) ın timp mediu O(n log n). Memoria medie ocupatade structura de cautare este O(n) si pentru un punct arbitrar q timpul mediu delocalizare este O(log n).

6.2 Aplicatie: miscarea unui robot-punct

Algoritm DeterminaSpatiuLiber (S)

− Input. O multime P de poligoane disjuncte.

− Output. O harta trapezoidala Cl a spatiului liber (pentru un robot-punct).

1. Fie S multimea muchiilor poligoanelor din P.

2. Determina harta trapezoidala T (S), folosind algoritmul HartaTrapez-oidala.

3. Elimina trapezele situate ın interiorul poligoanelor si returneaza subdivi-ziunea obtinuta.

36

Algoritm DeterminaDrum (T (Cl),Gd,Mstart,Mend)

− Input. Harta trapezoidala T (Cl) a spatiului liber, graful drumurilor Gd,punctul de start Mstart, punctul final Mend.

− Output. Un drum de la Mstart la Mend, daca exista. In caz contrar,algoritmul precizeaza ca nu exista un drum.

1. cauta trapeze ın T (Cl) continand Mstart, respectiv Mend.

2. if exista ∆start, respectiv ∆end continand Mstart, respectiv Mend

3. then fie vstart si vend centrele ∆start, ∆end (noduri din Gd)

4. cauta un drum ın Gd de la vstart la vend folosind BFS

5. if exista drum δ

6. then indica drumul [Mstartvstart] ∪ δ ∪ [vendMend]

7. else raporteaza ca nu exista drum de la Mstart la Mend

8. else raporteaza ca nu exista drum de la Mstart la Mend

Rezultatul principal

Teorema. Fie R un robot-punct care se deplaseaza ıntr-o multime S deobstacole poligonale, avand ın total n muchii. Utilizand timp mediu de pre-procesare O(n log n) pentru multimea S, un drum liber de coliziuni ıntre douapuncte fixate poate fi calculat (daca exista!) ın timp mediu O(n).

6.3 Exercitii, probleme, aplicatii

Exercitiul 6.1 Consideram un patrat avand laturile paralele cu axele de coor-donate, ın interiorul caruia se afla un alt patrat, astfel ca laturile sale sa facaun unghi de 30◦ cu axele de coordonate. Stabiliti cate trapeze are harta tra-pezoidala a regiunii situate ıntre cele doua patrate. Cate dintre acestea suntdegenerate?

Exercitiul 6.2 Fie punctele A = (1, 1), B = (2, 6), C = (5, 3), D = (4, 7),E = (8, 4), F = (10, 7), G = (6, 9), considerate ın interiorul dreptunghiuluiR delimitat de axele de coordonate si de dreptele date de ecuatiile x = 12,respectiv y = 12.

(a) Cate trapeze are harta trapezoidala asociata subdiviziunii planare indusede triunghiul ABC si patrulaterul DEFG?

(b) Indicati un drum parcurs de un robot-punct de la Mstart = (4, 1) laMend = (9, 9), determinat de algoritmul DeterminaDrum.

Exercitiul 6.3 Consideram doua triunghiuri T1 si T2 (astfel ca laturile lor sa fiesegmente ın pozitie generala), ın interiorul unui bounding box R. Cate trapezeare harta trapezoidala asociata? Depinde acest numar de pozitia relativa atriunghiurilor?

Exercitiul 6.4 Consideram patratul P delimitat de dreptele x = ±10, y = ±10(bounding box) si punctele A = (2, 0), B = (0, 2), C = (−2, 0), D = (0, λ), cuλ ∈ [−9, 9]. Fie Q acoperirea convexa a multimii {A,B,C,D}. Scrieti unalgoritm care sa decida cate trapeze are harta trapezoidala a regiunii situateıntre patratul P si poligonul Q.

37

Capitolul 7

Diagrame Voronoi

7.1 Generalitati

Problematizare

− Se considera o multime de puncte (oficiile postale) din plan. Care este celmai apropiat?

− Ideea de a delimita “zone de influenta” a aparut cu multa vreme ın urma(de exemplu ın lucrarile lui Descartes, dar si ın legatura cu alte probleme;este utilizata ın mod curent ın varii domenii. In plus, astfel de “ımpartiri”apar ın natura.

Formalizare

− Fie P = {P1, P2, . . . , Pn} o multime de puncte din planul R2, numitesituri.

− Diagrama Voronoi a lui P (notata Vor(P)) este o divizare a planuluiR2 ın n celule V(P1), . . . ,V(Pn) cu proprietatea ca

P ∈ V(Pi)⇔ d(P, Pi) ≤ d(P, Pj), ∀j = 1, . . . , n.

− Doua celule adiacente au ın comun o muchie sau un varf (punct de intersectiea muchiilor).

− Atentie! Varfurile lui Vor(P) sunt diferite de punctele din P.

− Uneori, prin abuz de limbaj, este precizata doar ımpartirea ın muchii /varfuri.

− Diagrame Voronoi pot fi construite pentru diverse functii distanta (e.g.distanta Manhattan); forma celulelor depinde de forma “cercului” ın ra-port cu functia distanta respectiva.

7.2 Proprietati

Proprietati elementare

− Celula asociata unui punct este o intersectie de semiplane:

V(Pi) =⋂j 6=i

h(Pi, Pj),

38

unde h(Pi, Pj) este semiplanul determinat de mediatoarea segmentului[PiPj ] care contine punctul Pi.

− In particular: fiecare celula este o multime convexa.

− Aplicabilitate: algoritm (lent) de determinare a diagramei Voronoi.

Structura unei diagrame Voronoi

− Fie P = {P1, P2, . . . , Pn} o multime de puncte din planul R2.

− Daca toate punctele sunt coliniare, atunci diagrama Voronoi asociataVor(P) contine n− 1 drepte paralele ıntre ele (ın particular, pentru n ≥ 3,ea nu este conexa).

− In caz contrar, diagrama este conexa, iar muchiile sale sunt fie segmente,fie semidrepte (cui corespund acestea?).

− Propozitie. Fie o multime cu n situri. Atunci, pentru diagrama Voronoiasociata au loc inegalitatile

nv ≤ 2n− 5, nm ≤ 3n− 6,

unde nv este numarul de varfuri ale diagramei si nm este numarul demuchii al acesteia.

7.3 Diagrame Voronoi si triangulari Delaunay

Legatura cu triangularile legale / unghiular optime

− Constructie:

• Multime de puncte P ın planul R2 =⇒• Diagrama Voronoi Vor(P) =⇒• Graful dual G(P). Noduri: fetele diagramei Voronoi (siturile). Arce:

daca celulele (fetele diagramei Voronoi corespunzatoare) au o muchiecomuna =⇒

• Triangulare TP (numita triangulare Delaunay)

− Propozitie. Fie T o triangulare a lui P. Atunci T este o triangulare De-launay daca si numai daca pentru orice triunghi din T cercul circumscrisnu contine ın interiorul sau niciun punct al lui P.

− Teorema. O triangulare este legala daca si numai daca este o triangulareDelaunay.

− Teorema. Orice triangulare unghiular optima este o triangulare Delau-nay. Orice triangulare Delaunay maximizeaza cel mai mic unghi, compa-rativ cu toate triangularile lui P.

− Intrebare: Cum “functioneaza” aceasta constructie cand punctele din Psunt (de exemplu) varfurile unui patrat?

39

7.4 Un algoritm eficient

Algoritmul lui Fortune [1987]

− Complexitate: O(n log n).

− Principiu (paradigma): sweep line / linie de baleiere.

− Inconvenient: la ıntalnirea unui varf al diagramei, linia de baleiere nu aıntalnit ın ca toate siturile (puncte din P) care determina acest varf!

− Adaptare: nu retinem informatia legata de intersectia dintre linia debaleiere si diagrama, ci doar informatia legata de partea diagramei care numai poate fi influentata de punctele situate de dincolo de linia de baleiere.

− Concepte:

– beach line / linie parabolica

– site event / eveniment de tip locatie (apare un arc de parabola)

– circle event / eveniment de tip cerc (dispare un arc de parabola)

AlgoritmulInput. O multime de situri P = {p1, . . . , pn} de situri ın plan.Output. Diagrama Voronoi Vor(P) ın interiorul unui bounding box, descrisa

printr-o lista dublu ınlantuita D.

1. Initializari: coada de evenimente Q ← P (preprocesare: ordonare dupay), statut (arbore balansat) T ← ∅; lista dublu ınlantuita D ← ∅.

2. while Q 6= ∅

3. do elimina evenimentul cu cel mai mare y din Q

4. if evenimentul ev este un eveniment de tip sit

5. then ProcessEvSit(pi), cu pi=ev

6. else ProcessEvCerc(γ), cu γ = arc(ev) ∈ T

7. Nodurile interne ınca prezente ın T corespund semidreptelor diagrameiVoronoi. Considera un bounding box care contine toate varfurile diagrameiVoronoi ın interiorul sa si leaga semidreptele de acest bounding box, prinactualizarea corespunzatoare a lui D.

8. Traverseaza muchiile pentru a adauga celulele diagramei si pointeri cores-punzatori.

Procedura ProcessEvSit (pi)

1. Daca T este vida, insereaza pi si revine, daca nu continua cu 2.−5.

2. Cauta ın T arcul α situat deasupra lui pi. Daca frunza reprezentand αare un pointer catre un eveniment de tip cerc ev din Q, atunci ev este oalarma falsa si trebuie sters.

3. Inlocuieste frunza lui T care reprezinta α cu un subarbore cu trei frunze:cea din mijloc retine situl pi si celelalte doua situl pj asociat lui α. Memo-reaza perechile reprezentand punctele de racord ın doua noduri interne.Efectueaza rebalansari ın T , daca este necesar.

40

4. Genereaza noi ınregistrari de tip semi-muchie ın structura diagramei Voro-noi (D), pentru muchiile care separa celulele V (pi) si V (pj), corespunzandcelor doua noi puncte de racord.

5. Verifica tripletele de arce consecutive nou create, pentru a verifica dacamuchiile corespunzatoare punctelor de racord se ıntalnesc. Daca da, inse-reaza evenimente de tip cerc ın Q si adauga pointeri de la nodurile lui Tla evenimentele corespunzatoare din Q.

Procedura ProcessEvCerc (γ)

1. Sterge frunza γ ∈ T care corespunde arcului de cerc α care dispare. Actu-alizeaza ın nodurile interne perechile care corespund punctelor de racord.Efectueaza rebalansari ın T , daca este necesar. Sterge toate evenimentelede tip cerc care ıi corespund lui α (cu ajutorul pointerilor de la predece-sorul si succesorul lui γ ın T .

2. Adauga centrul cercului care determina evenimentul ca ınregistrare de tipvarf ın D. Creeaza ınregistrari de tip semi-muchie corespunzand nouluipunct de racord de pe linia parabolica si asigneaza pointeri corespunzatori.

3. Verifica tripletele de arce consecutive nou create (care au fostii vecini ailui α ın centru), pentru a verifica daca muchiile corespunzatoare punctelorde racord se ıntalnesc. Daca da, insereaza evenimente de tip cerc ın Q siadauga pointeri de la nodurile lui T la evenimentele corespunzatoare dinQ.

Rezultate principale

− Teorema. Diagrama Voronoi a unei multimi de n situri poate fi determi-nata cu un algoritm de tip line sweep de complexitate O(n log n), folosindO(n) spatiu de memorie.

− Teorema. Triangularea Delaunay a unei multimi de n situri poate fideterminata cu un algoritm de tip line sweep de complexitate O(n log n),folosind O(n) spatiu de memorie.

7.5 Exercitii, probleme, aplicatii

Exercitiul 7.1 Determinati, folosind metoda diagramelor Voronoi, triangula-rea Delaunay pentru multimea formata din punctele A = (3, 5), B = (6, 6),C = (6, 4), D = (9, 5) si E = (9, 7).

Exercitiul 7.2 Determinati numarul de semidrepte continute ın diagrama Vo-ronoi asociata multimii de puncte M = {A0, . . . , A5, B0, . . . , B5, C0, . . . , C5},unde Ai = (i+ 1, i+ 1), Bi = (−i, i) si Ci = (0, i), pentru i = 0, . . . , 5.

Exercitiul 7.3 Dati exemplu de multimiM1 siM2 din R2, fiecare avand cate 4puncte, astfel ca, pentru fiecare dintre ele, diagrama Voronoi asociata sa continaexact 3 semidrepte, iar diagrama Voronoi asociata luiM1∪M2 sa contina exact6 semidrepte.

Exercitiul 7.4 Fie punctele A1 = (5, 1), A2 = (7,−1), A3 = (9,−1), A4 =(7, 3), A5 = (11, 1), A6 = (9, 3). Dati exemplu de multime de doua puncte{A7, A8} cu proprietatea ca diagrama Voronoi asociata multimii {A1, . . . , A8}are exact 4 muchii de tipul semidreapta (explicati constructia facuta).

Exercitiul 7.5 Demonstrati ca daca punctele din multimea P nu sunt coliniare,diagrama Voronoi Vor(P) nu poate contine drepte.

41

Bibliografie

[1] M. de Berg, M. van Kreveld, M. Overmars si O. Schwarzkopf,Computational Geometry, Algorithms and Applications, Sprin-ger, 2000.

[2] S. Devadoss, J. O’Rourke, Discrete and Computational Geometry, Prince-ton University Press, 2011.

[3] B. Gartner, M. Hoffmann, Computational Geometry. Note de curs, ETHZurich. http://www.ti.inf.ethz.ch/ew/courses/CG13/lecture/cg-2013.pdf.

[4] D. Lee, F. Preparata,Computational Geometry - A Survey, IEEE Transac-tions on Computers, 33 (1984), 1072-1101.

[5] F. Preparata si M. Shamos, Computational Geometry: An Introduction,Springer, 1985.

——————————————————————————————-

[6] L. Badescu, Geometrie, Editura Universitatii Bucuresti, 2000.

[7] M. do Carmo, Differential Geometry of Curves and Surfaces, Prentice Hall,1976.

[8] Gh. Galbura si F. Rado, Geometrie, Editura Didactica si Pedagogica, Bu-curesti, 1979.

[9] A. Gray, Modern Differential Geometry of Curves and Surfaces withMathematica, CRC Press, 1999.

[10] I. Hirica, S. Leiko, L. Nicolescu, G. Pripoae, Geometrie diferentiala. Pro-bleme. Aplicatii, Bucuresti, 1999.

[11] M.I. Munteanu, Algoritmi geometrici 2D si aplicatii ın CAGD, Editura Uni-versitatii ”Al. I. Cuza” Iasi, 2005.

[12] L. Nicolescu, Curs de geometrie, Bucuresti, 2002.

[13] L. Ornea si A. Turtoi, O introducere ın geometrie, Editura Theta, Bucuresti,2000.

[14] M.S. Stupariu, Geometrie analitica, Bucuresti, 2008.

42

Anexa A

Proiecte

1. Acoperirea convexa a unui poligon arbitrar.

Input: Un poligon P din R2.

Output: Varfurile acoperirii convexe Conv(P) (determinate ın timp liniar).Reprezentare grafica.

2. Invarianta acoperirii convexe la transformari afine.

Input: O multime P din R2, o transformare afina ϕ : R2 → R2.

Output: Acoperirea convexa a imaginii lui P prin ϕ (coincide cu imaginea luiConv(P) prin ϕ). Reprezentare grafica − ilustreaza cat mai sugestiv proprieta-tea de invarianta la transformari afine a acoperirii convexe.

3. Pozitia unui punct fata de un poligon convex.

Input: Un poligon convex P din R2, un punct A ∈ R2.

Output: Precizeaza pozitia lui A fata de P (ın interior, pe laturi, ın exterior),folosind o ımpartire convenabila pe sectoare. Reprezentare grafica.

4. Poligon convex si punct exterior.

Input: Un poligon convex P din R2, un punct A ∈ R2 ın exteriorul lui P.

Output: Determina varfurile acoperirii convexe Conv(P ∪ {A}) (ca lista ordo-nata, parcursa ın sens trigonometric). Reprezentare grafica.

5. Poligoane cu laturi paralele.

Input: Doua dreptunghiuri / poligoane convexe P,Q din R2, disjuncte, avandlaturile paralele.

Output: Determina varfurile acoperirii convexe Conv(P∪Q) (ca lista ordonata,parcursa ın sens trigonometric). Reprezentare grafica.

6. Cercuri.

Input: O multime de cercuri C1, . . . , Cq de raza 1, disjuncte, din planul R2 (suntindicate centrele cercurilor), un punct A ∈ R2.

Output: Precizeaza pozitia lui A fata de Conv(C1 ∪ . . . ∪ Cq). Reprezentaregrafica.

43

7. Triangulari ale poligoanelor − invarianta la transformari afine

Input: Un poligon P din planul R2, o transformare afina ϕ : R2 → R2.

Output: Construieste o triangulare TP a lui P si imaginea acesteia prin ϕca triangulare a lui ϕ(P). Reprezentare grafica − ilustreaza cat mai sugestivmodificarea triangularilor poligoanelor dupa aplicarea unei transformari afine.

8. Pozitia unui punct fata de un poligon

Input: Un poligon P din planul R2, un punct A ∈ R2.

Output: Determina o triangulare TP a lui P. Precizeaza pozitia lui A fata deP (ın exterior, pe laturi, ın interior). In cazul ın care este un punct interior,indica triunghiul din TP caruia A ıi apartine.

9.* Vizibilitate

Input: Un poligon P, un punct A ın interiorul lui P.

Output: Determina, folosind o triangulare TP a lui P, regiunea lui P care estevizibila din A. Reprezentare grafica.

10. Triangulari ale multimilor de puncte − invarianta la transformariafine

Input: O multimeM de puncte, reprezentand varfurile unui triunghi si puncteın interiorul acestuia.

Output: Construieste o triangulare TM a lui M si imaginea acesteia prin ϕca triangulare a lui ϕ(M). Reprezentare grafica − ilustreaza cat mai sugestivmodificarea triangularilor multimilor de puncte dupa aplicarea unei transformariafine.

11. Pozitia unui punct fata de o triangulare

Input: O multimeM de puncte, reprezentand varfurile unui triunghi si puncteın interiorul acestuia, un punct A ∈ R2.

Output: Determina o triangulare TM a lui M. Precizeaza pozitia lui A fatadeM (ın exterior, pe laturi, ın interior). In cazul ın care este un punct interior,indica triunghiul din TM caruia A ıi apartine.

12.* Echivalenta triangularilor

Input: O multime M de puncte, doua triangulari TM, T ′M ale lui M.

Output: Precizeaza daca cele doua triangulari sunt echivalente, i.e. pot fi trans-formate una intr-alta ıntr-un numar finit de pasi, prin aplicarea unor modificaride tip ”flip”. Reprezentare grafica.

44