Math courses taught by the Bolyai Institute

Back Course code and title MMN431E Convex and Algorithmic Geometry Responsible Department Department of Geometry  Responsible instructor Dr. Kincses János  Credit 4  Contact lecture hours 2  Type lecture  Type of exam exam  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 P.M. Gruber, J.M. Wills: Convexity and its applications, Birkhauser, Basel, 1983. Szabó László: Kombinatorikus geometria és geometriai algoritmusok, Polygon, Szeged, 2003. Szabó Zoltán: Bevezető fejezetek a geometriába. B. Grünbaum: Convex Polytopes, John Wiley & Sons, London, 1967. H. Edelsbrunner: Algorithms in Combinatorial Geometry, Springer Verlag, 1987.