Ce e geometria computationala?

Godfried T Toussaint

Laboratorul de geometrie computationala

Facultatea de informatica

Universitatea McGill

Montreal, Quebec, Canada

1.Introducere

Consideram punctul P si linia l precum in planul ilustrat in figura 1.1. Apare imediat intrebarea: punctual P se afla pe, sub sau deasupra dreptei l?

In sens restrans, geometria computationala este preoccupata de calculul proprietatilor geometrice ale unor seturi de obiecte geometrice aflate in spatiu, precum simpla relatie “deasupra”/”dedesuptul” a unui punct cu o dreapta data. In sens larg geometria computationala este preoccupata cu conceperea si analizarea unor algoritmi pentru a rezolva probleme de geometrie. In sens mai profund geometria computationala reprezinta studiul complexitatii computationale inerente a problemelor geometrice. Aceaste interpretare presupune mai intai determinatea proprietatilor geometrice calculabile.

Sa presupunem ca in problema de mai sus punctul P este specificat in functie de coordonaatele sale pe axele OX si OY (xp,yp) si ca dreapta l este data de ecuatia y=ax+b, unde a si b reprezinta panta dreptei iar y reprezinta punctul unde dreapra intersecteaza axa OY. Pentru a simplifica discutia vom presupune ca a nu este egal cu infinit sau zero adica dreapta nu este verticala sau orizintala. Pentru a rezolva aceasta problema este suficient sa calculam intersectia dreptei verticale prin P cu dreapta l. Vom denumi acest punct Z cu coordonatele (xz,yz) ca in figura 1.1. Atunci xz=xp si yz poate fi calculat utilizand ecuatia yz=axp + b. Daca yz>yp atunci P se afla sub dreapta l, daca yz<yp atunci P se afla deasupra dreptei l, iar daca yz=yp atunci P se afla pe dreapta l.

Algoritmul de mai sus reprezinta doar una din multele metode de rezolvare a acestei probleme. Pentru a ilustra o alta metoda sa presupunem ca avem in biblioteca noastra cu instrumente computationale de baza o subrutina care calculeaza aria unui triunghi atunci cand introducem coordonatele x si y ale celor 3 puncte care determina triunghiul. Atunci putem rezolva problema in urmatorul fel. Mai intai determinam doua puncte noi Q (xq,yq) si R (xr,yr) pe dreapta l (fig 1.2). Cele trei puncte Q,R,P definesc un triunghi. Putem calcula aria acestui triunhi folosind urmatoarea formula:

Area= 1/2 [xq (yr - yp) + xr (yp - yq) + xp (yq - yr)]

In mod surprinzator, aria ne va dezvalui pozitia lui P fata de dreapra l. Daca P se afla pe dreapta atunci aria va fi in mod evident 0. Formula data mai sus calculeaza de fapt “Aria semnata” adica rezultatul va fi negativ daca cele trei puncte (Q,R.P) apar in sensul acelor de ceasornic, ir rezultatul va fi pozitiv daca cele trei puncte apar in sens opus acelor de ceasornic. Mai mult, pentru a rezolva problema noastra ceea ce ne intereseaza cu predilectie este semnul si nu valoarea absoluta a ariei. Putem observa ca in figura 1.2, daca P se afla sub dreapta l, varfurile triunghiului apar in sensul acelor de ceasornic, pec and daca P se afla deasupra dreptei l, varfurile triunghiului apar in sens invers acelor de ceasornic. De aici putem trage concluzia ca atunci cand aria este pozitiva P se afla deasupra dreptei l, iar P se afla sub l atunci cand aria este negativa.

Am prezentat doi algoritmi foarte diferiti folositi pentru a rezolva aceeasi problema de geometrie. La nivel de baza geometria computationala se ocupa cu studiul comparativ al algoritmilor fundamentali, avand ca scop determinarea, in diferite contexte computationale, algoritmilor care ruleaza mai rapid, care necesita mai putina memorie si care sunt mai robusti din punct de vedere al erorilor numerice. Cu toate acestea, geometria computationala utilizata in informatica de azi se ocupa mai mult cu dezvoltarea si analiza algoritmilor la un nivel conceptual mult mai ridicat decat cel prezentat mai sus.

2. Geometria Constructiva Clasica versus Geometria Computationala Moderna

2.1 Introducere

Geometria computationala este de multe ori catalogata drept o noua stiinta in informatica, multi informaticieni considerand ca aceasta a luat nastere fie cu teza de doctorat a lui Michael Shamos la Universitatea Yale in 1978 fie cu lucrarea sa despre complexitatea geometrica din 1975. Altii ar spune ca a inceput cu 10 ani mai devreme cu teza de doctorat a lui Robin Forrest la Universitatea Cambridge in 1968 sau cu lucrarile sale ulteriore despre geometria computationala in ’71 si ’74. Totusi s-ar gasi altii care sa spuna ca totul a inceput cu Minky si Papert care au incercat sa afle in 1969 care sunt proprietatile geometrice ale unei figuri pentru care aceasta poate sau nu poate fi recunoscuta de o gama larga de modele de procesare ale unei retele neurale. In continuare vom arata ca geometria computationala exista de mai mult de 2600 de ani, fiind fondata de greci. In acest context istoric vom arata noile caracteristici pe care informatica le-a adaugat acestui domeniu in devoltare in ultimii 30 de ani. Computerul electronic digital, desi a avut o puternica influenta asupra acestui domeniu, este un instrument folosit pentru a-i da “aripi” informaticii.Esenta

informaticii este matematica constructiva (computationala, algoritmica etc) independenta de tecnologia masinilor folosite pentru a implementa algoritmii pe care aceasta ii dezvolta. Precum spunea si informaticianul Olandez Edsger Dijkstra, “informatica nu ar trebui sa fie numita stiinta a calculului din acelas motiv pentru care chirurgia nu ste numita stiinta a bisturiului”. Sa studiem deci ce fel de geometrie s-a facut in trecut cu calculatoare primitive, cu mult inaintea computerului digital electronic.

2.2 Sfori cu noduri, Rigle, Compasuri si Computerul Electronic Digital

Daca nu aveai un raportor si iti era cerut sa construiesti un unghi drept intr-un anumit punct pe o linie data, este posibil sa iti amintesti cum sa o faci cu dreptarul si compasul, un calculator popular al grecilor antici. Sa presupunem insa ca tot ce ai la indemana este o bucata de sfoara. Urmatorul calculator, ieftin si usor de confectionat permite implementarea unui algoritm simplu a carui corectitudine este bazata pe o teorema fundamentata a geometriei computationale. Luati 12 bucati egale de sfoara si legati-le cap la cap cu noduri astfel in cat sa formeze un “colier” cu 12 noduri precum in figura 2.1 (a). Constructia acestui “calculator-colier” este terminata, deci este timpul sa ne concentram asupra algoritmului.

Pasul 1. Luati orice nod, numiti-l B si atasati-l liniei L in punctul unde vreti sa construiti unghiul drept asa cum este ilustrat in figura 2.1(b).

