Forgot your password?
Computational Geometry - Spring 2022
Spring 2022
0368-3173-01
Course hours & location: Monday, 16:10-19:00 @ Dach Auditorium
Recitation: Thursday, 13:10-14:00 @ Check Point 001
Grader: Tal Levi, tallevi@mail.tau.ac.il
The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.
Bibliography:
The main textbook of the course is:
Computational Geometry: Algorithms and Applications (CGAA), 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.
A bibliographic list for the course
Slides:
I will often use slides that accompany the main textbook of the course. The slides are by Marc van Kreveld and they can be found
at the following site: Geometric Algorithms
Assignments, Examination and Grade:
The standard assignments will account for 10% of the final grade, in case they improve the final grade.
The grade in the final exam will account for the remaining 90% of the grade in the course.
Exam(ple), pdf file, traditional style
About halfway through the course (probably earlier), we will present a programming assignment.
We encourage you to submit the programming assignment as well. This is not mandatory.
If however you do submit it, then your grade breakdown will be 10% the standard assignments,
15% the programming assignment, and 75% the final exam. Here as well,
the assignments grades will be counted toward the final grade only if they improve it.
The assignments will appear in Moodle; they should be submitted as a pdf file.
Assignment no. 1, due: March 14th, 2022.
Assignment no. 2, due: April 1st, 2022.
Assignment no. 3, due: April 25th, 2022.
Programming project, due: June 9th, 2022. Additional information.
Assignment no. 4, due: May 23rd, 2022.
Assignment no. 5 (optional), due: June 10th, 2022.
Course Summary:
Below you'll find a very brief summary of what was covered in class during the semester.
This should not be taken as a complete description of the course's contents.
For an outline of the course, see for example, the course summary in the Fall 2020-2021 computational geometry course.
Motivation and techniques. A slow convex hull algorithm. Graham's O(n log n) algorithm (Chapter 1 in CGAA). (slides1.) Lower bound. Gift-wrapping algorithm for computing the convex hull, Jarvis's March (Preparata-Shamos, Section 3.3.3).
