MODULUL VI.

DIAGRAMA VORONOI

Tema are ca scop prezentarea detaliată a uneia din construcŃiile foarte utile ale Geometriei computaŃionale şi anume diagrama Voronoi a unei mulŃimi de puncte din plan. ProprietăŃi remarcabile ale acesteia permit abordarea şi rezolvarea unor probleme de proximitate.

StudenŃii vor întocmi o temă de casă care constă în rezolvarea

problemelor şi exerciŃiilor propuse.

Cuvinte cheie: diagrama Voronoi, graf planar, regiuni nemărginite, principiul divide et impera. IndicaŃii de studiere a temei: Timpul minim pe care trebuie să-l acordaŃi studierii acestui modul este de 3 ore. Se citeşte cu atenŃie şi se notează ideile principale, ecuaŃiile matematice, se aprofundează noŃiunile subliniate. Se parcurg întrebările de control şi testele de verificare. Se studiază problemele şi exerciŃiile rezolvate. Se rezolvă exerciŃiile propuse. Dacă nu se înŃeleg rezolvările sau nu pot da soluŃii unor probleme propuse se restudiază subiectul în cauză. Cuprins 6.1. Diagrama Voronoi: definiŃie, exemple 6.2. ProprietăŃi ale diagramei Voronoi 6.3. AplicaŃie: cele mai apropiate perechi de puncte ale unei mulŃimi M 6.4. Graful planar definit de diagrama Voronoi a unei mulŃimi M 6.5. Metoda divide et impera pentru construirea diagramei Voronoi a unei mulŃimi M de puncte din plan 6.6.Teme pentru casă

După parcurgerea şi însuşirea acestei teme, studentul va cunoaşte:

• NoŃiunea de diagramă Voronoi.

• ProprietăŃi ale diagramei Voronoi.

• Algoritmul de construire a diagramei Voronoi.

• AplicaŃii

6.1. DIAGRAMA VORONOI: DEFINIłIE, EXEMPLE

DEFINIłIE

Dată fiind o mulŃime M de puncte P1, P2, ..., Pn din plan, fiecare punct Pi determină o regiune ρi în care se găsesc punctele care sunt mai apropiate de punctul Pi decât de celelalte puncte ale mulŃimii. Întregul plan va fi împărŃit între aceste regiuni care, evident, nu pot avea puncte interioare comune. Această împărŃire se numeşte diagrama Voronoi a mulŃimii M. Următoarele exemple oferă o introducere în problematica diagramelor Voronoi.

EXEMPLE

a) Considerăm mulŃimea M constituită din două puncte A şi B. Mediatoarea segmentului AB împarte planul în două regiuni. În regiunea în care se află punctul A sunt punctele care sunt mai apropiate de A decât de B iar în regiunea cealaltă sunt punctele mai apropiate de B decât de A. Pe mediatoare, frontiera dintre cele două regiuni, se află punctele situate la distanŃe egale faŃă de A şi B.

M N

P

a)

B A

O B

C

A

b)

O

A

B

C

D

O

c)

O B

C

A

d)

