Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Algorithms in Geometry

    A tantárgy neve magyarul / Name of the subject in Hungarian: Geometriai algoritmusok

    Last updated: 2017. január 27.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics     		PhD  or MSc
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZD304   2/0/0/v 3  
    3. Course coordinator and department Dr. Tóth Géza,
    Web page of the course www.vik.bme.hu
    4. Instructors Géza Tóth (SZIT)
    5. Required knowledge Basic knowledge of linear algebra, graph theory, theory of algorithms
    is required.
    7. Objectives, learning outcomes and obtained knowledge The course presents the fundamental problems,
    concepts, and methods in computational geometry.
    8. Synopsis Computation of convex hull in the plane, degenerate cases, robustness.
     
    Segment intersection, computing the overlay of two maps.

    Polygon triangulation, its computation, the art gallery problem.

    Linear programming in low dimensions, incremental and randomized.
    Smallest enclosing disc.

    Range searching, range trees.

    Point location, trapezoidal maps. Randomized incremental approach.

    Voronoi diagrams, properties and computation.

    Arrangements of lines, point-line duality, levels in an arrangement,
    discrepancy.

    Triangulations of point sets, Delaunay triangulations, properties,
    relationship with the Voronoi diagram, computation.

    Computing the convex hull in the space.

    The k-set problem, bounds and applications.

    Crossing numbers of graphs, results, bounds, related problems.

    9. Method of instruction Lecture
    10. Assessment Exam
    11. Recaps

     

    Additional exam(s) according to the rules of the University

    12. Consultations On office hours or possibly at any other time.
    13. References, textbooks and resources Mark de Berg, Otfried Cheong (Schwarzkopf), Marc van Kreveld, Mark Overmars:
    Computational Geometry: Algorithms and Applications, Springer, 2008.

    14. Required learning hours and assignment
    Kontakt óra 28
    Félévközi készülés órákra 22
    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és 40
    Összesen 90
    15. Syllabus prepared by Géza Tóth (SZIT)