A+ | A- | Ø
 
  • Magyar
 
 
Saturday, 29 November 2014
Math courses taught by the Bolyai Institute

Back

Course code and titleMMN431G Konvex és algoritmikus geometria gyak.
Responsible DepartmentDepartment of Geometry 
Responsible instructorDr. Kincses János 
Credit
Contact lecture hours
Typeseminar 
Type of examsignature 


Curriculum

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.


Suggested literature

  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.