Geometriai algoritmusok

A tantárgy angol neve: Algorithms in Geometry

Adatlap utolsó módosítása: 2017. január 27.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

PhD  képzés

szabadon vagy kötelezően választható tantárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZD304   2/0/0/v 3  
3. A tantárgyfelelős személy és tanszék Dr. Tóth Géza,
A tantárgy tanszéki weboldala www.vik.bme.hu
4. A tantárgy előadója
Név:

 

 

 

Beosztás:

 

 

 

Tanszék, Int.:

 

 

 

Dr. Tóth Géza

 

 

 docens

 

 

 

SZIT

 

 

 

5. A tantárgy az alábbi témakörök ismeretére épít Lineáris algebra, gráfok, algoritmusok elmélete

 
7. A tantárgy célkitűzése A tárgy bemutatja a legfontosabb, legalapvetőbb problémákat, fogalmakat, módszereket, amelyek a geometriai algoritmusok elméletében szerepelnek.

 
8. A tantárgy részletes tematikája

Bevezetés: Konvex burok számítása a síkon,degenerált esetek, számítási hibák, alkalmazások 

Szakaszok metszéspontjainak a kiszámítása,tárolás, több térkép (szakasz elrendezés ) egyesítése 

Sokszögek háromszögelése, a teremőr probléma, sokszögek felosztása monoton részekre, monoton részek háromszögelése

Lineáris programozás a síkon, illetve alacsony dimenzióban,félsíkok metszetének kiszámítása, véletlent használó algoritmus

Pont helyének meghatározása,trapéz felosztás, véletlen algoritmus, degenerált esetek 

Voronoi diagram tulajdonságai és hatékony kiszámítása

Egyenes elrendezések, dualitás, diszkrepancia kiszámítása, k-halmaz ill. k-szint probléma,alsó és felső korlátok 

Delaunay háromszögelés tulajdonságai és hatékony kiszámítása, ponthalmaz háromszögelései

Konvex burok a térben

Gráfok metszési számai,alsó és felső korlátok,elméleti és gyakorlati alkalmazások, metszési szám viszonya más gráf paraméterekhez, véletlen gráf metszési száma  

 
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Előadás
10. Követelmények a.       A szorgalmi időszakban: házi feladat 

 

b.       A vizsgaidőszakban: szóbeli vizsga

 

         c.              Elővizsga: lehetséges

 
11. Pótlási lehetőségek A tanulmányi és vizsgaszabályzatnak megfelelően.
12. Konzultációs lehetőségek Fogadó órákon, illetve személyes egyeztetés alapján

 
13. Jegyzet, tankönyv, felhasználható irodalom de Berg, van Kreveld, Overmars, Schwarzkopf:  Computational Geometry, Springer, 2000.
14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra28
Félévközi készülés órákra22
Felkészülés zárthelyire 
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés40
Összesen90
15. A tantárgy tematikáját kidolgozta Dr.Tóth Géza