Pasul 2. Luati al patrulea nod de langa B in orice directie, numiti-l A si puneti-l de-a lungul liniei L tragand de sfoara astfel incat A sa fie cat mai indepartat de B

Pasul 3. Luati al treilea nod de langa B in cealalta directie,numiti-l C si trageti de el pana cand laturile AC si BC sunt perfect intinse.

Pozitia nodurilor B si C indica acum doua puncte pe o dreapta perpendiculara pe L in B. Dreapta perpendiculara pe L poate fi acum trasata cu un dreptar prin punctele B si C. In acest fel lucrau arhitectii egipteni acum 4000 de ani, Deci egiptenii aveau idee, cu mii de ani mai devreme decat grecii, de reciproca teoremei lui Pitagora.

In secolul al treilea inainte de Hristos, matematicienii din Alexandria precum Euclid erau implicati in geometria computationala.Geometria insa era studiata chiar si cu 200 d ani inainte, la scoala lui Platon din Atena.Desi Platon nu era un matematician ci un filozof el era de parere ca geometria era esentiala pentru a avea o minte sanatoasa. Studentilor sai de la filozofie le era cerut sa studieze geometria timp de 10 ani. La intrarea in scoala sa se gasea un semn pe care scria “nimeni care nu este familiar cu geometria sa nu intre aici.”

Deci care este diferenta dintre geometria greculo antici si geometria computationala moderna? Diferenta nu era una mare. Geometria computationala moderna se aseamana cu munca greculo preoccupati cu gasirea metodelor de rezolvare a problemelor de geometrie. Dupa cum vom vedea, multe din problemele cheie ale geometriei computationale din ziua de azi ii preocupau si pe grecii antici. Prima diferenta notabila ar fi ca ei lucrau cu date mici, pe cand in ziua de astazi, gratie calculatoarelor electronice digitale putem lucra cu seturi de date mai mari. Urmatorul exemplu concret din domeniul teoriei amplasarii cladirilor va evidentia acest lucru.

2.3 Marime Datelor de Intrare intr-un Algoritm

2.3.1 Teorema lui Heron

Sa consideram doua ferme in mijlocul unui camp in Saskatchewan de aceeasi parte a unei auto strazi din apropiere. Oamenii fac in mod continuu drumuri de la o ferma la cealalta si ar dori sa faca un ocol pana la autostrada pentru a face rost de provizii. O companie ar dori sa contruiasca un depozit undeva de-a lungul autostrazii in asa fel incat distanta dintre cele doua ferme via depozit sa fie minima. Unde ar trebui sa fie construit acest depozit si care este calea pe care ar trebui sa o urmeze fermierii? Aceasta problema a fost rezolvata de heron in jurul anului 100 dupa Hristos. Cu 400 de ani inainte, Euclid notase in cartea sa Catoprica legile fondamentale ale reflecxiei razelor de lumina de pe o oglinda.

Regula 1: Planul incidentei razei de lumina coincide cu planul reflexiei acesteia

Regula 2: Unghiul de incidenta al razei de lumina este egal cu unghiul de reflexie

Heron a extins rezultatele lui Euclid si a esplica legile reflexiei in termeni mult mai simpli: lumina calato reste intodeauna pec alea cea mai scurta. Din punct de vedere geometric putem formula problema cladirilor in urmatorul fel. Avem dreapta l si P si Q doua puncte de aceeasi parte a lui l (fig 2.2), iar d(a,b) reprezinta distanta euclidiana dinte punctele a si b. Gasiti punctul R pe l astfel incat d(P,R) + d(Q,R) sa fie minima. P’ este imaginea in oglinda a lui P (figura 2.3). Solutia R se afla la intersectia dreptei l cu dreapta P’Q. Aceasta este teorema lui Heron, cunoscuta si sub numele de “principiul reflexiei”. Este folosita pentru a rezolva o multitudine de probleme, una dintre cele mai recente fiind aceea a calcularii drumului cel mai scurt care trebuie urmat in interiorul unui poligon daca dorim sa atingem fiecare latura a acestuia. Pentru a verifica corectitudinea afirmatiei lui Heron considerati orice alt punct R’ situat la dreapta lui R (un argument similar se aplica atunci cand R’ se afla la stanga lui R). Prin constructie, dreapta l este un set de puncte echidistant fata de punctele P si P’. De aici rezulta ca d(P,R)= d(P’,R) si d(P,R’) = d(P’R’). Asta inseamna a lungimea “drumului” PRQ este egala cu lungimea “drumului” P’RQ si ca lungimea lui PR’Q este egala cu lungimea lui P’R’Q’. Dar din regula inegalitatii triunghiului care spune ca suma a doua laturi este mai mare decat a treia latura, rezulta ca “drumul” P’R’Q este mai lung deacat “drumul” P’RQ. De aici rezulta ca “drumul” PR’Q este mai lung decat “drumul” PRQ ceea ce inseamna ca R este locatia optima pentru depozit.

Problema lui Heron poate fi verificata foarte usor si cu compasul si dreptarul.

2.3.2 Problema localizarii cladirilor in format minimax

In versiunea standard a acestei probleme ne sunt date n puncte in plan reprezentand clienti, fabrici, scoli, piete, orase, puncte de distributie etc si se cere determinarea locatiei lui X unude o cladire ar trebui amplasata sa minimizeze distanta dintre X si cel mai indepartat punct. O astfel de problema este folositoare in amplasarea cladirilor serviciilor de urgenta (spitale, sediul politiei sau al pompierilor) atunci cand se doreste sa se micsorese timpul necesar interventiilor. Cand transportul dintre cladire si clienti se poate face in linie dreapta aceasta problema are o rezolvare eleganta si succinta: gasiti cel mai mic cerc cu centrul in X a carui arie inglobeaza cele n puncte. (fig 2.4)Raza cercului reprezinta distanta de la X la cel mai indepartat punct punct.

In acest tip de problema, numarul datelor de intrare poate varia de la ordinul sutelor pana la ordinul milionelor. Rezolvarea unei asemenea probleme pe vremea lui Euclid ar fi fost in afara oricarei discutii. Aceasta este una din diferentele dintre geometria computationalade atunci si de acum. In Antichitate, numarul datelor de intrare pentru un algoritm era foarte mic, insa era limiatata din motive practice si nu teoretice.

2.4 Dimensiunile unei probleme

Problemele discutate mai sus, precum majoritatea problemelor discutate in cartea “Elementele” a lui Euclid, sunt bidimensionala. Grecii se limitau la probleme bi sau tridimensionale. Astazi insa, geometria nu se limiteaza la rezolvarea problemelor de acest gen. Aceasta este o alta diferenta dintre geometria computationala de atunci si de acum. Grecii erau preocupati cu lumean fizica, modelata in trei dimensiuni euclidiene. Astazi insa tehnologii precum recunoasterea tiparelor de catre o masina si robotica ne ofera probleme in lumi multidimensionale.

2.5 Modele de calcul

2.5.1 Operatii Primitive

