Computational Geometry - NDMI097
Title: Výpočetní geometrie
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: doc. RNDr. Martin Tancer, Ph.D.
Opinion survey results   Examination dates   Schedule   Noticeboard   
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
The primary goal of computational geometry is the construction of algorithms and data structures for solving problems stated in terms of basic geometric objects, such as points, lines, polygons, convex polytopes and others. A lot of emphasis is given on the best possible asymptotic comlexity of the algorithms. The main application areas include computer graphics and data visualisation, computer vision, design of 3D objects and robotics. Knowledge in the scope of the course "Introduction to Combinatorial and Computational Geometry" is assumed.
Literature -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
  • Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational geometry: Algorithms and applications, Third edition, Springer-Verlag, Berlin, 2008, ISBN: 978-3-540-77973-5. [http://www.cs.uu.nl/geobook/]
  • Franco Preparata and Michael Shamos, Computational geometry: An introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985, ISBN: 0-387-96131-3

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
  • models of computation (Real RAM)
  • convex hull in R^2 and R^3
  • triangulation of a polygon
  • orthogonal range searching in R^2 and R^d
  • point localization and trapezoid decomposition
  • construction of the Voronoi diagram and the Delaunay triangulation
  • z-buffer, binary space partition, BSP tree
  • quadtree
  • visibility graph