Львівський національний університет імені Івана Франка

Факультет електроніки та комп'ютерних технологій

вул. Драгоманова, 50

Computational Geometry

Regular lectures

Every Monday (18:15–21:00) in room 377 of the Faculty of Mechanics and Mathematics.


Block course

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!


  1. You can use a single-sided A4 paper with hand-written notes. No further tools are allowed.
  2. 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.
  3. 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.
  4. You have 120 minutes for solving the problems.
  5. Make sure that you completely understand each problem!
  6. For your solutions, don’t write more lines of text than the number of points that you can get.
  7. If you are asked to “analyze the running time” of an algorithm, you should give some hints as to why your claims are true.
  8. A sample of examination problems can be downloaded here.


Good luck!



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.


Java tutorials:



Grades for the Homeworks + Class Activity


No NameFaculty Home1Home2Home3Home4Home8Home9ExtraTotal
1 Kryven M.Appl.Math.18+9+16203095
2 Parubochyi V.Electronics.99171223+ +1082
3 Basiuk Yu.Mathematics6412916181378
4 Barabash O.Appl.Math.961420118568
5 Tytar IrynaMathemitics93132012966
6 Pylypyvych M.Mathematics20++22022+65
7 Kryzhanovskyi V.Electronics.041710231165
8 Spodar N.Appl.Math.646121612561
9 Kasperska L.Mathematics811+1376955
10 Skvarko K.Appl.Math.8391212953
11 Hrytsyk Yu.Appl.Math.8371112849
12Bereza OleksandraMathematics3361120447
13 Duban MariaMathematics112141542
14 Simkiv M.Mathematics44101733
15 Koltok I.Mathematics3351122
16 Zhydyk V.Mathematics3351122
17 Yatsulka N.Mathematics3351122
18 Savchyn R.Mathematics3351122
19 Perun R.Mathematics3351122
20 Hrytsan O.Mathematics3351122
21 Baran I.Mathematics3351122
22 Lekh N.Mathematics3351122
23 Demchuk Yu.Mathematics3351122
24 Mykulyak A.Polytech1010
25 PavlyukPolytech1010
26 Beshley A.Appl.Math.729
27 Borachuk I.Appl.Math.88
28 Vertsimaha A.Appl.Math.88
17-60 All others00



Про нас



Електронне навчання



Наші партнери





© 2003- Міжкафедральна лабораторія високопродуктивних обчислювальних систем,
Факультет електроніки та комп'ютерних технологій, Львівський національний університет імені Івана Франка
Останні зміни ▲ Нагору ▲