Un model de calcul reprezinta descrierea sau specificarea unui dispozitiv abstract, masinarie sau computer din perspectiva operatiilor promitive care pot fi efectuate asupra datelor de intrare si din perspectiva “costului” acestora. Un model de calcul este foarte folositor in clasificarea si ordonarea unor probleme si algoritmi in functie de complexitate si timpul de executie. De aceea specificarea si investigarea unor asemenea modeleeste o preocupare de baza a geometriei computationale moderne.

Unul dintre cele mai populare modele the calcul utilizate in geometria computationala este Real RAM (Random Access Machine). In versiunea de baza a acestui model, datele de intrare sunt specificate in numere realse si si presupunem ca un numar real este stocat intr-o locatie care utilizeaza o unitate de memorie. De asemenea mai presupunem ca urmatoarele operatii sunt primitive si ca fiecare poate fi executata intr-o unitate de timp:

1. Operatiile Aritmetice (adunarea, scaderea, inmultirea si impartirea)

2. Compararea numerelor reale (<,=,>)

Adesea un RAM mai puternic este acceptat prin acceptarea unor operatii aditionale precum compilarea logaritmilor, radicalilor de ordin K sau functiile trigonometrice.

Puterea de calcul si echivalenta masinilor

Specificarea unui model de calcul ne permite sa punem multe intrebari interesante. De exempluputem intreba care probleme pot fi executate cu o anumita masina. De asemenea putem cere ca in cazul unei probleme si a unei masini date sa comparam toti algoritmii cunoscuti (care pot

rezolva acea problema) in functie de numarul de operatii primitive si unitatile de memorie necesare. Vom ilustra aceste idei cu un exemplu concret.

Vom considera o noua problema de localizare a cladirilor, similara celei solutionate de Heron dun Alexandria (ilustrata in figura 2.2). In problema lui heron se cerea sa se calculeze distanta cea mai scurta dintre doua puncte via o linie data. Acum insa vom considera doua drepte a si b si un punct P (fig 2.5) Aceasta problema este piatra de baza pentru o gama larga de probleme care in prezent sunt investigate in geometria computationala, numite probleme transversale. Intr-o problema transversala tipica ne sunt date o serie de obiecte iar noi trebuie sa aflam cara exista o linie care intersecteaza toate obiectele din colectie. Mai mult, daca mai mult de o linie exista ni se cere sa aflam care ste cea mai scurta.

O intrebare evidenta acum este daca aceasta problema poate fi rezolvata utilizand RAM de baza. Raspunsul este negativ. Putem insa punea aceasta intrebare daca utilizam o masina mult mai puternica, al care RAM a fost extins prin adaugarea de operatii primitive precum calculul radacinilor de ordin n. In acest caz raspunsul este afirmativ. Acest lucru ne determina sa punem intrebari legate de puterea de calcul relativa a diferitelor masini si echivalenta masinilor, precum si echivalenta claselor de probleme, toate acestea fiind probleme arzatoare in geometria computationala moderna. Desi unii dintre noi ar putea crede ca aceste probleme au aparut de curand, adevarul este ca ele exista inca de pe vremea lui Euclid.

In geometria constructiva clasica, oamenii de stiinta eau preocupati cu definirea unor modele de calcul: caractereisticile masinilor care va executa algoritmii. Exemple tipice de masini care au fost utilizate in trecut includ: rigla, compasul, compasul de unica folosinta (care pur si simplu dispare dupa ce deseneaza cercul). Pentru detalii privind o larga varietate de masini de calcul antice puteti studia cartea lui William Random.

S-a incercat de asemenea sa se determine operatiile primitive permse cu fiecare tip de masina si sa se gaseasca anumite constructii care ar necesita mai putine operatii decat constructiile facute de Euclid.

O alta zona activa de cercetare a fost analizarea si compararea diferitelor modele de masini in functie de puterea lor de calcul. De exemplu , in 1672 Georg Mohr , iar mai apoi in 1779 Lorenzo Mascheroni au demonstrat ca orice constructie care poate fi realizata cu o dreapta si un compas poate fi facuta doar cu compasul. In 1833 Jacob Steiner a demonstrat ca dreapta are aceeasi putere ca si compasul daca dreptei ii este permisa utilizarea compasului o singura data. Pentru a accentua faptul ca dreapta si compasul nu sunt inca inutile, trebuie remarcat faptul ca teorema Mohr-Mascheroni a fost redemonstrata recent (in 1987) de Arnon Avron la universitatea din Tel Aviv.

Cea mai veche teorema priving echivalenta modelelor de calcul ii este atribuita lui Eulcid in primul capitol al Elementelor, unde el echivaleaza compasul de unica folosinta cu un compas obisnuit. Trebuie notat faptul ca multe dintre afirmatiile lui Euclid au fost criticate in ultimii douazeci de ani insa acest lucru trebuie atribuit traducatorilor sai intrucat algoritmii originali ai lui Euclid sunt dincolo de orice repros.

Sa revenim insa la problema gasirii celei mai scurte drepte AB care leaga dreptele a si b prin punctul B (fig 2.5). Ne amintim faptul ca aceasta problema nu poate fi solutionata cu ajutorul RAM-ului Real de baza. De asemenea ne amintim faptul ca problema lui Heron din Alexandria a fost solutionata utilizand rigla si compasul. Ne intrebam deci daca si aceasta problema poate fi solutionata intr-un mod similar. De fapt, problema celui mai scurt pod si problema rezolvarii acesteia cu rigla si compasul au o instorie interesanta. Primul cercetator care a gasit o caracterizare a solutiei a fost Philon din Bizant in jurul anului 100 d.H. iar problemele de acest gen au fost numite Linia Philo. Si mai interesant este motivul pentru care Philo era interesat de acesta problema. Trei probleme pe care grecii le urmareau cu mare pasiune erau: impartirea in trei parti egale a unui unghi, construirea unui patrat cu aceeasi arie ca un cerc dat si construirea unui cub cu volum dublu fata de un cub dat . Aceste trei probleme trebuiau rezolvate doar cu o lini si un compas.

Solutiile acestor probleme au existat cu mult inainte de Philon insa foloseau alte tipuri de masini. De exemplu Plato a conceput un calculator pentru a dubla volumul cubului care semana cu intrumentul utilizat de un pantofar pentru a masura lungimea piciorului. Philon insa a demonstrat ca gasirea celui mai scurt drum intre cele doua drepte este echivalent cu dublatul cubului, fapt care l-a determinat sa incerce sa gaseasca o rezolvare care sa utilizeze doar rigla si compasul. De fapt, mai multe probleme fusesera reduse reduse la problema dublarii cubului, creand un intreg set de probleme. Daca oricare dintre acestea putea fi rezolvata atunci toate puteau fi rezolvate. Deci grecii dezvoltasera o teorie a complexitatii claselor intr-un mod asemanator celui in care cercetatorii moderni dezvolta teoria complexitatii. Cu toate acesta Philon nu a putut rezolva problema. In secolul al 17-lea Isaac Newton s-a aplecat asupra problemei lui Philon, a generalizat-o si a gasit o caracterizare diferita a ei. Cu toate acestea el nu a gasit o solutie care sa utilizeze doar rigla si compasul. De fapt nimeni nu a gasit o asemenea solutie pentru ca ea nu exista. Volumul unui cub nu poate fi dublat utilizand doar rigla si compasul, fapt demonstrat abia in secolul al 19-lea. Din teorema reducerii a lui Philon rezulta ca drumul cel mai scurt nu poate fi calculat doar cu rigla si compasul. Este interesant faptul ca o problema din secolul I inainte de Hristos reprezinta o piatra de baza pentru algoritmii transversali cei mai scurti din secolul XX si ca RAM-ul Real din secolul XX are aceleasi limitari ca rigla si compasul.

