Subject description - XP39VPG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
XP39VPG Computational Geometry
Roles:S Extent of teaching:2P+2S
Department:13139 Language of teaching:
Guarantors:Felkel P. Completion:ZK
Lecturers:Felkel P. Credits:4
Tutors:Felkel P. Semester:Z


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. Students who completed course 36VGE cannot enroll.

Study targets:

Analysis and design of effective algorithms for geometric objects.

Course outlines:

Exercises outline:


[1. Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Coputational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5
2. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000
3. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.


Knowledge of Fundamental sorting and searching algorithms. Linear algebra and fundamentals of computer graphics are advantageous. Programming in C++.



Computational geometry, Discrete geometry.

Subject is included into these academic programs:

Program Branch Role Recommended semester
DOKP Common courses S
DOKK Common courses S

Page updated 14.4.2021 05:52:57, semester: Z/2020-1, L/2021-2, L/2020-1, Z,L/2022-3, Z/2021-2, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)