A tantárgy adatlapja
1. A képzési program adatai
1.1 Felsőoktatási intézmény	Babeş-Bolyai Tudományegyetem	
1.2 Kar 	Matematika és Informatika Kar	
1.3  Intézet	Magyar Matematika és Informatika 	
1.4 Szakterület	Matematika, Informatika	
1.5 Képzési szint	Mesteri	
1.6 Szak / Képesítés	Oktatói matematika, Komputacionális matematika	

2. A tantárgy adatai
2.1 A tantárgy neve	 Algoritmikus geometria 	
2.2 Az előadásért felelős tanár neve	Varga György Csaba	
2.3 A szemináriumért felelős tanár neve	Varga György Csaba	
2.4 Tanulmányi év	I.	2.5 Félév	I.	2.6. Értékelés módja	Vizsga	2.7 Tantárgy típusa	 kötelező –alap	

3. Teljes becsült idő (az oktatási tevékenység féléves óraszáma)
3.1 Heti óraszám	3	melyből: 3.2 előadás	2	3.3 szeminárium/labor	1	
3.4 Tantervben szereplő össz-óraszám	42	melyből: 3.5 előadás	28	3.6 szeminárium/labor	12	
A tanulmányi idő elosztása:	Óra	
A tankönyv, a jegyzet, a szakirodalom vagy saját jegyzetek tanulmányozása	36	
Könyvtárban, elektronikus adatbázisokban vagy terepen való további tájékozódás	40 	
Szemináriumok / laborok, házi feladatok, portfóliók, referátumok, esszék kidolgozása	50	
Egyéni készségfejlesztés (tutorálás)	32	
Vizsgák	6	
Más tevékenységek: ..................		
3.7 Egyéni munka össz-óraszáma	   158	
3.8 A félév ősz-óraszáma	   200	
3.9 Kreditszám	    8(M) ill. (MI)	

4. Előfeltételek (ha vannak)
4.1 Tantervi	•	Nincsen	
4.2 Kompetenciabeli	•	Elemi geometria, gráfelmélet, algoritmika, konvex analízis	

5. Feltételek (ha vannak)
5.1 Az előadás lebonyolításának feltételei	•	Táblával és videoprojektorral felszerelt előadó	
5.2 A szeminárium / labor lebonyolításának feltételei	•	Táblával és videoprojektorral felszerelt előadó	

6. Elsajátítandó jellemző kompetenciák
Szakmai kompetenciák	•	Gráfelmélet alapelemeinek megismerése
•	Sokszögek háromszögesítése és más geometriai felbontások megismerése
•	Voronoi diagrammok és ezek tulajdonságainak megismerése	
Transzverzális kompetenciák 	•	A lineáris és konvex programozási feladatoknál való alkalmazás
•	Delaunay háromszögesítés hatékony kiszámítása
•	Modellek szerkesztése nem-euklideszi geometriákra 
•	Voronoi diagrammok különböző tudományterületeken való alkalmazása	

7. A tantárgy célkitűzései (az elsajátítandó jellemző kompetenciák alapján)
7.1 A tantárgy általános célkitűzése	•	Az előadás célja, hogy a diákokkal ismertessük az Algoritmikus geometria fogalmait és módszereit, amelyeknek jelentős alkalmazásaik vannak több tudományterületen, mint: alkalmazott matematika, fizika, biológia, informatika. Itt megemlítjük a Voronoi diagramok alkalmazását az asztronómiában, molekuláris fizikában, biológiában és más tudományterületeken. 
•	 A diákok az elsajátított ismereteket és módszereket felhasználhatják az oktatásban és a kutatásban.	
7.2 A tantárgy sajátos célkitűzései
	•	Azon ismeretek elsajátítása, amelyek szükségesek a lineáris és konvex programozáshoz

8. A tantárgy tartalma
8.1 Előadás	Didaktikai módszerek	Megjegyzések	
1.	Gráfok  
-  a gráfelmélet elemei
-  síkgráfok,  Euler tétele	
      Előadás	[1], [4]	
 2. Egyenesek metszése
- szakaszok metszése
- algoritmusok a szakaszok  metszéspontjainak meghatározására
- algoritmusok komplexitása	

      Előadás	[2], [3], [4], [7]	
 3. A sík felosztása             
- a sík két egymást fedő felosztásának meghatározása
- két egymást fedő sokszög meghatározása	
       Előadás	[2]	
 4. Sokszögek háromszögesítése
- a művészeti galéria tétele
- egy sokszög felbontása monoton részekre	
       Előadás	[2], [5], [7]	
 5. Felbontások 
