Marian Ioan MUNTEANU Ana Irina NISTOR

ALGORITMI DE TRIANGULARE

2 0 0 8

Marian Ioan Munteanu Ana Irina Nistor

Algoritmi de triangulare

2 0 0 8

to the memory of Kris Galicki

Cuvant ınainte

”Muchii strambe, muchii albeDiforme si umbriteIn unghiuri cifra v-o cantatiCand drepte cand lungite.

Figura voastra sta portret,scurgandu-se-n carouri

Iar romburile toate-n pieptDin cubul mingilor poetSclipesc patratice, ıncetPe muchii cad ın goluri.”

(R.B.)

Cuprins

Prefata 9

1 Introducere 151.1 Scurt istoric – de la navele romanilor la CAGD . . . . . . . . . . . 151.2 Curbe si suprafete ın CAGD . . . . . . . . . . . . . . . . . . . . . . 171.3 Modelarea imaginii . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.4 Influente si aplicatii stiintifice . . . . . . . . . . . . . . . . . . . . . 22

2 O abordare generala asupra metodelor de triangulare 252.1 Metoda Graham Scan . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.1.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.1.2 Algoritmul . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2 Diagrama Voronoi . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2.1 Problema Oficiului Postal . . . . . . . . . . . . . . . . . . . 312.2.2 Trasarea diagramei Voronoi . . . . . . . . . . . . . . . . . . 36

2.3 Triangularea Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . 442.3.1 Punerea problemei . . . . . . . . . . . . . . . . . . . . . . . 442.3.2 Triangularea Delaunay . . . . . . . . . . . . . . . . . . . . . 47

3 Triangulari optime 573.1 Algoritmul arie MaxMin . . . . . . . . . . . . . . . . . . . . . . . . 57

3.1.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.1.2 Proprietati geometrice ale triangularii ”MaxMin” . . . . . . 583.1.3 Algoritmul . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.1.4 Explicarea algoritmului si a structurilor de date . . . . . . . 63

3.2 Alti algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.2.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.2.2 Elemente geometrice fundamentale . . . . . . . . . . . . . . 673.2.3 Paradigma inserarii laturilor . . . . . . . . . . . . . . . . . 68

7

8 Cuprins

3.2.4 Schema subgrafului . . . . . . . . . . . . . . . . . . . . . . . 703.2.5 The Wall Scheme . . . . . . . . . . . . . . . . . . . . . . . . 71

3.3 Rafinarea laturilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.3.1 Generalitati . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.3.2 Marginirea curburii si a numarului de puncte . . . . . . . . 753.3.3 Algoritmul rafinarii laturilor . . . . . . . . . . . . . . . . . . 763.3.4 Algoritmul de triangulare regulata . . . . . . . . . . . . . . 80

4 Triangularea suprafetelor curbe 834.1 Aplicarea triangularii Delaunay . . . . . . . . . . . . . . . . . . . . 83

4.1.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.1.2 Algoritmul . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.2 Realizarea diagramei Voronoi . . . . . . . . . . . . . . . . . . . . . 924.2.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . 934.2.2 Algoritmul de constructie . . . . . . . . . . . . . . . . . . . 94

5 Aplicatii 1075.1 Supravegherea Galeriei de Arta . . . . . . . . . . . . . . . . . . . . 107

5.1.1 Punerea problemei . . . . . . . . . . . . . . . . . . . . . . . 1075.1.2 Divizarea unui poligon ın regiuni monotone . . . . . . . . . 1125.1.3 Triangularea unui poligon monoton . . . . . . . . . . . . . . 119

5.2 Algoritmul lui Kirkpatrick . . . . . . . . . . . . . . . . . . . . . . . 1225.2.1 Enuntul problemei . . . . . . . . . . . . . . . . . . . . . . . 1235.2.2 Prezentarea algoritmului . . . . . . . . . . . . . . . . . . . . 1235.2.3 Structura lui Kirkpatrick . . . . . . . . . . . . . . . . . . . 127