In final, este de notat faptul ca dublatul cubului este echivalent cu rezolvarea ecuatiei y3=2x3.Aceasta se poate scrie ca y=21/3x. De aceea problema lui Philon poate fi rezolvata cu versiunea extinsa a RAM-ului Real in care radacinile de ordin n sunt acceptate ca operatii primitive.

2.5.3 Complexitatea algoritmilor

Una dintre structurile geometrice fundamentale care a primit multa atentie in geometria computationala este invelitoarea convexa a unui set. De fapt, unii cercetatori sustin ca geometria computationala a inceput cu lucrarea din 1972 a lui Ron Graam despre calculul invelitorii convexe a unui set finit de puncte in plan. Invelitoarea convexa a unui set S este cel mai mic set convex care il contine pe S. Figura 2.6 (a) ilustreaza invelitoarea convexa a unui set de puncte. Imaginati-va punctele ca fiind cuie care ies in afara unei placi de lemn. Invelitoarea convexa este asemenea unei benzi elastice intinse in jurulcuielor. Cand S este un set de puncte, limita invelitorii convexe este un poligon convex care consta din margini care conecteaza anumite puncte ale lui S. O pereche contribuie la limita invelitorii convexe daca si numai daca linia l dusa prin cele doua puncte divide planul in doua regiuni (cate una de fiecare parte a lui l) in asa fel incat una dintre aceste regiuni nu contine niciun punct din S. In figura 2.6 (b) A,B contribuie la limita invelitorii convexe in timp ce C,D nu.

Aceasta caracterizare duce la un algortim conceptual simplu pentru a calcula invelitoarea convexa a lui S care foloseste algoritmul discutat in introducere pentru a determina daca un punct este deasupra sau dedesubtul uneilinii. Presupunem pentru simplitate ca punctele lui S sunt date in functie de coordonatele lor carteziene si ca oricare doua puncte nu au aceleasi coordonate. Tot ce trebuie sa facem este sa consideram toate perechile de puncte prin care tragem o linie si sa verificam daca cele ramse se afla de o parte a liniei. In cele din urma vom determina invelitoarea convexa.

O intrebare naturala se iveste insa: cat de puternic trebuie sa fie un calculator pentru a executa acest algoritm? Este simplu de verificat faptul ca RAM-ul Real de baza este suficient.

O alta intrebare este: Pentru un set S cu N puncte, cate operatii primitive sunt necesare pentru a calcula invelitaorea convexa a lui S. In alte cuvinte, care este complexitatea algoritmului. Aceasta intreabre este acceasi pe care Lemoine si-a pus-o pentru algoritmii lui Euclid care utilizau rigla si compasul. Lemoine a denumit numarul de operatii primitive necesare pentru executarea unui algoritm simplicitatea constructiei. Daca S consta dintr-o configuratie data de 10 puncte am putea pur si simplu sa numaram operatiile executate si sa raportam acest numar absolut ca fiind complexitatea algoritmului. In acest fel masurau grecii antici complexitatea algoritmilor. In epoca moderna insa, este mult mai util sa il determinam aceasta complexitatea a algoritmului ca o functie a lui n. Aceasta este diferenta dintre geometria computationala de atunci si cea de acum. Grecii se multumeau cu gasirea unei solutii la o problema, pe cand in ziua de astazi se cer algoritmi din ce in ce mai rapizi.

Considerati de exemplu algoritmul invelitorii convexe descris mai sus. Pentru o pereche de puncte data determinam linia care trece prin ele folosind k1 operatii primitive. Apoi testam n-2 puncte pentru a determina daca se afla deasupra sau dedesubtul liniei. Presupunem ca verificarea fiecarui punct necesita k2 operatii. Trebuie apoi sa repetam aceasta operatie pentru fiecare pereche de puncte din S. Vor fi deci n(n-1)/2 asemenea perechi. Deci numarul total de operatii primitive, numit complexitatea algoritmului, notat cu C(n) este:

C(n)=[n(n-1)/2 ]*[(n-2)k2 + k1]

Extinzand aceasta expresie , rearanjand termenii si redenumind constantele obtinem:

C(n)=c1n3 + c2n2 + c3n + c4

unde ci, i=1,2,3,4 sunt constante

Acest algoritm simplu contine un polinom de grad trei in expresia care ii determina complexitatea. Probleme mai complicate pot avea formule mult mai lungi si mai complicate, facand compararea algoritmilor dificila. De aceea vom folosi o conventie simpla pentru a face complexitatea expresiilor mai simpla: vom folosi doar termenul care ii domina pe toti ceilalti termeni si vom scapa de constante. Acest tip de notatie se numeste notatia “Marelui O”. Folosind notatia “Marelui O” complexitatea algoritmului nostru devine O(n3). Pe masura ce n creste, C(n) incepe sa se comporte ca n3. De asemenea este denotat faptul ca daca o operatie primitiva se executa intr-o micro-secunda iar n este un milion ii vor trebui algoritmlui 10.000 de ani pentru a se executa. De aceea cand n este de o asemenea marime, o complexitate in timp a lui O(n3) nu mai poate fi determinata. Multi alti algoritmi cu complexitatea in timp mult mai mica exista pentru calculul invelitorii convexe a n puncte. Algoritmul lui Graham este unul dintre cei mai rapizi si necesita doar O(n log n) operatii primitive. Este de notat faptul ca acest algoritm se va executa in o secunda.

2.5.4 Complexitatea inerenta a problemelor de geometrie

