CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

# Computational Geometry

Code Completion Credits Range Language
B4M39VG Z,ZK 6 2P+2S Czech
Vztahy:
It is not possible to register for the course B4M39VG if the student is concurrently registered for or has already completed the course BE4M39VG (mutually exclusive courses).
The requirement for course B4M39VG can be fulfilled by substitution with the course BE4M39VG.
It is not possible to register for the course B4M39VG if the student is concurrently registered for or has previously completed the course BE4M39VG (mutually exclusive courses).
Garant předmětu:
Petr Felkel
Lecturer:
Petr Felkel
Tutor:
Petr Felkel
Supervisor:
Department of Computer Graphics and Interaction
Synopsis:

The goal of computational geometry is analysis and design of efficient algorithms for determining properties and relations of geometric entities. The lecture focuses on geometric search, point location, convex hull construction for sets of points in d-dimensional space, searching nearest neighbor points, computing intersection of polygonal areas, geometry of parallelograms. New directions in algorithmic design. Computational geometry is applied not only in geometric applications, but also in common database searching problems.

Requirements:

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

Syllabus of lectures:

1. Computational geometry (CG), typical applications, effective algorithm design techniques

2. Geometric searching

3. Geometric searching 2

4. Planar convex hull

5. Convex hull in 3D

6. Voronoi diagram of points

7. Voronoi diagram of line segments. Higher order Voronoi diagrams

8. Triangulations

9. Intersections of line segments and polygons

10. Intersections of polygonal line segments with a rectangular window

11. Arrangements

12. Dual algorithms

13. New directions in algorithmic design

14. Spare lesson

Syllabus of tutorials:

1. Introduction to the form of the seminars, fundamental math. concepts useful in CG.Selection of topics for assignment.

2. Robustness of geometric predicats and constructs.

3. Presentations of the topic assigned, discussion. Evaluation of the presentation materials and evaluation of the speech by classmate students. Ideas for improvements.

4. Presentation of the topic assigned

5. Presentation of the topic assigned

6. Presentation of the topic assigned

7. Presentation of the topic assigned

8. Presentation of the topic assigned

9. Presentation of the topic assigned

10. Presentation of the topic assigned

11. Presentation of the topic assigned

12. Presentation of the topic assigned

13. Assessment

14. Spare

Study Objective:

The course is an informal continuation of fundamental data structures and algorithms courses. You will learn geometric algorithms and data structures allowing for effective computations, e.g., localization of area hit by a ray, computation of intersections and triangulation. You will train presentation and professional discussion skills on the seminars. All of it should not be missing in knowledge of educated progressive Master of Science.

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, 1st ed, 1994 or 2nd ed, 2000

3. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

Note:
Further information:
https://cw.fel.cvut.cz/wiki/courses/cg/start
Time-table for winter semester 2024/2025:
 06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00 roomKN:E-301Felkel P.12:45–14:15(lecture parallel1)Karlovo nám.Šrámkova posluchárna K9 roomKN:E-127Felkel P.09:15–10:45(lecture parallel1parallel nr.102)Karlovo nám.Kotkova cvičebna K4roomKN:E-126Felkel P.11:00–12:30(lecture parallel1parallel nr.101)Karlovo nám.Trnkova posluchárna K5
Time-table for summer semester 2024/2025:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-06-16
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet4698706.html