Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
FIŞA DISCIPLINEI

Codul	Disciplina	
MMG0006	Geometrie computaţională	

Specializarea	Semestrul	Ore: C+S+L	Categoria	Statutul	
Informatică - linia de studiu maghiară	4	2+2+0	specialitate	optionala	
Matematică informatică - linia de studiu maghiară	6	2+2+0	specialitate	optionala	

Titularii de disciplină	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.	
Conţinutul	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	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.