b) Dacă mulŃimea M este constituită din trei puncte A, B şi C atunci mediatoarele laturilor triunghiului ABC se întâlnesc în punctul O care este centrul cercului circumscris, singurul punct din plan care se află la aceeaşi distanŃă de cele trei puncte A, B, C. Aceste trei mediatoare, împreună cu punctul O, delimitează cele trei regiuni ale diagramei Voronoi. c) Se consideră mulŃimea M constituită din patru puncte A, B, C şi D aflate pe un cerc cu centrul în punctul O. Mediatoarele coardelor se întâlnesc în punctul O. Ele delimitează cele partu regiuni ale diagramei Voronoi. De fapt regiunea cuprinsă între semidreptele ce pornesc din O şi au drept suport mediatoarele segmentele AB şi AC este formată din punctele care sunt mai apropiate de A decât de B şi de C. Dar mediatoarea corzii AD, care trece şi ea prin punctul O, împarte planul în două regiuni astfel că regiunea lui A conŃine întreaga mulŃime a punctelor care sunt mai apropiate de A decât de B şi de C. Punctul O este singurul punct din plan care este egal depărtat de cele patru puncte. Este uşor de văzut că această diagramă se poate generaliza la cazul când mulŃimea M este constituită din vârfurile unui poligon inscriptibil. d) Considerăm mulŃimea M constituită din punctele A, B, C şi O în care triunghiul ABC este ascuŃitunghic iar O este centrul cercului circumscris triunghiului ABC, în care se întâlnesc mediatoarele laturilor triunghiului. Mediatoarele segmentelor OA şi OB se întâlnesc în punctul M situat pe mediatoarea laturii AB. Punctul M este centrul cercului circumscris triunghiului AOB. Analog, punctele N, respectiv P sunt centrele cercurilor circumscrise triunghiurilor AOC respectiv BOC. Triunghiul MNP delimitează regiunea Voronoi corespunzătoare punctului O. Aceasta este singura regiune mărginită a diagramei.

6.2. PROPRIETĂłI ALE DIAGRAMEI VORONOI

1). Regiunile

Fiecare regiune a diagramei Voronoi este o mulŃime convexă. Într-adevăr, fie Pi un punct al mulŃimii M = {P1, P2, ...,Pn} şi ρi regiunea corespunzătoare punctului Pi. Pentru fiecare indice j ≠ i se consideră mediatoarea segmentului PiPj şi πj semiplanul în care se află punctul Pi în raport cu această mediatoare.

Regiunea ρi este intersecŃia tuturor semiplanelor πj. Cum intersecŃia unor mulŃimi convexe este convexă reyultă că regiunea ρi este o mulŃime convexă. Evident că frontiera unei regiuni este constituită din semidrepte sau segmente de dreaptă. Regiunile mărginite ale diagramei Voronoi sunt poligoane convexe.

2). Muchiile

Orice muchie a diagramei Voronoi, mărginită sau nemărginită, separă două regiuni bine determinate ρi şi ρj corespunzătoare punctelor Pi şi Pj respectiv. MulŃimea punctelor acestei muchii este intersecŃia celor două regiuni. Punctele muchiei sunt la egală distanŃă de punctele Pi şi Pj.

3) Vârfurile

Orice vârf G al diagramei Voronoi este intersecŃia a cel puŃin trei regiuni. Într-adevăr, dacă punctul G ar fi capătul comun al numai două muchii atunci ele ar mărgini două regiuni. Una din cele două regiuni nu va fi atunci convexă deoarece din cele două unghiuri formate de muchii unul este mai mare decât 180*. Punctul G nu poate fi capătul unei singure muchii deoarece scoŃând această muchie se obŃine o mulŃime care nu este convexă. Dacă numărul muchiilor incidente în punctul G este r ≥ 3 atunci punctul G este comun pentru r regiuni care corespund la r puncte ale mulŃimii M. Ordonând aceste muchii în sens trigonometric sau invers, unghiul dintre două muchii consecutive trebuie să fie mai mic decât 180* deoarece între ele se află o singură regiune. Aceste puncte fiind egal depărtate de punctul G înseamnă că G este centrul cercului care conŃine toate aceste r puncte. Rezultă că dacă mulŃimea M nu are patru puncte conciclice atunci în orice vârf al diagramei Voronoi sunt incidente exact trei muchii.

4). Poligonul inscriptibil corespunzător unui vârf.

Dacă în vârful G al diagramei Voronoi sunt incidente r ≥ 3 muchii atunci G este punctul comun al regiunilor corespunzătoare la r puncte Q1, Q2, ...,Qr ale mulŃimii M. Deci punctul G fiind egal depărtat de cele r puncte, acestea se găsesc pe un cerc cu centrul în G.

