Disciplina: Geometrie computaţională	Cod: MMG0006	

Semestrul	Ore: C+S+L	Tipul	Specializarea	
4	2+0+2	optionala	Informatică	

Cadre didactice indrumatoare	Prof. Dr. VARGA Csaba Gyorgy, csvarga@cs.ubbcluj.ro
Conf. Dr. BLAGA Paul Aurel, pablaga@cs.ubbcluj.ro
Lect. Dr. MAKO Zoltan, zmako@math.ubbcluj.ro	
Obiective	Cursul isi propune introducerea studentilor in geometria computationala. Geometria computationala este deosebit de importanta in multe domenii ale matematicilor aplicate si ale informaticii. La seminar se vor discuta unele dintre aceste aplicatii, completate cu exercitii menite sa contribuie la aprofundarea si clarificarea materialului la curs	
Continut	1. Fundamente.
1.1. Fundamente algoritmice.
1.2. Conditii geometrice.
1.3. Modele de calcul.
2. Cautare geometrica.
2.1. Localizarea punctelor.
2.2. Cautare regionala.
3. Invelitori convexe.
3.1. Constructia invelitorilor convexe in plan.
3.2. Invelitori convexe in dimensiuni mai mari decat doi.
3.3. Aplicatii in statistica.
4. Probleme de apropiere.
4.1. Problema celei mai apreopiate perechi.
4.2. Diagrama Voronoi.
4.3. Arbori minimali euclidieni.
4.4. Triangulari plane.
4.5. Diagrame Voronoi generalizate.
4.6. Intervale si acoperiri.
5. Intersectii.
5.1. Aplicatii plane.
5.1.1. Intersectia poligoanelor convexe.
5.1.2. Intersectia segmentelor de dreapta.
5.1.3. Intersectia semiplanelor.
5.1.4. Nucleul unui pologon plan.
5.2. Aplicatii spatiale.
5.2.1. Intersectia poligoanelor convexe.
5.2.2. Intersectia semispatiilor.
6. Geometria dreptunghiurilor.
6.1. Aria si perimetrul unei reuniuni de dreptunghiuri.
6.2. Conturul unei reuniuni de dreptunghiuri.
6.3. Intersectia dreptunghiurilor	
Bibliografie selectiva	1. DE BERG, M. - VAN KREFELD, M. - OVERMARS, M. - SCHWARZKOPF, O.:  Computational Geometry,  (2nd edition), Springer, 2000
2. BOISSONNAT,  J.-D. - YVINEC, M.: Algorithmic Geometry, Cambridge University Press, 1998
3. CORMEN, T.H. - LEISERSON, C.E. - RIVEST, R.L.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusets, 1990
4. EDELSBRUNNER, H.: Algorithms in Combinatorial Geometry, Springer, 1997
5. GOODMAN, J. - O'ROURKE, J. (eds.): Handbook of  Discrete and Computational Geometry, CRC Press, 1997
6. OKABE, A. - BOOTS, B. - SUGIHARA, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley, 1992
7. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987
8. O'ROURKE, J.: Computational Geometry in C, Cambridge University Press, 1994
9. PREPARATA, F.P. - SHAMOS, M.I.: Computational Geometry, Springer, 1985	
Evaluare	Vor fi mai multe lucrari de control pe parcursul semestrului, studentilor li se va cere sa implementeze unii dintre algoritmi. La sfarsit va fi un examen, care va tine cont si de activitatea din timpul semestrului