Diagrame VoronoiDigrama Voronoi este o structur geometric adaptabil. Are numeroase aplicaii in fizic , astronomie, robotic si in geografia social. Urmeaz sa fie prezentate cteva definiii si proprieti de baz necesare in construcia digramei Voronoi. n cel mai simplu caz avem o muline de N puncte numite locaii sau puncte Voronoi. Fiecrui punct ii va corespunde o celula Voronoi, aceasta fiind formata din toate punctele care au locaia Voronoi respectiv cea mai apropiat. Segmentele ce contureaz celule Voronoi sunt formate de punctele echidistante dintre dou locaii. Nodurile Voronoi sunt punctele echidistante ntre trei sau mai multe locaii i pot fi privite ca punctele comune ale segmentelor ce contureaz diagramele Voronoi.

Fig. 1. Exemplu de diagram Voronoi

Notm distana Euclidian dintre punctele p i q prin dist(p,q) definit astfel:dist ( p, q ) = ( x p x q ) 2 + ( y p y q ) 2

(1)

Fie P = { p1 , p 2 , , p n } un set de n puncte distincte din plan, care reprezint locaiile Voronoi. Definim diagrama Voronoi a mulimii P drept divizarea planului n n celule, cte una pentru fiecare punct din P, cu proprietatea c un punct q aparine unei

celule corespunztoare unei locaii p i dac i numai dac dist ( p i , q) < dist ( p j , q ) , oricare ar fi p j P cu i j . Notm diagrama Voronoi a lui P cu Vor(P), iar celula Voronoi ce corespunde unei locaii p i cu V ( p i ) . Pentru studierea n detaliu a digramei Voronoi am ales doar o singur celul. Pentru dou puncte p si q, mediatoarea segmentuluip q

mparte planul n dou

semiplane. Semiplanele ce conin punctele p, respectiv q sunt notate cu h(p,q), respectiv cu h(q,p). Un punct r h( p, q ) dac dist ( r , p ) < dist ( r , q) . De aici rezult i observaia:V ( pi ) = 1j ,i j h( pi , p j ) n

(2)

Drept urmare V ( p i ) este intersecia a n 1 semiplane, deci o regiune convex, deschis i mrginit de cel mult n 1 vrfuri i cel mult n 1 laturi.. Deci digrama Voronoi este o divizare a planului a crei laturi sunt linii drepte. Pentru cazul n care toate locaiile sunt puncte coliniare, avem urmtoarea teorem: Teorema 1 Fie P o mulime de n locaii n plan. Dac toate locaiile sunt coliniareor or atunci V (P ) const din n-1 paralele. Altfel, V (P ) este conectat i laturile sale

sunt fie segmente de dreapt sau semidrepte. Pentru a gsi complexitatea diagramei, trebuie analizate numrul de laturi si numrul de vrfuri. Din moment ce sunt n locaii i fiecare celul Voronoi are cel multor n 1 vrfuri i laturi, complexitatea lui V (P ) are cel mult ordin ptratic.

Fig. 3.2. a)Celul Voronoi; b) Cazul locaiilor coliniare

Teorema 23n 6 .

Pentru n 3 , numrul de vrfuri ale diagramei Voronoi pentru o

mulime de n locaii n plan este cel mult 2n 5 , iar numrul de laturi este cel mult Dac locaiile sunt coliniare, demonstraia rezult imediat din Teorema

DEMONSTRAIE.

3.1 deci se va presupune c locaiile sunt necoliniare. Se folosete formula lui Euler care spune c pentru orice graf plan conex cu mv noduri, me arce i m f fee are loc relaia:mv me + m f = 2

(3)

or or Nu putem aplica direct formula pentru V (P ) , deoarece V (P ) are laturi infinite i

nu formeaz un graf propriu. Pentru a remedia situaia, se adaug un vrf n plus mulimiior de vrfuri, la infinit, notat v i unim toate semidreptele lui V (P ) cu acest vrf. Se

obine astfel un graf plan conex cruia i vom aplica formula lui Euler, rezultndor urmtoarea relaie ntre nv , numrul de vrfuri ale V (P ) , ne , numrul de laturi ale V (P ) si n, numrul de locaii: or

(4) n plus, fiecare latur n graful extins are exact dou vrfuri, astfel, dac se sumeaz gradele tuturor vrfurilor, se va obine de dou ori numrul laturilor. Pentru c fiecare vrf, inclusiv v are gradul cel puin 3, rezult c:2ne 3( nv +1)

(nv + 1) ne + n = 2

(5)

Fig. 3. Construirea vrfului v

Din cele dou relaii rezult, concluzia teoremei.

Muchiile mai pot fi caracterizate ca poriuni ale mediatoarelor segmentelor dintre perechi de locaii iar vrfurile sunt punctele de intersecie dintre aceste mediatoare. Dinor numrul ptratic de mediatoare rezult complexitatea liniar a V (P ) . Astfel, nu toate

mediatoarele definesc laturi in diagram i nu toate interseciile sunt vrfuri ale diagramei. Pentru a caracteriza mediatoarele care determin laturi sau vrfuri n viitoareaor diagram V (P ) dm urmtoare definiie:

Definiia 1

Pentru un punct q definim cel mai mare cerc gol al lui q raportat la P,

notat cu C P (q ) , cercul cu diametrul maxim care are centrul n q i nu conine nici o alt locaie a lui P n interiorul su.

Fig. 4. Cel mai mare cerc gol a unei locaii q

Teorema 3

or Pentru diagrama Voronoi V (P ) a unei mulimi de puncte P avem: V (P ) dac i numai dac frontiera celui mai or

(1) un punct q este vrf a lui

mare cerc gol C P (q ) conine cel puin 3 locaii; mediatoarea dintre locaiile p i i p j definete o latur a diagramei dac i numai dac exist un punct q pe mediatoare astfel ncat i p i i p j aparin frontierei cercului C P (q ) , iar nici o alt locaie nu aparine acestui cerc.