BME VIK - Geometriai algoritmusok

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

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)