5.3 Reconstituiri grafice arheologice . . . . . . . . . . . . . . . . . . . . 1285.3.1 Sisteme de realitate virtuala . . . . . . . . . . . . . . . . . . 1285.3.2 Modelarea obiectelor . . . . . . . . . . . . . . . . . . . . . . 131

6 Programe MATLAB 1396.1 Reprezentarea reliefului . . . . . . . . . . . . . . . . . . . . . . . . 1396.2 Locatii teritoriale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1486.3 Triangularea sferei . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

Bibliografie 161

Index 167

Lista figurilor 171

Prefata

Motto: Daca stii ce vrei, ebine. Daca nu, mai bine, ıtialegi pe drum.

Scriind aceasta carte, autorii au ıncercat sa satisfaca exigentele tuturor posibililorcititori, pe de o parte a celor specializati ın domeniu, pe de alta parte a celorpasionati doar de stiintele exacte si nu ın ultimul rand sa starneasca o doza decuriozitate celor ”neinitiati” rasfoind macar aceste pagini.

Cititorii vor regasi notiuni din diverse domenii ale geometriei: elementara, di-ferentiala, computationala sau combinatorica alaturi de algoritmi specifici infor-maticii, care se ımbina ın campul CAGD-ului pentru a contura Universul Trian-gularilor – subiectul cartii de fata. Vedem astfel cum matematicile fundamentaletrec ın domeniul informaticii definind matematicile aplicate prin utilizarea al-goritmilor de triangulare ın probleme practice. Se doreste ca materialul acesteicarti sa ıi sprijine deopotriva atat pe cei care ındragesc geometria sau informatica,dar si pe un cititor ocazional sa faca ınca un pas spre CUNOASTERE, deoarece”matematica este idealul spre care tinde ıntreaga noastra cunoastere”.

Aceasta lucrare prezinta o sinteza a aspectelor importante ın domeniul trian-gularilor suprafetelor. Desi acest domeniu de cercetare este vast, prin lucrarea defata am dorit doar schitarea celor mai studiate metode de triangulare cu o mareaplicabilitate ın practica. Materialul reprezinta doar un punct de initiere pentrucercetari viitoare plecand de la proprietatile de baza ale triangularilor si de lacele mai sugestive aplicatii, prezentate ın cadrul lucrarii.

Termenul de triangulare defineste procedeul prin care, pornind de la o multimede puncte desemnand de regula varfurile unui poligon ın plan, se obtine divizareainteriorului poligonului ın triunghiuri. Evident, acesta ar trebui sa fie cel maisimplu caz de triangulare: triangularea unui poligon. Dar, de cele mai multe ori,ın practica, ne intereseaza cum putem triangula o suprafata, mai ıntai ın 2D apoiın 3D.

9

10 Prefata

Domeniul extins care se ocupa cu studiul algoritmilor de triangulare este Com-puter Aided Geometric Design - CAGD. Termenul CAGD a fost introdus decatre R. Riesenfeld si R. Barnhill ın 1974 cand au organizat o conferinta inti-tulata CAGD la Universitatea din Utah. Au participat cercetatori din StateleUnite si din Europa, acest eveniment putand fi considerat momentul fondatoral CAGD. Zece ani mai tarziu o dezvoltare paralela a ınceput la Institutul deCercetari ın Stiinta Calculatoarelor Schloss Dagstuhl initiata de catre H. Hagen.Acest domeniu de cercetare a aparut sub influenta mai multor arii de studiuatat ın stiinta cat si ın inginerie. Prima lucrare ın CAGD apartine lui I. Faux siM. Pratt intitulandu-se Computational Geometry for Design and Manufacture.Sensul termenului de Geometrie Computationala s-a schimbat de atunci, fiindutilizat pentru a descrie o disciplina preocupata de complexitatea algoritmilor sicare lucreaza cu elementele geometriei discrete.