- egy monoton sokszög háromszögesítése
- egy sokszög háromszögesítése	
       Előadás	[2], [5]	
6.  Konvex halmazok
- egy ponthalmaz konvex burkolójának a meghatározása
- konvex burkoló meghatározása (Jarvis,  Graham algoritmusai)	

       Előadás	[2], [4], [5]	
7. Voronoi diagramok
- Voronoi diagramok és azok alapvető  tulajdonságai
- Voronoi diagramok szerkesztése a  “divide et impera” algoritmussal	
        Előadás	[2], [5], [6]	
8. Háromszögesítések
- egy véges ponthalmaz háromszögesítése 
- a Delaunay háromszögesítés
- a Delaunay háromszögesítés meghatározása	
         Előadás	[2], [5], [6]	
9. Geometriai felbontások
- vágások peremének a meghatározása
- vágások peremének a megszerkesztése	
          Előadás	[2], [3], [7]	
10. Dinamikus és kinematikus Voronoi diagramok
- dinamikus és kinematikus Voronoi  diagramok
- dinamikus Delaunay háromszögesítés és   alkalmazásai	
         Előadás	[2], [5], [6]	
11. Nagyobb dimenziók
- Voronoi diagramok nagyobb dimenziókban               
- Delaunay felbontások
 - egy alkalmazás a csillagászatban	

         Előadás	[2], [5], [6], [12]	
12.   Egy alkalmazás a biológiában
-  növényfajták ábrázolása Voronoi diagramok segítségével
- egy alkalmazás a növények növekedésében           	
         Előadás	[2], [5], [9]	
13.   Egy alkalmazás a proteinek szerkezetének leírásában
-  a Voronoi diagramok alkalmazása a  proteinek szerkezetének leírásában          
-  a proteinek térfogatának kiszámítása 	

          Előadás	[2], [5], [8]	
14.    Egy fizikai alkalmazás
- az oxigén atomok szekezete
- egy alkalmazás a folyadékok mehanikájában	
          Előadás	[2], [5], [10], [11]	
Könyvészet
1. ANDRÁSFAI B.: Introductory graph theory, Akadémiai Kiadó – North Holland, 1987.
2. BOISSONAT, J.-D., YVINEC, M.: Algorithmic Geometry, Cambridge, 1998. 
3. JIANER, Ch.: Computational Geometry: Methods and Applications, Texas A & M University, 1996. 
   4. CORMEN, T.H., LEISERSON, CH.E., RIVEST, R.R.: Introducere în algoritmi, Ediţia în limba română, Computer Libris Agora, 2000.
5. de BERG, M., CHEONG, O., van KREVELD, M., OVERMARS, M.: Computational Geometry (3rd edition), Springer-Verlag, 2008.
6. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
7. PREPARATA, F.P., SHAMOS, M.I.:Computational Geometry, Springer, 1985. 
8. RICHARDS, F.M.: The interpretation of protein structures: total volume, group volume distributions, and packing density. In In the Journal of Molecular Biology, volume 82, pages 1–14, 1974.
9. ROQUE, W. L., CHOSET, H.: The green island formation in forest fire modeling with voronoi diagrams. In In the 3rd  Center for Geometric Computing Workshop on Compuational Geometry, 1998.
10. SEREZHKIN, V. N., BLATOV, V. A., SHEVCHENKO, A. P.: Voronoi-dirichlet polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155–161, 1995.
11. SERRANO, M., FABRITIIS, P., ESPANOL, E., FLEKKY, G, COVENEY, P.V.: Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A: Mathematics and General, volume 35, pages 1605–1625, 2002.
12. ZANINETTI, L.: The galaxies distribution as given from the voronoi diagrams. In In the Journal of Astronomy and Astrophysics, Italy.     	
8.2 Szeminárium / Labor	Didaktikai módszerek	Megjegyzések	
1.	- algoritmusok komplexitása
-  adatszerkezetek
- vermek és sorok	
Feladatok megoldása,
problematizálás, beszélgetés	[2], [3]	
2.	- bináris kereső fák 
- piros-fekete fák
- B-fák 	
Feladatok megoldása,
problematizálás, beszélgetés	[2], [3]	
3.	- sokszögek háromszögesítése   	Feladatok megoldása,
problematizálás, beszélgetés	[2], [4], [5]	
4.	- sima geometriai objektumok  Voronoi  diagramja
- a felületek formák szerkesztése	Feladatok megoldása,
problematizálás, beszélgetés	[2], [4]	
5.	-  nem euklidészi metrikák
- a Poincare modell	Feladatok megoldása,
problematizálás, beszélgetés	[1], [2]	
6.	- affin diagramok
- súlyozott diagramok	Feladatok megoldása,
problematizálás, beszélgetés	[2], [7]	
7.	- a vágások széleinek a megszekesztése	Feladatok megoldása,
problematizálás, beszélgetés	[2], [4], [5]	
8.	- félsíkok metszetei
- a legkisebb területű háromszög 	Feladatok megoldása,
problematizálás, beszélgetés	[2], [4], [5]	
9.	- a proteinek szerkezete
	Feladatok megoldása,
