A+ | A- | Ø
 
  • English
 
 
2014. november 27. csütörtök 11:44
A Bolyai Intézet által aktuálisan oktatott kurzusok

Vissza

A tárgy kódja és neveMMN431G Konvex és algoritmikus geometria gyak.
Meghirdető tanszék(csoport)Geometria Tanszék 
Felelős oktatóDr. Kincses János 
Kredit
Heti óraszám
Típusagyakorlat 
Számonkérésaláírás 


Tematika

Konvexitás, Charatheodory-tétel, Radon-tétel, Helly-tétel. Szeparációs tételek. Konvex halmazok polaritása, lapok és extremális részhalmazok.
Poliéderek algebrai leírása, a lineáris programozás alapfeladata. Farkas-lemma. Politopok laphálója, felső korlát tétel. Politopok kombinatorikus típusa, Steinitz tétele. Poliéderek merevsége, Cauchy tétele.
Konvexitás: konvex burok, konvex burok és konvex kombináció, konvex halmazok metszetei, konvex poliéderek laphálója, kombinatorikus izomorfizmus, élgráfok és poliédertípusok, rúdrendszerek merevsége.
Algoritmikus geometria: poligonok és pontrendszerek triangulálása, konvex burkot kereső algoritmusok, poliéderek reprezentációja, DV-cella keresése. Zárt töröttvonal belsejének meghatározása, ponthalmazok szétdarabolása. Legbővebb konvex részhalmaz keresése. Minimális háromszögek. Legközelebbi szomszéd keresése, pontrendszerek alakja. Képtárproblémák. Mozgástervezés.


Ajánlott irodalom

  1. P.M. Gruber, J.M. Wills: Convexity and its applications, Birkhauser, Basel, 1983.
  2. Szabó László: Kombinatorikus geometria és geometriai algoritmusok, Polygon, Szeged, 2003.
  3. Szabó Zoltán: Bevezető fejezetek a geometriába.
  4. B. Grünbaum: Convex Polytopes, John Wiley & Sons, London, 1967.
  5. H. Edelsbrunner: Algorithms in Combinatorial Geometry, Springer Verlag, 1987.