O importanta suprapunere ıntre CAGD si Geometria Computationala o reprezintaalgoritmii de triangulare. Acestia se ocupa cu determinarea unei multimi de tri-unghiuri avand data o multime 2D de puncte drept varfuri. Descriem ın con-tinuare evolutia algoritmilor de triangulare. Primul algoritm de triangulare afost descris de catre Lenners, ın 1911, folosind tehnica inserarii recursive a di-agonalelor, cu o complexitate de ordinul O(n2). Apoi, ın 1975, ın [50], Meisterspropune ca tehnica algoritmul de decupare a colturilor cu o complexitate maimare, de ordinul O(n3), care mai tarziu a fost ımbunatatit. Garey, Johnson,Preparata si Tarjan ın 1978 propun ca tehnica de triangulare descompunereapoligonului mai ıntai ın piese monotone (cf. [28]). Vezi si [42]. De asemenea siaceasta idee a fost dezvoltata ulterior ın aplicatii practice, de exemplu pentrusupravegherea unei Galerii de Arta din lucrarea [3]. Complexitatea algoritmuluipropus atunci este de ordinul O(n log n). Pornind de la ideea lui Meisters, ın1990, Kong, Everret si Toussaint au dat algoritmul Graham Scan cu o complexi-tate mult mai buna, de ordinul O(kn), unde n reprezinta numarul total de varfuriale poligonului, iar k−1 este numarul de varfuri concave, atingand ordinul maximın cel mai defavorabil caz de O(n2).

Pentru a ne forma o privire de ansamblu asupra acestor algoritmi de triangulare,sa analizam putin sablonul urmat ın linii mari la realizarea unei triangulari. Asacum am mai precizat, cazul cel mai simplu de la care putem ıncepe studiul, ılreprezinta triangularea poligoanelor simple. Un poligon simplu, prin definitie, esteacel poligon care nu contine goluri si ale carui laturi nu se intersecteaza. Primaabordare ıntr-un algoritm de triangulare a fost decuparea colturilor, care a fostutila prin simplitatea ei, dar avand mai mult rol didactic, fiind un punct de pornireın studiul algoritmilor de triangulare. Cazul particular al poligoanelor convexenecesita un algoritm de triangulare ın timp liniar. Astfel triangularea se obtine

Prefata 11

prin trasarea diagonalelor dintr-un varf la celelalte varfuri. Diagonala reprezintaun segment de dreapta interior poligonului care uneste doua varfuri neconsecutiveale acestuia. Dar, descompunerea poligonului initial ın subpoligoane convexe, nueste tocmai simpla, asa ca s-a recurs la divizarea lui ın regiuni monotone. Astfel,un poligon simplu se numeste monoton fata de o dreapta d daca pentru oricedreapta d

′perpendiculara pe d intersectia poligonului cu d

′este un segment de