În interiorul acestui cerc nu se află nici un punct al mulŃimii M. Într-adevăr, dacă în interiorul acestui cerc s-ar găsi un punct al mulŃimii M atunci punctul G ar fi mai apropiat de acest punct decât de cele r puncte şi deci G nu ar aparŃine regiunilor definite de cele r puncte.

5). Regiunile nemărginite ale diagramei Voronoi a mulŃimii M

Considerăm înfăşurătoarea convexă a mulŃimii M = {P1, P2, ..., Pn}. Aceasta este un poligon convex având drept vârfuri puncte ale mulŃimii M. Vom arăta că singurele regiuni nemărginite ale diagramei Voronoi sunt cele care corespund punctelor mulŃimii M situate pe frontiera acestui poligon. Fie Pi şi Pj situate pe o latură a poligonului care înfăşoară mulŃimea M. Dreapta PiPj împarte planul în două regiuni din care una, pe care o notăm π’ conŃine toate punctele mulŃimii M. Cercul cu centrul într-un punct H almediatoarei segmentului PiPj şi de rază egală cu HPi = HPj nu conŃine alte puncte ale mulŃimii M decât cele situate în segmentul de cerc situat însemiplanul π’. Dacă centrul H al cercului se deplasează pe mediatoare în direcŃia opusă semiplanului π’, deci către exteriorul înfăşurătoarei, în acest cerc vor rămâne din ce în ce mai puŃine puncte ale mulŃimii M. Fie H0 poziŃia punctului H pentru care interiorul cercului cu centrul în H0 nu conŃine nici un punct al mulŃimii M dar arcul PiPj conŃine astfel de puncte.

Pi

Pj H

H0

H

π’

Dacă punctul H se îndepărtează pe mediatoare dincolo de H0 atunci punctele Pi şi Pj, aflate la distanŃă egală de punctul H, sunt cele mai apropiate puncte ale lui M de punctul H. Deci punctul H se află pe frontiera care desparte regiunile Voronoi ale regiunilor Pi şi Pj. Aşadar regiunea Voronoi a unui punct al mulŃimii M situat pe frontiera înfăşurătoarei convexe a acesteia va avea muchii nemărginite. Deci regiunea este nemărginită. Reciproc, să considerăm un punct Pi al mulŃimii M a cărui regiune Voronoi are o muchie nemărginită d. Această muchie desparte regiunea lui Pi de regiunea unui alt punct Pj iar muchia d va avea ca suport mediatoarea segmentului PiPj. Cercul care prece prin punctele Pi şi Pj şi cu centrul pe semidreapta d nu poate avea în interior puncte ale mulŃimii M, în caz contrar aceste puncte ar fi mai apropiate de puncte ale lui d decât punctele Pi şi Pj. Dar depărtând la nesfârşit centrul cercului pe semidreapta d acest cerc, la limită conŃine toate punctele semiplanului determinat de dreapta PiPj şi în care se află semidreapta d. Prin urmare semiplanul opus semidreptei d va conŃine toate punctele mulŃimii M, adică segmentul PiPjse află pe frontiera înfăşurătoarei convexe a mulŃimii M.

6.3. APLICAłIE: CELE MAI APROPIATE PERECHI DE PUNCTE ALE UNEI MULłIMI M

Fie Pi un punct fixat al mulŃimii M şi Pj un punct aflat la distanŃă minimă de punctul Pi. Vom arăta că frontiera regiunii lui Pi conŃine o muchie care desparte această regiune de regiunea lui Pj. Pentru a dovedi acest lucru să notăm H mijlocul segmentului PiPj şi d mediatoarea acestui segment. Cercul cu centrul în Pi şi de rază PiH este tangent dreptei d. În interiorul acestui cerc nu se află nici un punct al frontierei regiunii lui Pi. Într-adevăr, dacă punctul N situat în interiorul cercului ar fi pe frontiera regiunii lui Pi atunci N se află pe o muchie a acestei regiuni, muchie ce o separă de regiunea Voronoi a unui alt punct Ph. Această muchie are ca suport mediatoarea segmentului PiPh şi deci PiN = NPh. Pe de altă parte PiN < PiH şi deci: PiPh ≤ PiN + NPh = 2PiN < 2PiH = PiPj. Acest rezultat contrazice ipoteza că punctul Pj se află la distanŃa minimă de Pi.