O intrebare naturala din geometria computationala a secolului 20 este: care este cel mai rapid algoritm pentru a rezolva o anumita problema? De exemplu putem intreba care este numarul minim de operatii primitive necesare necesare pentru a calcula invelitoarea convexa a n puncte în conformitate cu un model potrivit de calcul. In mod surprinzator aceasta intrebare simpla nu a fost pusa de vechii greci, sau chiar Lemoine in ceea ce priveste numarul de pasi in constructiile lor cu compasul si dreptarul. Aceasta este poate cea mai importanta diferenta dintre geometria computationala de atunci si cea de acum. Un raspuns la aceasta intrebare ne ofera o limita inferioara a complexitatii in timp a unei probleme. In locul Marelui O vom utiliza simbolul Ω, pentru a nota limita inferioara. Trebuie notat faptul ca aceasta afirmatie se refera la o problema si nu la un algoritm. Cu toate acestea este o afirmatie despre toti algoritmii posibili pentru rezolvarea acestei probleme. Complexitatea unui anume algoritm care rezolva problema mai este numita si limita superioara a complexitatii in timp a unei probleme. Gasirea limitelor inferioare este una dintre cele mai teoretice activitati din geometria computationala, insa are unele dintre cele mai practice consecinte. De exemplu, daca pantru o problema data exista un algoritm O(n log n) dar limita inferioara este Ω(n) atunci zeci de cercetatori pot pierde ani intregi in cautarea unor algoritmi mai rapizi. De cealalta parte, daca cineva dovedeste ca existenta unei limite inferioare Ω(n log n) atunci cercetarile se pot opri intrucat nu exista algoritmi mai rapizi. Se poate atunci incerca reducerea factorului constant din complexitate. Atunci cand limita inferioara a unei probleme este aceeasi cu limita superioara a algoritmului, algoritmul este optim.

2.5.5 Complexitatea Asteptata a Algoritmilor

Este de asemenea comun in analiza complexitatii unui algoritm sa aflam nu numai complexitatea in cel mai rau caz, adica cel mai mare numar de operatii primitive necesare impuse de diferitele configuratii ale datelor de intrare, ci si complexitatea asteptata. In analiza complexitatii asteptate presupunem ca datele sunt aleatoare si sunt generate de un anumit model probabilistic. Sub influenta acestor presupuneri, calculam valoarea asteptata a numarului de operatii primitive asteptate. In practica, complexitatea asteptata este de cele mai multe ori o descriere mai realista a performantei in timp a algoritmului. Cu toate acestea, analiza complexitatii asteptate este mult mai greu de realizat decat analiza complexitatii in cel mai rau caz.

2.5.6 Observatii istorice

Discutia de mai sus legata de complexitate ajuta in solutionarea disputei cu privire la cine si cand a inceput geometria computationala. Desi acum este clar ca geometria computationala nu a inceput cu Shamos, contributia acestuia la includerea analizei complexitatii si introducerea limitelor inferioare i-a castigat supranumele de parintele teoriei complexitatii geometrice

Este de remarcat faptul ca Shamos nu a fost primul care a folosit notatia Marelui O pentru a descrie complexitatea unui algoritm. Lucrarea lui Graham din 1972 despre invelitoarea convexa dovedeste acest lucru. Cu toate acestea, Graham nu mentioneaza limitele inferioare. O limita inferioara Ω(n log n) a fost stabilita pentru problema invelitorii convexe ani mai tarziu, demonstrand ca algoritml lui Graham este optim

Este incorect faptul ca geometria computationala a inceput cu problema invelitorii convexe si ca Graham a avut primul algoritm. Aproape acelasi algoritm a fost publicat de Bass si Schubert cu cinci ani inainte.

Inchidem aceasta sectiune prin a mentiona faptul ca trebuie sa avem grija cu definitia problemei ce priveste limitele inferioare. De exemplu limita inferioara Ω(n log n) a problemei invelitorii convexe de mai sus nu este aceeasi daca datele de intrare specifica un simplupoligon cu n laturi. Cativa algoritmi O(n) exista pentru acest caz special. Primul asemenea algoritm a fost descoperit de McCallum si Avis.

3. Domeniul Geometriei Computationale

3.1 Introducere

In aceasta sectione vom incerca sa oferim cititorului o privire de ansamblu asupra geometriei computationale din zilele noastre. Geometria computationala este astazi un domeniu larg si nu il putem studia pe tot. De aceea, oriunde este posibil vom mentiona alte domenii ale acestei discipline si vom indica materiale auxiliare care se ocupa de aceste sub-discipline.

3.2 Sondarea Geometrica

Sa presupunem ca lucrati in domeniul producerii inelelor de metal in forma de cerc du diametrul D, dar procesul de productie nu este perfect si uneori apar inele care nu sunt circulare. Cu toate acestea, procesul este destul de bun intrucat intotdeauna produce unele convexe si netede. Ai dori sa implementezi o procedura de control al calitatii care sa determine care inele sunt circulare si care nu, pentru a le putea trimite pe cele defecte inapoi atelierului pentru remodelare.

Poate ca ati creat vreodata un obiect la strung si ati folosit un set de etrieri pentrua masura latimea obiectului pe o anumita directie ca in figura 3.1. Un asemenea test poate fi considerat o sonda care deduce forma obiectului. Idealizat intr-un spatiu geometric, putem vizualiza aceasta sonda ca apropierea a doua drepte paralele si infinite de marginile obictului convex pana il ating. In aceasta pozitie de contact dreptele se numesc drepte paralele de suport. Rezultatul obtinut este distanta de separare minima dintre dreptele paralele de suport. Sa denumim acest tip de sonda, sonda etrier. Evident folosind doar o sonda etrier nu putem obtine prea multa informatie despre forma obiectului in afara de faptul ca poate fi plasat in cadrul unei benzi de latime D. Dar ghidat de sentimentul ca un obiect convex neted cu diametrul D intr-un numar suficient de directii este circular, implementati un sistem de control al calitatii in care trei probe etrier sunt plasate la 60 de grade distanta una de cealalta.Daca toate probele dau o distanta da separare D atunci puteti trage concluzia ca inelul este circular.

Va intrebati insa cat de bun este un asemenea control. Procedura de mai sus a fost utilizata pentru a determina daca sectiunile rachetelor de propulsie aleunei navete spatiale sunt suficient de circulare pentru a fi refolosite la urmatoarea lansare. O poveste fascinanta cu privire la circumstantele tehnice,manageriale si politice in care naveta spatiala Challenger a explodat omorand 7 astronauti ii apartine fizicianului castigator al premiului Nobel, Richard Feynman. Acesta a fost in comitetul de investigare a dezastrului de atunci si a scris despre aceasta experienta in cartea sa “What Do You Care What Other People Think?”

Cand rachetele propulsoare si-au indeplinit scopul acestea se detaseaza si cad in ocean. Apoi sunt recuperate, desfacutein sectiuni si trimise in Utah pentru reconstructie. In timpul impactului acestea se deformeaza partial si nu mai au forma circulara. De aceea ele sunt testate cu trei probe etrier aflate la 60 de grade una de cealalta . Daca deformarea nu este prea puternica, sectiunile sunt considerate a fi circulare si sunt refolosite. In timpul vizitei lui Feynman la fabrica din Utah, munitorii i s-au plans ca deseori intampinau dificultati in a reasambla sectiunile si ca suspectau ca testele nu erau adecvate. Superiorii lor insa l-au ignorat plangerile.

