Fundamental techniques, data structures, and algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, the Voronoi diagram and Delaunay triangulation of a point set, polygon triangulation, range search, linear programming, and point location. Some topics of discrete geometry, e.g., the crossing number of a graph and its applications, are also covered.
(02/Jan/21) Ex3 was posted in the web page of the course. Enjoy!
(14/Dec/20) In the wake of Hanukkah, there is no class today.
(01/Dec/20) Ex2 was posted in the web page of the course. Enjoy!
(15/Nov/20) Ex1 was posted in the web page of the course. Enjoy!
(02/Nov/20) Ex4 was posted in the web page of the course. Enjoy!
(20/Oct/20) Students who did not fulfill my request from September 16, 2020, are humbly asked to do it today. (Otherwise they will not get the password for the zoom meetings...)
(16/Sep/20) All students (including free listeners) are kindly requested to join the mailing list of the course. (This is in addition, and irrelated, to the formal registration to the course! One can leave this mailing list at any time.) For joining the mailing list, please e-mail me your full name, id/student #, faculty, and degree toward which you study.
Main text book: Computational Geometry: Algorithms and Applications (3rd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2008. | |
For background: Computational Geometry in C (2nd ed.), J. O'Rourke, Cambridge University Press, 1998. |
As much as I will be happy to hold in-person lectures, we will start the
semester with on-line lectures. If possible, we will switch later to
in-person lectures. Zoom meetings:
Lectures: https://technion.zoom.us/j/518018934?pwd=??? (password
sent by email)
Recitations: https://technion.zoom.us/j/91964945349 (no password)
Passwords will be given only to students and non-students registered to
the mailing-list of the course, see above under "News and Messages."
3 Home assignments (dry): ~12.5% (compulsory, submission in
singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Thursday 04/Feb/21, at ??:??, hall ???;
2nd term: hopefully will not be needed).
If a physical exam is not possible, an on-line exam will
take place.
Assignment 1 (dry): published 16/Nov/20, due 30/Nov/20
Assignment 2 (dry): published 01/Dec/20, due 21/Dec/20
Assignment 3 (dry): published 04/Jan/21, due 18/Jan/21
Assignment 4 (wet): published 02/Nov/20, due 24/Dec/20 (before ex3!)