Aşadar interiorul cercului este în întregime în regiunea Voronoi a punctului Pi. Cum punctele de pe segmentul HPj sunt mai apropiate de Pj decât de Pi înseamnă că punctele acestui segment nu se află în regiunea Voronoi a lui Pi. Înseamnă că punctul H se află pe frontiera acestei regiuni. Punctul H nu poate fi vârf al acestei regiuni deoarece în acest caz cel puŃin una dintre muchiile incidente acestui vârf ar avea puncte în interiorul cercului având în vedere că unghiul dintre ele trebuie să fie strict mai mic decât 180*. În concluzie, punctele mulŃimii M care se află la distanŃa minimă de punctul fixat Pi se află printre punctele ale căror regiuni sunt despărŃite de regiunea lui Pi prin muchiile regiunii lui Pi. Căutând, pentru fiecare punct Pi al mulŃimii M punctele care sunt cele mai apropiate de punctul Pi găsim cele mai apropiate perechi de puncte ale mulŃimii M.

6.4. GRAFUL PLANAR DEFINIT DE DIAGRAMA VORONOI A UNEI MULłIMI M.

Diagrama Voronoi este aproape un graf planar şi chiar format din segmente de dreaptă. Singurul ei defect este că are muchii nemărginite. Vom modifica diagrama Voronoi astfel încât să devină un graf planar. Fie Γ un punct situat în afara cercului care conŃine toate muchiile mărginite ale diagramei Voronoi. Exteriorul acestui cerc fiind o mulŃime

Pi

N Ph

Pj

H

d

conexă punctul Γ se poate uni cu câte un punct de pe fiecare muchie nemărginită cu câte o curbă, astfel că aceste curbe să nu se întretaie şi nici una să nu taie vreo muchie mărginită a diagramei Voronoi. Se obŃine un graf planar dar care nu este format numai din segmente de dreaptă deoarece muchiile incidente în vârful Γ nu sunt în general segmente de dreaptă. Acest graf planar are un vârf în plus faŃă de diagrama Voronoi, anume vârful Γ. Dacă mulŃimea M are n puncte atunci tot n vârfuri are diagrama Voronoi dar graful planar corespunzător are n + 1 vârfuri. Complexitatea algoritmului de găsire a perechilor celor mai apropiate ale mulŃimii M = {P1, P2, ... ,Pn} Presupunem că am determinat diagrama Voronoi a mulŃimii M şi avem şi tabelul dublu conex al muchiilor grafului planar asociat. În această situaŃie putem parcurge conturul fiecărei regiuni a grafului, complexitatea acestei operaŃii fiind egală cu numărul muchiilor regiunii. Pentru un punct fixat Pi al mulŃimii M parcurgem lista muchiilor ce constituie frontiera regiunii punctului Pi. Aceste muchii despart regiunea punctului Pi de alte regiuni corespunzătoare unor alte puncte Pj ale mulŃimii M. Din proprietatea 5) rezultă că printre aceste puncte se află toate punctele mulŃimii M care se află la distanŃa minimă de punctul Pi. Pentru fiecare punct Pi al mulŃimii M se alcătuieşte lista punctelor celor mai apropiate puncte de punctul Pi precum şi distanŃa comună corespunzătoare. Din aceste liste se reŃin cele pentru care distanŃa este minimă. ObŃinem astfel lista tuturor perechilor de puncte ale mulŃimii M aflate la distanŃă minimă. În ce priveşte complexitatea algoritmului admitem faptul că frontiera unei regiuni poate avea tot atâtea muchii câte puncte are mulŃimea M, adică n. Ar rezulta că algoritmul are complexitatea n2. Totuşi Ńinem seamă că fiecare muchie este luată în calcul de exact două ori. Pe de altă parte, am dedus, din teorema lui Euler că numărul muchiilor şi al vârfurilor este de acelaşi ordin de mărime ca şi numărul regiunilor care este n. În concluzie dacă avem diagrama Voronoi a mulŃimii M = {P1, P2, ...,Pn) şi tabelul dublu conex al muchiilor grafului planar corespunzător atunci algoritmul de determinare a listei perechilor de puncte aflate la distanŃa minimă are complexitatea n.

