Computational Geometry
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| BE4M39VG | Z,ZK | 6 | 2P+2S | English |
- 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. Proximity problems, Voronoi diagram.
7. Voronoi diagram applications.
8. 2D a 3D triangulations
9. Intersections of line segments
10. Intersections of polygonal areas and halfspaces
11. Geometry of parallelopids.
12. Dual algorithms.
13. New directions in algorithmic design
14. Spare lesson
- Syllabus of tutorials:
-
1. Introduction to the form of the seminars, Selection of topics for assignment.
2. Individual preparation of the presentations
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 2023/2024:
-
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
Mon Tue Wed Thu Fri - Time-table for summer semester 2023/2024:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Open Informatics - Computer Vision and Image Processing (compulsory course of the specialization)
- Open Informatics - Computer Graphics (compulsory course of the specialization)
During a review of study plans, the course B4M39VG can be substituted for the course BE4M39VG.