Computational Geometry

Semestr: Winter

Range: 2+2s


Credits: 4

Programme type: Undefined

Study form:

Course language:


Principles of computational geometry (CG), data structures and paradigms, methods of geometric search, convex polygons and hulls, applications of convex hull, proximity problems, Voronoi diagrams, triangulation, efficient intersection algorithms, intersection of semispaces and polygonal regions, geometry of rectangles, dual mappings and spaces, convex hull in dual space, algorithms of computer graphics and CG.


Computational geometry, Discrete geometry, Gometrical algorithms

Course syllabus:

1. Subject of computational geometry (CG)
2. Data structures and paradigms in CG
3. Methods of geometric searching
4. Convex hulls and convex polygons
5. Applications of convex hull
6. Proximity problem
7. Voronoi diagram
8. Triangulation of polygons
9. Intersections of segments and lines
10. Intersection of semispaces and polygonal regions
11. Geometry of rectangles
12. Dual mappings and spaces, convex hull in dual space
13. Algorithms of computer graphics & computational geometry
14. Application of CG in Geographic Information Systems

Seminar syllabus:

1. Algorithms of generation and searching 2D-interval trees
2. Location of point in a planar subdivision
3. Overmans's and van Leeuwen's algorithms for dynamical construction of convex hull
4. Construction of Voronoi diagram
5. Proximity problems solved by the Voronoi diagram
6. Algorithms of intersections of line segments
7. Algebra of plane polygons
8. Algebra of rectangles
9. Dual mappings, Line and plane intersections in a dual space
10. Presentation of student projects
11. Presentation of student projects
12. Presentation of student projects
13. Assessment


[1] Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985
[2] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987
[3] de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997