Computational Geometry

Common page for subjects B4M39VG, BE4M39VG, XP39CG.

• The third assignment has been released.
• Starting from week 4, the lecture room has changed from K1 (KN:E-107) to K9 (KN:E-301).

The goal of computational geometry is the 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.

You definitely should know the fundamental sorting and searching algorithms, understand the concept of operational and memory complexity, and be able to write programs in C++. Knowledge of linear algebra, fundamentals of computer graphics would also be an advantage.

1. Seminars are compulsory (two absences are allowed).
2. Every student (or pair of students) is assigned a different topic for individual study. He/she prepares slides and presents them on the seminar. The topics available.
3. All students code the homework assignments (in C++).
4. Both, the presentation and the homework must be uploaded in the electronic form to the ( upload system brute).
   • Sources of the presentation (.ppt, .odp, .tex + figures, … more files in an archieve file).
   • The homework as a single .cpp file and/or the report file (.txt, .pdf,…) according to the homework handout.

Conditions for awarding of the assessment:

• Attending of the seminars (2 absences are tolerated without a necessity to excuse)
• Oral presentation according to the plan
• Presentation slides uploaded by 1 week after the presentation (later deliverable is penalized by -5 points)
• Upload of the homework programs (later deliverable is penalized by -1 point penalty for every 24 hours after the deadline, but not more than -5 points penalty)
• Minimum 25 points from seminars

Students who receive the assessment are allowed to take the exam. The exam focuses on theoretical knowledge from the lectures, seminars, and individual studies. The exam has a written part and an oral part. Additional positive or negative points can be obtained during the oral exam (in the extrema, fundamental lack of knowledge may yield to a failure (F)).

For the exam, a maximum of 50 points can be awarded. A minimum of 25 points must be achieved for a passing grade:

The final grade is assigned according to the sum of seminars and exam points.

• Academic principles, Plagiarism and cheating
• dcgi
• Timetable - BE Rozvrh - B

• Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Computational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5 (available in 10 exemplars in the CTU library located in National Technical Library building (NTK), Dejvice Campus, 5th floor, signature QA447 .C66 2008). Web page.
• Mount, D.: Computational Geometry Lecture Notes for Spring 2020 (older versions: Fall 2016 - Table of contents 2016, Fall 2016, Fall 2014, Spring 2007, contents 2007)
• O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1st ed, 1994 or 2nd ed, 2000
• Preparata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

Petr Felkel