Diagrame Voronoi

(Categoria Algoritmi, autor Catalin Francu)

<p>Multumiri lui Mihai Popa care a cotrobait prin arhiva de mesaje si a gasit mesajul de mai jos. El se refera la principiul dualitatii si am adaugat o bucata despre diagramele Voronoi.</p>

Principiul dualitatii

<p>Daca tot n-am mai prea trimis probleme, hai sa va impartasesc si voua ceva din adanca intelepciune care mi-a fost bagata cu pompa pe gat la MIT. Scriu sub impulsul momentului, asa ca nu va asteptati la prea multa coerenta.</p>

<p>Incep cu observatia ca "Geometrie Computationala" nu suna prea romaneste, insa pe de alta parte "Geometrie Analitica" nu suna prea corect, fiindca nu e totuna cu ce se face (facea?) in clasa a XI-a de liceu.</p>

<p>Sa pornim de la urmatoarea problema: Avem o colectie de N drepte in plan, oricare doua neconfundate, astfel incat nici una din ele nu trece prin origine. Sa se indice care din drepte sunt vizibile din origine.</p>

<p>Un algoritm decent functioneaza in O(N^2), astfel: ia fiecare dreapta di, si o intersecteaaza cu fiecare din celelalte drepte dj. In acest fel, di se imparte in doua semidrepte, din care numai una este vizibila din origine, cealalta fiind obturata de catre dj. In felul acesta tot intersectam semidrepte peste semidrepte, si vedem daca in final ramanem cu vreun segment vizibil din origine. Desigur, pe parcurs apare tot tacamul de cazuri particulare: drepte verticale, drepte orizontale, erori de calcul, radicali, distante etc. Sper ca v-am scarbit destul ca sa vreti sa aflati si o implementare mai eleganta.</p>

<p>Vom prezenta un algoritm foarte dragut si foarte cunoscut (in final) care rezolva problema in O(N log N). Facem intai urmatoarea conventie. De vreme ce dreptele nu trec prin origine, ele au ecuatii de forma ax+by+c=0, cu c<>0. Atunci le vom aduce pe toate la forma ax+by+1=0 (evident, impartind prin c).</p>

Si-acum sa vedem ce este principiul dualitatii. El asociaza fiecarei drepte de forma ax+by+1=0 un punct de coordonate (a,b) in plan. Vom numi spatiul dreptelor "spatiu primal", iar spatiul punctelor corespunzatoare "spatiu dual". De aici decurg o multime de observatii foarte interesante, din care nici eu nu-mi aduc aminte decat cateva:

1. Oricarui punct din spatiul dual ii corespunde o dreapta in spatiul primal, si ce este mai interesant, oricaror doua puncte distincte din spatiul dual le corespund drepte distincte in spatiul dual
2. Oricarei drepte din spatiul primal ii corespunde un punct in spatiul dual. Exceptia o constituie dreptele care trec prin origine, pentru ca ele au c=0 si nu pot fi normalizate. Totusi, daca extindem spatiul dual ca sa contina si puncte de la infinit, atunci fiecarei drepte care trece prin origine in spatiul primal ii corespunde un punct de la infinit in spatiul dual. Cu asta, bijectia intre cele doua spatii este completa.
3. Sa ne inchipuim acum doua drepte in spatiul primal, care se
   intersecteaza intr-un punct: ax+by+1=0, dx+ey+1=0. Fie (p,q) punctul lor
   de intersectie, care are proprietatile:
   <p>ap+bq+1=0
   dp+eq+1=0</p>
   <p>Sa dualizam acum cele doua drepte. Obtinem punctele (a,b) si (d,e). Sa analizam ecuatia dreptei care trece prin aceste doua puncte:</p>
   <p>x-a  y-b
   --- - --- = 0 (*)
   d-a  e-b</p>
   <p>Dar ap+bq+1=dp+eq+1 --> (d-a)p + (e-b)q = 0 --> (d-a) = -(e-b)q/p</p>
   <p>Inlocuind asta in (*) si reducand numitorul (e-b) deducem:</p>
   <p>(x-a)p/q + (y-b) = 0 ==> px+qy-(pa+qb)=0, dar pa+qb=-1, deci ecuatia
   dreptei este:</p>
   <p>px+qy+1=0 !!!</p>
   <p>Cu alte cuvinte, daca dreptele d1 si d2 se taie in punctul P, atunci dualizand totul obtinem punctele dual(d1) si dual(d2), care determina tocmai dreapta dual(P). Asta mai arata si ca nu e obligatoriu ca in spatiul primal sa avem drepte si in spatiul dual sa avem puncte, ci putem dualiza orice, oriunde ( :) ).</p>
4. La fel se demonstreaza reciproca: doua puncte care determina o dreapta se dualizeaza in doua drepte care se intersecteaza intr-un punct.
5. Generalizarea este si mai draguta: Un fascicol de drepte (pentru cei care nu prea dau pe la mate, asta inseamna o colectie de drepte care se intalnesc in acelasi punct) se dualizeaza intr-o multime de puncte, toate coliniare. Se demonstreaza folosind acelasi punct (p,q) pentru toate dreptele.
6. Dar o colectie de drepte paralele? O sa radeti, dar se dualizeaza tot intr-o multime de puncte coliniare. Daca nu ma-nsel, dreapta care contine aceste puncte coliniare inteapa originea. Demonstratia se poate face fie prin calcul direct, fie observand ca in fond o colectie de
   drepte paralele este un fascicol de drepte care se intalnesc la infinit (Euclid sa traiasca!)
7. Sa luam dreapta ax+by+1=0. Daca normalizam dreapta (impartind prin sqrt(a*a+b*b)), aflam ca distanta de la dreapta la origine este 1/sqrt(a*a+b*b). Dualizand dreapta, obtinem punctul (a,b), care este situat la distanta sqrt(a*a+b*b) de origine. Mai expresiv, daca dreapta este la distanta d de origine, punctul dual este la distanta 1/d de origine. Mai interesant este ca punctul dual, originea si piciorul perpendicularei din origine pe dreapta sunt coliniare. E destul de usor
   de demonstrat, daca nu v-ati luat inca un creion si o hartie e cazul sa o faceti, altfel cred si eu ca va plictisiti :).