dreapta, un punct sau multimea vida. Apoi, s-au dat algoritmi de triangularepentru aceste cazuri particulare de poligoane. O situatie interesanta o reprezintacazul triangularii Delaunay si al diagramei Voronoi, aceste doua notiuni fiindduale. Diagrama Voronoi pentru o multime de puncte reprezinta descompunereaplanului ın celule care contin punctele cele mai apropiate de punctele date initial,numite locatii. Pentru fiecare latura a unei celule Voronoi, exista o latura ın tri-angularea Delaunay. Astfel, triangularea Delaunay reprezinta un graf dual al dia-gramei Voronoi pentru aceeasi multime de puncte, care are drept varfuri locatiilesi cate o fata corespunzatoare fiecarei celule Voronoi. Dar, la un moment dat s-adorit obtinerea unor triangulari ale caror laturi sa ındeplineasca anumite restrictii,rezultand astfel triangulari Delaunay constranse. De asemenea, triangularile De-launay se folosesc si pentru reprezentarea suprafetelor 3D. Se realizeaza mai ıntaitriangularea 2D apoi se considera liftul fiecarui punct ımbinandu-se triunghi-urile rezultate ın 3D. Evident, urmand tiparul oricarui domeniu de cercetare, siın cazul algoritmilor de triangulare s-a ıncercat obtinerea de triangulari optime.Optimizarea a mers pe criterii date de lungimea laturilor, masura unghiurilor sauaria triunghiurilor implicate ın triangulare. Criteriile folosite sunt de tip MinMaxsau MaxMin. Primul cuantificator defineste o optimizare facuta peste toate tri-angularile posibile ale multimii de puncte date, iar al doilea specifica optimizareafacuta ın interiorul triunghiurilor, raportata la unghiuri si laturi pentru o singuratriangulare. De exemplu, unghiul MinMax este utilizat pentru triangularea careminimizeaza unghiul maxim ıntr-o triangulare, peste toate triangularile posibileale multimii de puncte date. In triangularea de tip arie MaxMin este maximizataaria celui mai mic triunghi obtinut. Un alt criteriu interesant care este folositpentru determinarea unei triangulari optime, pentru suprafete de aceasta data, ılreprezinta curbura suprafetei. Aceasta va influenta foarte mult forma suprafeteigenerate prin ımbinarea peticelor triunghiulare ın 3D. Astfel, o triangulare cu catse apropie mai mult de aceasta restrictie, cu atat va produce o suprafata maiapropiata de modelul real. De asemenea putem clasifica problemele care au casubiect triangularile optime ın doua categorii: probleme de tip da/nu, cand sun-tem ıntrebati doar daca exista o triangulare care sa respecte un anumit criteriu deoptimizare si probleme de constructie ın care ni se cere determinarea triangulariioptime.

12 Prefata

Acestea ar fi principalele aspecte legate de obtinerea triangularilor. Dar, ın acestdomeniu s-a scris mult, ıncepand cu primul algoritm dupa cum am vazut ıncadin 1911 si se scrie ın continuare. Fara a fi tratate ın ıntregime (ar fi, de altfel,imposibil), ın lucrarea de fata, putem aminti domeniile ın care se pot folosi si sefolosesc triangularile.

In geografia sociala, cand dorim sa determinam aria de influenta a unui factorasupra perimetrului ınconjurator ın 2D, putem folosi diagrama Voronoi. Pentrufiecare locatie vom gasi celula care cuprinde toate punctele cel mai apropiatede locatia corespunzatoare, raportate la toate celelalte locatii. Putem studia siinfluenta pe care ar produce-o adaugarea unui nou factor ın acelasi perimetru.

Domeniul graficii computerizate are la dispozitie printre altele si triangulareaDelaunay utila de exemplu la reprezentarea pe calculator a formelor de relief.Stiind coordonatele unei multimi discrete de puncte ın 2D si ınaltimea core-spunzatoare fiecaruia, putem genera suprafata ın 3D. Folosim aceasta metodadeoarece o reprezentare a valorilor discreta, ar duce la un relief ”ın trepte”, carenu ar da o vizualizare fidela pe calculator a modelului real. De asemenea, re-constituirile grafice ın arheologie folosesc triangularile. Pornind de la o partea unui artefact descoperit ın stare buna dupa sapaturile arheologice, se poategenera pe calculator obiectul initial. Pentru aceasta se folosesc si alte functii deluminozitate, umbrire sau textura.

Problema organizarii eficente a unui sistem de supraveghere video a unei ıncapericu pereti interiori, avand o forma care nu ne permite ”sa vedem” tot spatiul dintr-un punct interior perimetrului a fost pusa ınca din 1973 de catre Victor Klee ıntr-oconversatie cu Vasek Chvatal. Aceasta problema se numeste Problema Galerieide Arta iar rezolvarea ei a venit utilizand de asemenea triangularile. S-a pornitde la premisa ca spatiul 3D poate fi restrans la spatiul 2D, planul dusumelei, careofera la fel de multe informatii. Intrebarea la care se cauta raspuns este: ”De catecamere video avem nevoie pentru a supraveghea Galeria de Arta?”. Raspunsul laaceasta ıntrebare ımpreuna cu solutia problemei, pot fi gasite ın aceasta lucrarela capitolul Aplicatii.

