h2. Diagrame Voronoi

In primul rand ce sunt alea. Sa consideram un poligon convex (pentru simplitate vom lua un dreptunghi) si n puncte P1, P2, ..., Pn in acel dreptunghi. Poligonul Voronoi al unui punct Pi este format din multimea acelor puncte P din dreptunghi care sunt mai aproape de Pi decat de orice alt punct Pj. Impartirea dreptunghiului in poligoane se numeste diagrama Voronoi.

In primul rand ce sunt alea. Sa consideram un poligon convex (pentru simplitate vom lua un dreptunghi) si n puncte P ~1~ , P ~2~ , ..., P ~n~ in acel dreptunghi. Poligonul Voronoi al unui punct P ~i~ este format din multimea acelor puncte P din dreptunghi care sunt mai aproape de P ~i~ decat de orice alt punct P ~j~ . Impartirea dreptunghiului in poligoane se numeste diagrama Voronoi.

Exemple:
Pentru n=1, exista un singur poligon Voronoi care este intregul dreptunghi.

Pentru n=2, ducem mediatoarea lui P1 si P2 si o intersectam cu dreptunghiul, obtinand doua poligoane. Punctele din poligonul lui P1 sunt mai aproape de P1 decat de P2 si invers.
Pentru n=3, ducem cele trei mediatoare ale segmentelor P1P2, P2P3 si P3P1. Mediatoarele se intalnesc intr-un punct (cercul cercului circumscris) si le prelungim pana intersecteaza dreptunghiul. Pentru n=3, cand P1 P2 si P3 sunt coliniare, dreptunghiul este sectionat in trei "felii".

Pentru n=2, ducem mediatoarea lui P ~1~ si P ~2~ si o intersectam cu dreptunghiul, obtinand doua poligoane. Punctele din poligonul lui P ~1~ sunt mai aproape de P ~1~ decat de P ~2~ si invers.
Pentru n=3, ducem cele trei mediatoare ale segmentelor P ~1~ P ~2~, P ~2~ P ~3~ si P ~3~ P ~1~ . Mediatoarele se intalnesc intr-un punct (cercul cercului circumscris) si le prelungim pana intersecteaza dreptunghiul. Pentru n=3, cand P ~1~ P ~2~ si P ~3~ sunt coliniare, dreptunghiul este sectionat in trei "felii".

Se poate defini diagrama Voronoi si fara constrangerile dreptunghiului, adica pe intregul plan xOy, dar in acest caz poligoanele sunt "deschise" (se duc la infinit). In orice caz, nu este greu de demonstrat ca poligoanele Voronoi sunt convexe.

O metoda "barbara" de a afla poligoanele Voronoi porneste de la observatia ca daca duc mediatoarea dintre Pi si Pj, atunci in mod sigur punctele de partea lui Pj nu au cum sa fie in poligonul lui Pi, pentru ca sunt mai aproape de Pj decat de Pi. Dec algoritmul este:

O metoda "barbara" de a afla poligoanele Voronoi porneste de la observatia ca daca duc mediatoarea dintre P ~i~ si P ~j~ , atunci in mod sigur punctele de partea lui P ~j~ nu au cum sa fie in poligonul lui P ~i~ , pentru ca sunt mai aproape de P ~j~ decat de P ~i~ . Dec algoritmul este:

* Pentru fiecare i afla poligonul lui Pi astfel:

* Pentru fiecare i afla poligonul lui P ~i~ astfel:

* Porneste cu un poligon egal cu intregul dreptunghi
* Pentru fiecare j<>i

* Intersecteaza poligonul cu mediatoarea lui PiPj si "arunca" bucata din partea lui Pj
* Poligonul ramas este poligonul lui Pi

* Intersecteaza poligonul cu mediatoarea lui P ~i~ P ~j~ si "arunca" bucata din partea lui P ~j~
* Poligonul ramas este poligonul lui P ~i~

Complexitatea este O(N^3), iar numarul de cazuri particulare este mare. In continuare revenim la principiul dualitatii si la problema de mai sus, a vizibilitatii unor drepte dintr-un punct.

Complexitatea este O(N^3^), iar numarul de cazuri particulare este mare. In continuare revenim la principiul dualitatii si la problema de mai sus, a vizibilitatii unor drepte dintr-un punct.

Sa ne imaginam punctul Pi inconjurat de n+3 drepte: cele n-1 mediatoare ale segmentelor PiPj si cele 4 laturi ale dreptunghiului. Atunci poligonul Voronoi al lui Pi are drept laturi exact segmentele "vizibile" din Pi ale acestor n+3 drepte. Si dupa cum am vazut mai sus, aceasta problema se reduce la infasuratoare convexa. Trebuie avut grija pentru ca in rezolvarea de mai sus a problemei vizibilitatii am presupus ca punctul de observare este originea. Deci in cazul general va trebui sa translatam totul in asa fel incat Pi sa ajunga in origine, pentru a putea aplica principiul dualitatii. Un ultim aspect care trebuie abordat este acela ca problema de mai sus indica numai care drepte sunt vizibile, nu exact ce segmente din acele drepte.