6.5. METODA DIVIDE ET IMPERA PENTRU CONSTRUIREA DIAGRAMEI VORONOI A UNEI

MULłIMI M DE PUNCTE DIN PLAN Am arătat cum probleme de proximitate privind mulŃimi M de puncte din plan se rezolvă în timp liniar dacă se dispune de diagrama Voronoi a acestei mulŃimi. Sunt şi alte probleme a căror rezolvare presupune deja construită diagrama Voronoi. Pentru construirea diagramei se dispune de un algoritm de complexitate nlogn dacă se asumă ipoteza pe care am mai menŃionat-o şi anume că mulŃimea M nu are patru puncte pe acelaşi cerc. Prezentarea completă a acestui algoritm, cu detaliile demonstrării consistenŃei, nu face obiectul acestei expuneri. Ne mărginim să dăm o descriere sumară a paşilor algoritmului urmată de un exemplu de aplicare a acestuia. Algoritmul foloseşte principiul cunoscut sub numele divide et impera. Se împarte mulŃimea M în două submulŃimi, Ms şi Md, aproximativ egale ca număr de elemente, dar îndeplinind condiŃia că sunt separate printr-o linie verticală de abscisă x0: Punctele din mulŃimea Ms au abscisa strict mai mică decât x0 iar cele din mulŃimea Md au abscisa strict mai mare decât x0. Se continuă această diviziune până când se obŃin submulŃimi suficient de mici încât să se poată construi direct diagrama Voronoi a acestora, de exemplu dacă se ajunge la mulŃimi care au câte trei sau patru puncte. Numărul împărŃirilor succesive este log2n. După ce se obŃin diagramele Voronoi ale mulŃimilor de pe ultimul nivel, se cuplează două câte două şi se obŃin diagramele Voronoi ale submulŃimilor de pe nivelul imediat superior. Repetând acest proces se ajunge la diagrama Voronoi a mulŃimii M. Dificultatea algoritmului constă în cuplarea diagramelor Voronoi a două submulŃimi. Mai precis, folosindu-ne de diagramele Voronoi ale submulŃimilor Ms şi Md notate Vors şi Vord trebuie construită diagrama Voronoi a mulŃimii M, pe care o notăm Vor(M) Procesul de cuplare constă în adăugarea unor noi muchii precum şi eliminarea unora (sau porŃiuni) din muchiile celor două diagrame. Se folosesc înfăşurătoarele convexe ale celor două submulŃimi şi se consideră podul superior UsUd şi podul inferior LsLd în care Us şi Ls sunt puncte ale mulŃimii Ms iar Ud şi Ld sunt puncte ale mulŃimii Md. Se consideră mediatoarele mu şi ml mediatoarele acestor segmente. În continuare se parcurge un drum de sus în jos, de la mu la ml în paşii căruia se adaugă la diagramele Voronoi ale celor două submulŃimi

