Description:

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.

Contents:

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

Seminar contents:

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

Recommended literature:

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.

Keywords:

Computational geometry, Discrete geometry, Geometrical algorithms.

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar