A(E)4M39VG - Computational Geometry


  • New version of Mount, D.: Computational Geometry Lecture Notes for Fall 2014 is online


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.

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 electronic form to the ( upload system).
    • Sources of the presentation (.ppt, .odp, .tex + figures, … more files in an archieve file).
    • The homework as 1 file according to its 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 afterwards (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/ae4m39vg/start.txt · Last modified: 2017/06/26 09:39 by felkepet