noi muchii şi se elimină unele din muchiile vechi sau porŃiuni ale acestora. Mediatoarea mu serveşte drept suport al muchiei Voronoi care desparte regiunea lui Us de regiunea lui Ud (acestea fiind puncte alăturate de pe înfăşurătoarea convexă a mulŃimii M, regiunile lor vor avea ca muchie comună o semidreaptă situată pe mediatoarea mu). Pe de altă parte, la distanŃă suficient de mare pe mediatoare ne aflăm în intersecŃia a două regiuni: regiunea Vors(Us) a lui Us din diagrama Vors şi regiunea Vord(Ud) cea a lui Ud din Vord. Mediatoarea va intersecta într-un punct bine determinat Qs frontiera regiunii Vors(Us) şi în punctul Qd frontiera regiunii Vord(Ud). Notăm Q0 pe cel cu ordonata mai mare. Punctul Q0 va fi vârf al diagramei nou construite Vor(M) iar semidreapta de pe mediatoare de la infinit la Q0 va fi muchie nou introdusă pentru diagrama Vor(M). Pe de altă parte, dacă Q0 = Qs atunci se elimină partea din muchia regiunii Vors(Us) de la Qs la infinit, iar dacă Q0 = Qd atunci se elimină partea din muchia regiunii Vord(Ud) de la Qd la infinit. În cazul Q0 = Qs, dacă se continuă deplasarea în direcŃia mediatoarei, se va trece în regiunea diagramei Vors a unui punct Us,1 din Ms care este despărŃită de regiunea Vors(Us) prin muchia lui Vors care trece prin punctul Qs. Ne vom afla deci la intersecŃia regiunilor Vors(Us,1) şi Vord(Ud). În această intersecŃie se găsesc punctele care sunt mai apropiate de Us,1 decât de toate punctele din Ms şi mai apropiate de Ud decât de toate punctele din Md. Mediatoarea segmentului Us,1Ud va despărŃi regiunea lui Us,1 de regiunea lui Ud. Remarcăm că această mediatoare trece prin Qs deoarece acest punct este centrul cercului circumscris triunghiului UsUdUs1. Deci din punctul Qs se continuă drumul pe direcŃia perpendicularei pe Us1Ud. Analog se procedează dacă Q0 = Qd. Deplasându-ne pe noua mediatoare (a lui Us1Ud) ne vom afla în intersecŃia regiunilor Vors(Us1) şi Vord(Ud) astfel că va intersecta într-un punct bine determinat frontiera primei regiuni şi în alt punct bine determinat din frontiera celeilalte regiuni. Primul dintre ele va fi noul vârf Q1 al diagramei Vor. Se repetă procedeul până ajungem la mediatoarea mu a podului inferior.

EXEMPLU

Punctele A, B, C constituie mulŃimea Ms iar A’, B’, C’ mulŃimea Md. Diagrama Voronoi a mulŃimii Ms are ca muchii mediatoarele laturilor triunghiului ABC care se întâlnesc în punctul O care este centrul cercului circumscris acestui triunghi. Punctul O este singurul vârf al diagramei Voronoi a mulŃimii Ms. În figură sunt indicate muchiile şi vârful O’ ale diagramei Voronoi a mulŃimii Md. Podul superior al celor două mulŃimi este evident segmentul AA’ iar cel inferior este BB’. Se vede că mediatoarea mu a podului superior străbate partea comună a regiunilor Voronoi ale punctelor A şi A’ . În această zonă, cuprinsă între mediatoarele segmentelor AC şi A’C’, sunt punctele care sunt mai apropiate de A şi A’ decât de toate celelalte puncte. Deci în această zonă trebuie tranşat între A şi A’. PorŃiunea din mediatoarea mu care se află în această zonă, (semidreapta lui mu având capătul în Q0) este muchia diagramei Voronoi a întregii mulŃimi M care delimitează regiunea lui A de regiunea lui A’. În punctul Q0 mediatoarea mu traversează mediatoarea segmentului A’C’ care desparte regiunea lui A’ de regiunea lui C’ în diagrama

A

B

C C’

A’

B’

O

O’

Q0 Q1

Q2

Q3

mu

ml