Sa ne gandim la o problema extrem de usor de rezolvat de catre ochiul uman,dar pentru care mult timp nu s-a gasit un algoritm optim: problema localizariipunctelor. Dandu-se o divizare a planului ın celule poligonale si un punct dinplan, se cere sa se precizeze ın care dintre celule se afla acesta. Primul care adezvoltat un astfel de algoritm a fost David G. Kirkpatrick.

Astronomia este ınca un domeniu ın care triangularile ısi gasesc aplicabilitate.Ideea de a utiliza triangularea ın studiul dinamicii planetelor i-a apartinut lui

Prefata 13

Johannes Kepler ın 1620, avand ca rezultat Legile lui Kepler asupra MiscariiPlanetelor. El a pornit de la urmatorul principiu: daca se cunoaste orbita uneiplanete ın jurul Soarelui si locatia planetei respective la doua pozitii diferite alePamantului pe orbita sa, atunci distanta la acea planeta poate fi calculata printriangulare.

In studiul texturii materialelor sunt utilizate triangularile dinamice pentru simu-larea 3D eficienta a materialelor granuloase si testarea coliziunii dintre particule.Daca particulele sunt discuri 2D sau sfere 3D, poate fi folosita o metoda eficientade detectare a ciocnirii bazata pe triangularile dinamice cu greutate.

Diagramele Voronoi pot conduce la generarea fractalilor. Pentru a ıntelege maibine, amintim ca o diagrama Voronoi este formata din celule care contin punctelecel mai apropiate de punctele date initial. Pentru a crea un fractal, dupa ce amcreat o diagrama Voronoi din cateva puncte, vom adauga apoi alte puncte sicream noi diagrame Voronoi ın interiorul fiecareia din cele de dinainte. Repetandprocesul recursiv, putem genera chiar structura unei frunze.

Cercetarea ın medicina este de asemenea un domeniu cu aplicatii ale trian-gularilor. Metode de interpolare bazate pe triangulari 10D sunt utilizate pentrua detecta disfunctii ale inimii analizand modificarea ritmului cardiac din electro-cardiograme. Studiul tumorilor si cresterea celulelor canceroase se poate face pebaza diagramelor Voronoi.

Domeniile prezentate mai sus sunt doar cateva arii ale stiintei si tehnicii careaplica triangularile ca metoda de lucru sau de cercetare.

Prezenta lucrare, prin cele 6 capitole ale sale descrie ın mod gradat o abordareasupra metodelor de triangulare cel mai des ıntalnite si cateva implementari ınMatlab.

Introducerea face o trecere ın revista succinta de la primele mentionari ale uti-lizarii curbelor la constructia barcilor romane, apoi la schitele pe hartie si re-strangerea lor apoi ın formule pana la reprezentarea grafica pe calculator.

Capitolul O abordare generala asupra metodelor de triangulare prezinta metodelede baza, si anume metoda Graham Scan, diagrama Voronoi si triangularea De-launay care vor reprezenta puncte de pornire pentru ceilalti algoritmi prezentatiın urmatorul capitol intitulat Triangulari optime. Algoritmii de optimizare suntclasificati dupa criteriul de optimizare folosit, avand exemple de triangulare op-tima si pentru poligoane, dar si pentru suprafete. Capitolul 4 este dedicat tri-angularii suprafetelor curbe. Am prezentat aplicarea celor doua metode de tri-angulare duale, triangularea Delaunay si realizarea diagramei Voronoi ın cazul

14 Prefata