Va poate surprinde faptul ca o forma convexa cu o mie, un milion, chair si un numar infinit de diametre masurate pe o infinitate de directii, poate sa nu fie circulara. Triunghiul Reuleaux ilustrat in figura 3.2 este un astfel de exemplu In figura 3.2, figura ABC reprezinta un triunghi echilateral standard. Lungimea fiecarei laturi este D. Pentru a construi un triunghi Reuleaux vom inlocui fiecare latura cu un arc de cerc de raza D. Este evident ca peorice directie dreptele paralele de suport vor fi la distanta D una de cealalta. Cu alte cuvinte, toate sondele etrier au acelasi diametru. O astfel de forma se numeste forma cu diametru constant. De aceea, un astfel de test ineficient a contribuit masiv la tragicul dezastru de pe naveta Challenger.

Exemplul de mai sus ilustreaza aplicatiile unui tip de sonda (sonda etrier) pentru a determina forma unui obiect. Acesta mai demonstreaza si ca orice numar de sonde este insuficient pentru a determina daca o forma este circulara. Cu toate acestea, exista multe alte obiecte de interes in afara de cercuri. De exemplu ne putem imagina un robot cu senzori tactili care trebuie sa determine forma exacta a unui poligon convex cu n noduri. Ne putem imagina de asemenea o sonda mult mai performanta care poate determina nu numai distanta dintre cele doua drepte paralele, ci si coordonatele punctelor de contact. Atunci putem determina forma unui poligon convex necunoscut folosind un numar finit de sonde.

Teoria sondarii geometrice este preocupata de acest tip de probleme legate de obiecte bi si multi dimensionale, folosind sonde etrier, precum si multe alte tipuri de sonde. Doua dintre cele mai importante probleme care se ivesc sunt: determinarea numarului de sonde necesare si suficiente si crearea de algoritmi eficienti care sa controleze sondele.

Aceasta zona a geometriei computationale ilustreaza o alta diferenta dintre ce se practica acum si ce se practica pe vremea vechilor greci. Grecii erau preocupati doar de obiecte predefinite si nu explorau partea de invarate prin folosirea de sonde asupra unor figuri cunoscute doar partial

3.3 Teoriile si Algoritmii Galeriilor de Arta

Sa presupunem ca detineti un muzeu sau o galerie de arta cu picturi si sculpturi nepretuite. Sunteti interesati de instalarea unui sistem de supraveghere compus din camere video fixe, dar care se pot roti la 360grade. Presupuneti pentru simplitate ca traiti intr-o lume bidimensionala. Galeria de arta poate arata ca unl din poligoanele din figura 3.3. Daca galeria are forma din figura 3.3 (a) atunci este clar faptul ca veti avea nevoie doar de o camera aflata in punctul X. Mai mult, X poate fi oriunde in galerie. Un poligon care necesita doar o camera este cunoscut drept poligon-stea. Toate poligoanele au forma de stea, insa nu toate poligoanele-stea sunt convexe. Setul de puncte unde o camera poate fi amplasata se numeste nucleu al galeriei. In figura 3.3 (b) avem o galerie non-