Voronoi a mulŃimii Md. Se trece astfel în zona comună dintre regiunea lui C’ din Md şi tot regiunea lui A din Ms. Aceste două regiuni sunt separate de mediatoarea segmentului AC’, care trece prin Q0 deoarece în acest punct se întâlnesc mediatoarele laturilor AA’ şi A’C’ ale triunghiului AA’C’. Deci ducând perpendiculara din Q0 pe AC’ aceasta este şi mediatoare a acestui segment. Partea din mediatoarea lui A’C’ care trece dincolo de Q0 nu mai are nici un rol pentru diagrama Voronoi a întregii mulŃimi. Perpendiculara din Q0 pe AC’ întâlneşte mediatoarea lui AC în punctul Q1. Segmentul Q0Q1 este muchia comună dintre regiunile lui A şi C’ în diagrama mulŃimii M. În punctul Q1 se traversează mediatoarea lui AC care separă regiunea lui A de regiunea lui C în diagrama lui Ms. Deci zona în care se trece este comună regiunilor lui C din Ms şi a lui C’ din Md. Pe de o parte porŃiunea din mediatoarea lui A’C’ care este dincolo de punctul Q1 nu mai face parte din diagrama Voronoi a întregii mulŃimi M, deci se şterge. Pe de altă parte, în noua zonă trebuie să se separe regiunea lui C de regiunea lui C’. Această separare se face cu mediatoarea lui CC’ care trece prin punctul Q1 care este intersecŃia dintre mediatoarele laturilor AC şi AC’ ale triunghiului ACC’. Mediatoarea lui CC’ întâlneşte frontiera regiunii lui C din Ms în punctul Q2 de pe mediatoarea lui BC care separă regiunea lui B de regiunea lui C din Ms. Mai departe se trece în zona comună dintre regiunea lui B din Ms şi regiunea lui C’ din Md. Pe de o parte se şterge porŃiunea din mediatoarea lui BC situată dincolo de punctul Q2. Pe de altă parte din Q2 se continuă în direcŃia perpendiculară pe BC’, care va fi şi mediatoarea acestui segment. Această mediatoare întâlneşte mediatoarea lui BB’ (care este mediatoarea ml a podului inferior) în punctul Q3. Se continuă drumul din Q3 pe direcŃia mediatoarei ml şi se şterge porŃiunea din mediatoarea lui B’C’ situată dincolo de punctul Q3. În final se obŃine diagrama Voronoi a întregii mulŃimi M care are 6 vârfuri: O, O’, Q0, Q1, Q2, Q3. Muchiile acestei diagrame sunt evidenŃiate în desen prin linii îngroşate. Din cele 6 regiuni ale diagramei două sunt mărginite şi anume regiunea lui C, care este triunghiul OQ1Q2, şi regiunea lui C’ care este pentagonul O’Q0Q1Q2Q3.

6.6. TEME PENTRU CASǍ 6.6.1. Să se alcătuiască tabelul dublu conex al grafului constituit din 4 vârfuri: A, B, C, D în care punctul D este în interiorul triunghiului ABC iar muchiile, în număr de 6, unesc fiecare vârf cu celelalte trei. 6.6.2. Să se determine diagrama Voronoi a mulŃimii formate din punctele A, B, C, O în care O este centrul cercului circumscris triunghiului ABC. 6.6.3. Fie triunghiul ascuŃitunghic ABC şi D simetricul lui C faŃă de AB. Notăm E şi F centrele cercurilor circumscrise triunghiurilor ABC şi respectiv ABD. Se cere diagrama Voronoi a mulŃimii formate din punctele A, B, C, D, E, F.

Bibliografie [1] J. CHEN, Computational Geometry: Methods and Applications, Texas A&M University, 1996. [2] F. P. PREPARATA, M. I .SHAMOS, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. [3] J. SCHWARTZ, C. YAP Algorithmic and Geometric Aspects of Robotics, New Jersei, 1987.