particular al suprafetelor curbe. In capitolul 5 am inclus cateva aplicatii in-teresante ale triangularilor, cum ar fi: supravegherea unui perimetru folosindcamere video, localizarea punctelor si o aplicatie ın arheologie, la reconstituireaartefactelor. Ultimul capitol prezinta implementarea triangularii Delaunay si re-alizarea diagramei Voronoi utilizand functii specifice MATLAB.

Bibliografia cuprinde ıntreg cadrul informational folosit ın alcatuirea acestei lu-crari. In timp ce se parcurge textul lucrarii, se pot remarca trimiteri directe ladocumentatie pentru a oferi cititorului suportul necesar pentru o ıntelegere catmai buna a termenilor si a conceptelor folosite.

Multumiri. Autorii doresc sa multumeasca referentilor pentru rabdarea de aciti atent manuscrisul si pentru observatiile facute.

Pentru realizarea acestei carti, primul autor a fost suportat partial din GrantCEEX ET 5883 / 2006-2008, ANCS Romania (ca director de grant) si Grant PNII IDEI ID 398 / 2007-2010 (ca membru), derulate la Universitatea Al. I. Cuza,Iasi.

M. I. Munteanu, A. I. Nistorianuarie 2008 Universitatea ‘Al. I. Cuza’ Iasi

Index

Aalgoritmul

arie MaxMin, 57de Casteljau, 18de triangulare regulata, 80ear–cutting, 26lui Fortune, 36, 149lui Kirkpatrick, 122rafinarii laturilor, 76

arborecuaternar, 137octal, 137

arc de spirala, 95arheologie virtuala, 129

BBezier

curbe ∼, 18triunghi ∼, 20

Bernsteinpolinoame ∼, 17

C3–colorare∼ a unui graf, 108∼ a unui poligon ce admite o trian-

gulare, 110CAGD, 10celula Voronoi, 33, 150cerc

de blocare, 73osculator, 86, 95spline, 19

cerc gol, 35, 84(cel mai mare) ∼, 35

coada de prioritate, 63

van Emde-Boas, 63coordonate baricentrice, 20criteriu∼ ariei maxime, 88∼ unghiului minim, 88(de) actualizare a triangularii, 85, 88MaxMin, 68MinMax, 68

curbainofensiva, 94Jordan, 100–103spline, 19spline bicubica, 19spline Wilson-Fowler, 19

Ddescompunere Voronoi cu greutate, 82diagrama

putere Voronoi, 81Voronoi, 139

diagrama Voronoi, 31–33, 36, 37, 39,43, 47, 49, 92–94, 98, 100, 103,106, 148–152

diagrama Voronoi abstracta, 93discretizare

(metoda de) ∼ a laturilor, 86distanta

Euclideana, 32, 96putere, 81

Eelipsa circumscrisa goala∼ ecuatia implicita, 90∼ ecuatii parametrice, 90

eveniment cerc, 39excentricitate MinMax, 69

167

168 Index

FF–petice, 20florar, 18formula

lui Euler, 35, 45, 103, 126French curve, 18functia

distanta, 88Top, 60

functiede zonalitate, 61

functii Matlabcontourf, 144delaunay, 143, 154girddata, 144lighting, 143meshgird, 144plot, 143, 148, 149shading, 143, 144surf, 144trimesh, 143trisurf, 143view, 143voronoi, 149

Ggradul grafului Delaunay, 55graf

Delaunay, 47, 49geometric plan, 67

graf dualal diagramei Voronoi, 47al triangularii, 111din descompunerea Voronoi, 81

graf Voronoi, 98complexitatea unui ∼, 102

Iınaltime MaxMin, 69iluminare

model de ∼ Gouraud, 144model de ∼ Phong, 144

interpolari transfinite, 20interpolare a ınaltimii, 44interval de admisibilitate, 62

JJordan

curba ∼, 100–103

Llatura

ilegala, 45legala, 45non-admisibila, 74, 76