problematizálás, beszélgetés	[8]	
10.	 - a folyadékok dinamikája	Feladatok megoldása,
problematizálás, beszélgetés	[10], [11]	
11.	- galaxisok eloszlása	Feladatok megoldása,
problematizálás, beszélgetés	[12]	
12.	-  az oxigén atomok szerkezete	Feladatok megoldása,
problematizálás, beszélgetés	[9]	
13.	-  egyéni dolgozat bemutatása (I)	Előadás, beszélgetés		
14.	-  egyéni dolgozat bemutatása (II)	Előadás, beszélgetés		
Könyvészet
1. ANDERSON, J.W.: Hyperbolic Geometry, 2nd edition, Springer, 2005.
2. BOISSONAT, J.-D., YVINEC, M.: Algorithmic Geometry, Cambridge, 1998.
3. CORMEN, T.H., LEISERSON, CH.E., RIVEST, R.R.: Introducere în algoritmi, Ediţia în limba română, Computer Libris Agora, 2000.      
4. de BERG, M., CHEONG, O., van KREVELD, M., OVERMARS, M.: Computational Geometry (3rd edition), Springer-Verlag, 2008.
5. JIANER, Ch.: Computational Geometry: Methods and Applications, Texas A & M University, 1996. 
6. O'ROURKE, J.: Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
7. POPESCU, I.P., Geometrie afină şi euclidiană, Editura Facla, Timişoara, 1984.
8. RICHARDS, F.M.: The interpretation of protein structures: total volume, group volume distributions, and packing density. In In the Journal of Molecular Biology, volume 82, pages 1–14, 1974.
9. SEREZHKIN, V. N., BLATOV, V. A., SHEVCHENKO, A. P.: Voronoi-dirichlet polyhedra for uranium(vi) atoms in oxygencontaining compounds. In the Russian Journal of Coordination Chemistry, volume 21, pages 155–161, 1995.
10. SERRANO, M., FABRITIIS, P., ESPANOL, E., FLEKKY, G, COVENEY, P.V.: Mesoscopic dynamics of voronoi fluid particles. In In the Journal of Physics A: Mathematics and General, volume 35, pages 1605–1625, 2002.
11. STORA, D., AGLIATI, P.O., CANI, M.P., NEYRET, F., GASCUEL, J.D.: Animating lava flows. In Graphics Interface, 1999.
12. ZANINETTI, L.: The galaxies distribution as given from the voronoi diagrams. In In the Journal of Astronomy and Astrophysics, Italy.  	

9. Az episztemikus közösségek képviselői, a szakmai egyesületek és a szakterület reprezentatív munkáltatói elvárásainak összhangba hozása a tantárgy tartalmával.
•	 A tantárgy tartalma megegyezik az egyetemi oktatásban a fontosabb egyetemeken oktatott algoritmikus geometria hagyományos tartalmával.
•	A tárgy segítséget nyújt a számítógép kínálta lehetőségek kiaknázásában geometria problémák megoldása esetén.
•	A tárgy segítséget nyújt külöböző fizikai, kémiai, biologiai illetve csillagászati jelenségek megértésében.
•	Az előadások során megismert modellek jobb megértésében és megszerkesztésében segít.

10. Értékelés
Tevékenység típusa	10.1 Értékelési kritériumok	10.2 Értékelési módszerek	10.3 Aránya a végső   jegyben	
10.4 Előadás 	Alapfogalmak és alaptételek ismerete	Félév végi szóbeli vizsga	        40%	
10.5 Szeminárium / Labor	Feladatmegoldások helyessége	Szemináriumi tevékenység	        30%	
		Egyéni dolgozat bemutatása 	        30%	
10.6 A teljesítmény minimumkövetelményei	
•	Az Algoritmikus geometria legalapvetőbb fogalmainak, módszereinek és alkalmazási lehetőségeinek ismerete.
•	Tudjon megoldani egyszerűbb feladatokat minden fejezetből.	

Kitöltés dátuma			Előadás felelőse			Szeminárium felelőse
          2012 szeptember 24		         Varga György Csaba			Varga György Csaba
Az intézeti jóváhagyás dátuma	                                                               Intézetigazgató	
    ..........................						                          Szenkovits Ferenc