convexa in forma de stea. Camera (punctul y) poate fi montata oriunde in nucleul galeriei (regiunea umbrita.

Acum sa presupunem ca aveti o galerie foarte mare si complicata care nu este in forma de stea, cu n ziduri ( n destul de mare). Poate galeria voastra arata precum cea din figura 3.4. In 1973 Victor Klee a pus intrebarea: pentru garelie arbitrara care este numarul minim de camere necesar pentru a pazi interior al unei galeri cu n ziduri. Vasek Chvatal a stabilit “teorema galeriei de arta a lui Chvatal” ca n/3 camere sunt intotdeauna suficene si cateodata necesare. In figura 3.4 n=36 si n/3=12 deci 12 camere sunt suficiente potrivit teoremei. Cu toate acestea pentru aceasta galerie specifica sunt necesare doar 4. In 1981 Avis si Toussaint au demonstrat un algoritm eficient pentru gasirea locatiilor unde ar trebui amplasate camerele. Este tentata amplasarea unei camere la fiecare al 3-lea nod al poligonului. Cititorul poate crea cu usurinta o galerie unde aceasta strategie vaesua indiferent de unde se incepe amplasarea camerelor.

Acest tip de problema pentru diferite tipuri de camere si diferite tipuri de mediu cade intr-o zona de cercetare care a devenit cunoscuta drept teoriile si algoritmi galeriilor de arta.

3.4 Grafica pe calculator

3.4.1 Problema liniei ascunse.

Consideram galeria de arta din figura 3.4 unde 4 camere sunt instalate pentru a vedea intreaga galerie. Sunteti interesati sa aflati care zone din galerie sunt vizibile cu o singura camera C o asemenea regiune denumita zona de vizibilitate din punctul C este ilustrata in figura 3.5 determinarea acestei zone de vizibilitate este cunoscuta in literatura de specialitate drept sproblema liniei ascunse. In grafica pe calculator suntem si mai interesati de versiunea tridimensionala a acestei probleme denumita si problema eliminari suprafetei ascunse. Intr-o problema tipica ne ofera o descriere geometrica a unui set de obiecte in spatiu si ni se cere sa specificam obiectele vizibile din punctul V. Cu toate acestea multe dintre aceste probleme au beneficiat de aportul geometriei computationale. Un algoritm standard folosit pentru rezolvarea problemei din figura 3.5 le este datorat lui Freeman si Loutrel care au dezvoltat un algoritm cu mai mult de 10 ani inainte de lucrarea lui Shamos care ar marca inceputul geometriei computationale. Freeman si Loutrel nu au calculat complezitatea aloritmului lor in termeni de Marele O insa algoritmul lor se executa in timp O(n2), unde n este numarul de laturi ale poligonului. Folosind uneltele create pentru dezvoltarea algoritmilor in geometria computationala ElGindy si Avis au putut sa creeze un algoritm care se executa in timp O(n). Cand n este mare aceasta reprezinta o imbunatatire considerabila a vitezei algoritmului.

3.4.2 Urmarirea razelor, aproximarea poligoanelor si triangularea poligoanelor.

Trei aplte probleme fundamentale in grafica pe calculator sunt:

I -Urmarirea razelor.

II -aproximarea poligonala a unei curbe.

III-triangularea poligoanelor.

In aceste domeni geometria computationala a avut contributi semnificative.

3.4.3 Geometria computationala si grafica pe calculator.

Aceste 2 domeni s-au influentat unul pe celalalt fapt evidentiat de problemele liniei ascunsesi cea a eliminari suprafetelor. Grafica pe calculator faec cunoscute probleme practice comunitati geometrie computationale care ofera adeseori algoritmi mai rapizi. Este de asteptat ca geometria computationala sa aduca imbunatatiri dramatice algoritmilor standard folositi in grafica pe calcualator. Geometria computationala le ofera programatorilor grafici noi metode de a gandi problemele. In a treia sa lucrare David Dobkin exploreaza viata la interferenta acestor 2 lumi.

3.5 Geometria computationala dinamica.

Sa consideram din nou problema calculului invelitori convexe a unui set de puncte in plan. Sa presupunem ca vi se dadeau n puncte si ca foloseati O(n3) operati primitive cu algoritmul de scris in sectiunea 2.5. Presupuneti acum ca un punct aditional P a fost lasat afara din datele initiale si vi se cere sa aflati invelitoarea convexa a celor n+1 puncte. Cu alte cuvibte vi se cere sa actualizati invelitoarea convexa a celor n puncte prin inserarea unui nou punct. O abordare evidenta este sa desconsiderati toata munca depusa pentru cele n puncte originale si sa aplicati algoritmul inca o data pentru cele n+1 puncte. Aceasta inseamna ca inserati un punct nou folosind O(n3) operati primitive. Este de mentionat faptul ca notarea prin conventie a Marelui O ne indica: O((n+1)3)=O(n3). O metoda mult ami eficienta ar fi sa modificam invelitoarea convexa existenta pentru a reflecta introducerea noului punct P. De exemplu am putea verifica daca noul punct se afla in interiorul invelitori convexe originale. In acest caz invelitoarea nu se modifica si nimic alt ceva nu mai trebuie modificat. Intrebarea evidenta este: cat de repede ne putem da seama daca punctul P este in interiorul unui poligon cu n laturi. Prima nota ar fi ca marginile invelitori convexe sunt de 2 feluri marginile de sus si cele de jos. Sa ne amintim ca am presupus pentru a usura discuia ca nu exista 2 puncte cu aceleas coordonate X, deci nici o margine nu este verticala. E evident un punct p este in invelitoarea convexa daca si numai daca se afla deasupra tuturor liniilor care trec prin amrginile inferioare si daca sxe afla dedesubtul tuturor liniilor care trec prin marginile superioare. De aceea putem determina daca un punct pP este in interiorul unui poligon convex de n laturi folosind algoritmul descris in introducere pentru a testa poziti relativa a unui punct in arport cu o linie. Aceasta abordare utilozeaza un algoritm O(n) pentru a testa incluziunea unui punct intr-un poligon complex. Cu toate acestea putem sa facem ceva mult mai bun daca preprocesam poligonul convex si depozitam informatiile intr-o structura de date potrivita.

Mai intai alegeti un punct arbitrar O in interiorul poligonului aceasta poate fi facuta in urma calculari mediei aritmetice a orcaror 3 noduri ale poligonului. Apoi trsati linii din o prin fiecare nod al poligonului precum figura 3.6(a). Consideram o linia verticala v care trece prin O. Presupunem ca p se agla la dreapta lui v si consideram dreptele aflate in dreapta lui v. Deoarece poligonul este convex toate aceste drepte apar sortate in ordine dupa pantape masura ce traversam nodurile ordonate ale poligonului. Deci prin stocarea acestor drepte intr-un vector ordonat putem aplica o cautare binara pentru a determina in doar O(log n) operati linia aflata imediat deasupra punctului P. O data cunoscuta perechea de drepte pe care punctul se aflaun simplu test ne va spune daca punctul se afla in interiorul poligonului. Presupunem ca am aflat ca P se afla intre li si li+1 precum in figura 3.6(a). Atunci daca Pi,,Pi+1 este o margine superioara verificam daca P se afla sub linia care trece

prin Pi,,Pi+1 daca da atunci P este poligonul complex altfel nu este. O abordare similara este utilizata atunci cand P se afla la stanga lui v.

Daca punctul se afla in exteriorul invelitori convexe atunci actualizarea proceduri nu este finalizata intrucat trebuie sa deconectam o aprte din vechea granita si sa adaugam doua noi margini la cea noua precum in figura 3.6(b). Utilizand tehnici analoage celor descrise mai sus aceasta operatie poate fi executata in O (log n) pasi.

Sa schimbam acum scenariul si sa presupunem ca noi pincte sunt inserate in mod continuu pentru a beneficia in continuare de structura de date preprocesataa, aceasta trebuie actualizata. Asemenea structuri de date sunt dinamice air aceasta subdisciplina a geometriei computationale este numita geometrie computationala dinamica. Mai mult in situati dinamice vrem nu numai sa adaugam puncte ci si sa stergem din ele.

In a patra sa lucrare Yi-Jen Chiang si Roberto Tamassia ofera un tutorial care are aplicati practice importante in grafica pe calculator si design asistat de calculator.

3.6 Geometria computationala paralela.

3.6.1 Retele de calculatoare secventiale.

In discutiile anterioare am presupus in mod tacit ca modeklele de calcul sunt secventiale adica toate operatiile primitive erau executate una dupa alta. Am subliniat faptul ca pentru unele probleme dacca datele de intrare sunt foarte mari timpul necesar executiei poate fi o problema in sine. De aici apare intrebarea: daca in locul folosiri unei singure masin pe care operatiile primitive sunt executate una dupa alta, am folosi o colectie de k calculatoare care ar lucra la problema simultann, cat de rapid aam putea solutiona problema. Deoarece fiecare calculator solutioneaza doar o parte a priblemei si calculatoarele trebuie sa comulnice unul cu celalalt pentru anu aparea aceleas rezultate de doua ori, si pentru a asambla rezultatele partiale obtinute de fiecare calculator intr-o solutie complecta algoritmi utilizati sunt diferiti de cei folositi de calculatoarele secventiale. Un calculator secvential poate afla invelitoarea convexa in O(n3) operati primitive. Daca folosim O(n3) calculatoare in apralel algoritmul se poate executa intr-o unitate de timp. Desigur poate ca e imposibil sa construim un calculator cu O(n3) procesoare care sa comunice unul ce celalalt. Geometria computationala in apralel face un compromis intre numarul de procesoare utilizat in apralel si timpul necesar executari algoritmului.

In acincea lucrare Mikhail Atallah ofera mai multe tehnici pentru rezolvarea tehnici pentru rezolvarea problemelor de geometrie pe masini in paralel.

3.6.2 Geometria computationala si retelele neuronale.

Trebuie sa mentionam ca lucrarea clasica despre retelele neuronale a lui Minsky si Papert intra in domeniul geometriei computationale in paralel. Accentul cade insa pe abilitatea calculatoarelor in paralel (retele neuronale) de a invata sa recunoasca anumite proprietati geometrice ale datelor de intrare.

3.6.3 Geometria computationala optica.

O alta abordare a geometrie computationale in apralel utilizeaza calculatoare optice. Pentru detali consultati lucrarea lui Karasik si Sharir, “ Geometria computatiomala obtica “

3.7 geometria computatioanala isothetica.

Cunoscuta si sub numele de geometrie computationala rectilinie aceasta se ocupa cu date de intrare reprezentate de segmente si poligoane in care toate laturile sunt fie verticale fie orizontale. Aceasta restrictie simplifica masiv algoritmi pentru rezolvarea problemelor de geometrie. In unele domeni precum procesarea de imagine datele utilizate sunt predominant poligoane isothetice.

Poate una dintre cele mai importante aplicati este asa numita problema a conturului patrulaterelor lipute. In aceasta problema ne sunt date patrulatere in plan si ni se cere sa aflam granita exterioara a acestora.

3.8 Geometria computationala numerica.

Considerati urmatoarele date de intrare pentru un algoritm care proceseaza invelitoarea convexa. Generati 1000 de puncte pe limita unui cerc dat api calculati invelitoarea convexa a cestor puncte. In mod evident invelitoarea convexa ar trebui sa fi eun poligon complex cu o 1000 de noduri. O implementare tipica a algoritmului invelitori convexe ne va da ca reziltat un poligon convex cu doar 950 de noduri. Aceasta ilustreaza problemele ingrijoratoare legate de acuratetea algoritmilor.

Geometria computationala numerica se ocupa de crearea unor algoritmi de incredere. Edelsbrunner si Mucke descriu o tehnica numita de ei simularea simplitati care simplifica algoritmi sugerand un model uniform de a elimina degenerarile.

3.9 Modelarea geometrica

se refera la procesul generari de modele geometrice a unor obiecte reale sau a unor procese dinamice care pot fi stocate in calculator cu scopul designului (CAD), manufacturii, sau stimularea proceselor. Nu este surprinzator faptul ca exista o varietate de subprobleme in modelarea geometrica in care geometria computationala joaca un rol important. Una din cele mai portante probleme este generarea unei site in interiorul unui poligon.

3.10 Computer Vision

3.10.1 Introducere.

Acest domeniu sa dezvoltat in ultimi 40 de ani ca o subdisciplina a inteligentei artificiale. Cele mai relevante carti din acest domeniu au fost scrise de Ahuja si Schacter (1983) si Sugihara (1986).

Este util sa descompunem problema viziuni calculatorului intr-o serie de subprobleme care se executa secvential si in ordinea ilustrata in figura 3.9 scopulprogramului viziuni calculatorului este de a analiza o scena din lumea realacu ajutorul uinui dispozitiv de intrare precum o camera digitala, si de a ajunge la o descriere a sccenei care este folositoare pt indeplinirea unei sarcini. De obicei camera foloseste o matrice de numere fiecare reprezentand cantitatea de lumina a unei scene din lumea reala intr-o anumita loicatie din campul vizual. Prima etapa a procesului consta in

segmentarea imagini in obiecte semnificative. Urmatoarea etapa implica procesarea imaginilor pentru a evidentia anumite caracteristici si pt a indeparta neregularitatile sub o firma sau anlta.

A treia etapa consta in extragerea caracteristicilor sau masurarea formelor obiectelor. Ultima etapa este preocupata de clasificarea obiectului in una sau ami multe categori.

3.10.2 Grafuri de proximitate si forma unui set de puncte.

In unele contexte datele de intrare nu sunt descrise de poligoane ci de un set de puncte discontinue. Asemenea obiecte sunt numite tipare punct si sunt bine modelate ca seturi de puncte. Deci una din problemele centrale in analiza formelor este extragerea sau descrierea formei unui set de puncte. S defineste un set finit de puncte in plan. Un graf de proximitate a unui set de puncte este un graf obtinut prin conectarea a doua puncte prin intermediul unei alturi daca cele doua puncte sunt apropiate iintr-un anume sens. MST (garful de intindere minima) si RNG (graful relativ de invecinare)sunt 2 grafuri de proximitate care au fost bin einvestigate in acest proces.

Graful de intindere seamana cu un copac aobtinut prin conectarea perechilor de puncte. Lungimae unui copac reprezinta suma tuturor lungimilor laturilor din copac. Graful de intindere minima reprezinta copacul cu cea mai mica lungime dintre toate grafurile de intindere. Acesta prezinta proprietati atractive pentru viziunea clculatorului si din acest motiv este utilizat la scara larga. Consideram punctele din figura 3.9(a) cum asti conecta acease pucte in asa fel incat figura rezultanta sa descrie structura atat de evidenta pentru oameni. Graful de intindere minima este evidentiat in figura 3.9(b). Cu toate acestea graful de intindere minima impune structura de copac fiecarui tipar din puncte pe care il intalneste in cazul tiparului ciclic din figura 3.9 acesta esueaza deoarece va lasa un spatiu undeva. Graful vecinatati relative definit ami jos este mult mai puternic decat garful de intindere minima pentru acest tip de probleme.

3.11 Robotica

nicio discuti elegata de geometria computationala nu poate merge inainte fara a mentiona robotica drept una din principalele aplcati exista mai multe subprobleme ale robotici care vor fi mentionate:

1- palnificarea miscarilor

2- legaturi

3- asamblarea automata

in planificarea miscarilor o problema tipica implica un robot care trebuie sa se descurce intr-un spatiu plin de obstacole aici apar intrebari ca: poate robotul sa se miste din punctul a in b fara a se lovi de obiecte , si daca da sa gaseasca cea mai scurta cale.

O legatura este o colecti e de tije rigide legate impreuna la capete, insa se pot roti livbere. Tijele pot fi legate in mai multe feluri. De exemplu putem forma un lant (legatura lant) sau un poligon inchis (legatura poligonala).

Asamblarea automata este o problema de planificare a miscari unde luam in considerare o colectie de obiecte si trebuie sa sraspundem la intrebari legate de separarea sau mbinarea intr-o

anumaita configurateie iar dca aceste actiuni sunt posibile, ce fel de miscari sunt necesare. O intrebare tipica este aceeea daca o colectie de obiecte poate fi dezasamblata mutand doar cate un obiect. In figura 3.10 este ilustrata o configuratie de 3 obiecte in forma de stea in asa fel incat niciun obiect nu poate fi mutat fara a le deranja pe celelalte, darpot fi separate daca doua din ele sunt mutate simultan.

3.12 geometria computationala geodezica

sa consideram problema localizari cladirilor discutata la sectiunea 2 dar presupunem ca transportul se va face pe apasi ca orasele se afla pe coasta precum in filipine. In aceasta situatie distanta euclidiana dintre doua puncte este inutila, noi avand nevoie de distanta geodezica. In acest exemplu cea mai scurta cale este pe ocean si insulele sunt obstacole care trebuiesc ocolite. O generalizare a invelitori convexe este invelitoarea convexa relativa cunoscuta si ca invelitoarea convexa geodezica.

3.13 Topologia computationala.

Multe probleme fundamentale ale geometriei computationale au o natura topologica. De exemplu: avand un lant poligonal inchis in spatiul tridimensional este normal sa intrebam daca alntul este inodat intrun anume fel sau este simolu. Inspirata de asemenea probleme o noua arie, topologia computationala sa dezvoltat in ultimi ani.

4 Concluzie

Cand calculatorul electronic digital a aparul la inceputul anili\or 40 a fost folosit pentru a realiza calcule numerice imitand scopul predecesorilor sai mecanici. Calculul era numeric atunci si anliza numerica era principala preocupare a savantilor. Insa este dificil dialogul dintre oameni si masini. Un cuvant ocupa mi de cifre iar dezvoltarea limbajelor de programare a ajutat enorm la imbunatatirea interfetei om masina. Dar desigur o poza valoreaza cat o1000 de civinte iar comunicarea om masina din ziua de azi este reamizata aproape exclusiv prin grafica si imagini. Calculul a devenit vizual iar fundatia calculului vizual este geometria computationala.