This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

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.

Prerequisities - what to know before attending the course

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:

Total points Minimum for passing
Seminars 50 25
- Presentation (oral + slides) 10 4
- Homework assignments 40 20
Exam 50 25
- written 40 20
- oral 10 5

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

ECTS grade Pass Fail
Points 100-90 89-80 79-70 69-60 59-50 49-0


Lecturer & Instructor

courses/cg/start.txt · Last modified: 2022/12/02 13:36 by felkepet