lemaCake-Cutting, 68

locatieeveniment, 38inofensiva, 96, 106teritoriala, 148, 149, 151

Mmasura

unei triangulari, 68mapare

tehnica de ∼, 84Matlab

programe ∼, 139maximizarea minimului, 67mesh, 83metoda

(de) discretizare a laturilor, 86Graham Scan, 25retractiei, 93

modelareaobiectelor, 131poligonala, 132prin compunerea obiectelor, 132, 136prin divizare spatiala, 132, 137prin retele de petice parametrice bicu-

bice, 132, 136solidelor, 132

monotonpoligon ∼, 112

multimeavarfurilor Steiner, 67

Index 169

Nnorma

Euclideana, 71

Oochi de retea, 83optimizare

problema de ∼, 58

Ppanta MinMax, 69paradigma inserarii laturilor, 66, 68pas de blocare, 73plan

sweep, 36, 38pointer

outgoing ∼, 52poligon

de control, 18monoton, 112

primitive geometrice, 136prioritate

de tip Emde-Boas, 65problema de optimizare, 58problema

galeriei de arta, 108MaxMin, 58MinMax, 58oficiului postal, 31

probleme de prag, 59proprietatea

cercului circumscris gol, 79, 89discului gol, 72elipsei circumscrise goale, 89

punctde ıntoarcere, 113eveniment, 36redundant, 81

Rrafinarea laturilor, 73rafinarea regulata a laturilor, 82retea, 83realitatea virtuala, 128reconstituiri grafice arheologice, 128

regiunemonotona, 112y-monotona, 112

regiune Voronoi, 97, 102, 104restaurarea obiectului arheologic, 133

Sschema subgrafului, 66, 68sistem de realitate virtuala

ımbogatita, 130desktop, 130imersiv, 130proiectiva, 130

spatiu parametric, 85, 86spline, 16, 19

cerc ∼, 19curba ∼, 19curba ∼ bicubica, 19curba ∼ Wilson-Fowler, 19

structuralui Kirkpatrick, 127

subpoligoane complementare, 60subpoligon de zona k, 60sunet virtual tridimensional, 131supravegherea galeriei de arta, 107

Tteorema

(lui) Kneser, 95(lui) Vogt, 952-E (two – ears), 27galeriei de arta, 108, 111subgrafului, 70

transformarede modelare, 132

triangulari optime, 58triangulare, 9

de cost minim, 66de tip ınaltime MaxMin, 69de tip excentricitate MinMax, 69de tip greutate minima, 66, 71de tip lungime minima, 66de tip lungime MinMax, 70, 71de tip panta MinMax, 69Delaunay, 44, 55, 88, 90, 139

170 Index

Delaunay conforma, 66, 72Delaunay restrictiva, 77pentru un poligon monoton, 119pentru un poligon simplu, 109, 122pentru un poligon y-strict monoton,

122regulata, 81Steiner, 67

Uunghi MinMax, 58, 69

Vvarf

concav, 26, 28–30convex, 29de ıntrerupere, 114de start, 113de unire, 114final, 114regulat, 113Steiner, 67, 71

voxel, 137

WWall Scheme, 66, 68, 71

Zzonalitate, 60

“Materialul elaborat de autori prezintă o tematică de interes practic pentru comunitatea de matematică aplicată, fizică şi informatică şi pentru perfecţionarea specialiştilor în domeniile menţionate. Lucrarea este prezentată într-un stil matematic riguros, coerent, îngrijit şi atent la detalii. Este bine structurată, iar utilizarea a numeroase figuri este bine-venită. ... Triangularea fiind un subiect de interes major în rezolvarea numerică a unor probleme de actualitate şi formulate matematic, precum şi stilul plăcut al scrierii, fac ca această carte să fie de interes deosebit pentru comunitatea ştiinţifică şi educaţională românească.”

Prof. Dr. Dana PETCU Universitatea de Vest din Timişoara