Every Monday (18:15–21:00) in room 377 of the Faculty of Mechanics and Mathematics.
In the week 3–7 November 2014, Prof. Alexander Wolff has delivered the course "Computational Geometry II" in room 301.
is planned on Wednesday 17 December 2014 at 12:00--14:00 in Room 216
Please read the following carefully!
- You can use a single-sided A4 paper with hand-written notes. No further tools are allowed.
- The exam consists of six tasks. You don’t have to solve all of them. The correct solution of a task yields the number of points stated next to the task. The total number of points is 75. Your solutions to Prof. Banakh’s homework assignments can earn you another 25 points. Together, this yields at most 100 points. You pass this course if you collect at least 50 points.
- Use separate sheets of paper to write down your solutions. Make sure to write your name on each sheet! On the first sheet, also mention your university and study program.
- You have 120 minutes for solving the problems.
- Make sure that you completely understand each problem!
- For your solutions, don’t write more lines of text than the number of points that you can get.
- If you are asked to “analyze the running time” of an algorithm, you should give some hints as to why your claims are true.
- A sample of examination problems can be downloaded here.
Results of the exam can be downloaded here.
The final grade for the course can be calculated by the formula:
Final score = (grades for exam) + (grades for homeworks)/3.
According to this formula the following students have got more than 50:
1. Parubochyi V. (55+82/3=82)
2. Pylypovych M. (53+65/3=75)
3. Spodar N. (55+61/3=75)
4. Kryven M. (28+95/3=60)
5. Skvarko K. (40+53/3=58)
6. Barabash O. (30+68/3=52)
7. Tytar I. (30+68/3=52)
A discussion of the results of the exam is planned on 26 December 2014 in (or near) Room 377 at 13:00.
The lectures course covered the following topics:
1. Convex hulls in 2D and 3D
2. Line Segment Intersections
3. Polygon Triangulation
4. Linear programming
5. Orthogonal Range Searching
6. Point Location
7. Voronoi Diagram
8. Delaunay Triangulation
9. Robot Motion Planning
10. Visibility Graphs
Textbook and Other Materials
The course will be based on the following textbook:
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, Springer, 3rd edition, 2008.
We plan to write programs in Java, which can be downloaded from:
Java programs realizing some algorithms discussed during the lectures can be found here.
Grades for the Homeworks + Class Activity