Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Geometrie computaţională
Cod
Semes-
trul
Ore: C+S+L
Tipul
Specializarea
MG008
6
2+1+0
optionala
Matematici aplicate
Cadre didactice indrumatoare
Conf. Dr. BLAGA Paul Aurel,  pablagacs.ubbcluj.ro
Prof. Dr. VARGA Csaba Gyorgy,  csvargacs.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
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.
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline