Computational Geometry

Lecturer:

Petr Felkel (gar.)

Tutor:

Petr Felkel (gar.)

Supervisor:

Department of Computer Graphics and Interaction

Synopsis:

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.

Requirements:

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

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Analysis and design of effective algorithms for geometric objects.

Study materials:

[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.

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Doctoral studies, daily studies (compulsory elective course)
• Doctoral studies, combined studies (compulsory elective course)
• Doctoral studies, structured daily studies (compulsory elective course)
• Doctoral studies, structured combined studies (compulsory elective course)