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

Back

Course code and titleMMN431E Convex and Algorithmic Geometry
Responsible DepartmentDepartment of Geometry 
Responsible instructorDr. Kincses János 
Credit
Contact lecture hours
Typelecture 
Type of examexam 


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.