De ce asa? Pentru ca punctele de pe infasuratoarea convexa sunt cele mai departate de origine, deci dreptele lor duale sunt cele mai apropiate de origine. Va las placerea de a analiza cazurile particulare, de exemplu cele in care multimea de drepte nu defineste un poligon inchis in jurul originii, ci unul deschis (hint: originea nu apartine infasuratorii convexe a punctelor duale).

O alta tema de gandire este: ce se intampla in cazul limita cand trei sau mai multe puncte sunt coliniare pe infasuratoarea convexa?

O alta tema de gandire este: ce se intampla in cazul limita cand trei sau mai multe puncte sunt coliniare pe infasuratoarea convexa?
 
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.
 
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".
 
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:
 
* Pentru fiecare i afla poligonul lui Pi 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
 
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.
 
Algoritmul pentru aflarea poligonului Voronoi al lui Pi este:
 
* Translateaza tot sistemul pentru a suprapune Pi peste origine !!
* Construieste colectia de n+3 drepte D1, D2, ..., Dn+3
* Rezolva infasuratoarea convexa si afla colectia de drepte vizibile din origine, fie ele V1, V2, ..., Vk (in ordine trigonometrica)
* Calculeaza varfurile poligonului Voronoi: Wi = Vi-1 int. cu Vi
* Retranslateaza originea si {Wi} pentru a duce Pi in pozitia originala
 
!! Cum se translateaza colectia de puncte este clar: din fiecare Pj.x se
scade Pi.x si din fiecare Pj.y se scade Pi.y; in acest fel Pi.x si pi.y
devin 0. Cum translatam laturile dreptunghiului (sau in cazul general o
dreapta oarecare) ? Daca ecuatia originala era ax+by+c=0, scriem aceasta
ecuatie relativ la Pi.x si Pi.y:
 
Fie t=a*Pi.x + b*Pi.y + c
a(x-Pi.x) + b(y-Pi.y) + t =0
 
Deci noua ecuatie este
ax + by + t =0
 
Cu alte cuvine, pentru a translata dreapta cu -Pi.x si -Pi.y, scadem din c valoarea a*Pi.x + b*Pi.y.
 
Complexitatea noului algoritm este (pentru un singur poligon):
* O(N) translatia
* O(N) constructia dreptelor
* O(N) dualizarea
* O(N log N) infasuratoarea convexa
* O(N) constructia poligonului Voronoi
* O(N) translatia inapoi
 
Pentru intreaga diagrama complexitatea este O(N^2 log N).
Programul este implementat si testat. Nu este chiar scurt daca il construiti de la 0, dar daca puteti scrie fara greseala rutinele pentru infasuratoare convexa, intersectii de drepte si asa mai departe, cam in 1.5 - 2 ore ar trebui sa puteti programa toata povestea asta.