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.
(9/Jan/12) Next semester I will give an advanced seminar (236801) on polyominoes and polycubes - see syllabus here. All students are encouraged to attend this seminar; note that the registration is manual.
(4/Jan/12) Due to a popular demand, all students may submit Ex4 till January 15, 12:00, without penalty in grade.
(1/Jan/12) A clarification about the Delaunay triangulation of four cocircular points can be found here.
(27/Dec/11) Ex3 was posted in the web page of the course. Enjoy!
(27/Dec/11) A recitation will be held on Thursday, January 19, 2012, and will be dedicated to solving exam questions.
(15/Dec/11) The lecture of Thursday 12/Jan/2012 is canceled.
(15/Dec/11) Maor began to maintain a FAQ file for ex4. See link below.
(7/Dec/11) Ex2 was posted in the web page of the course. Enjoy!
(2/Dec/11) Ex4 was posted in the web page of the course. Enjoy!
(14/Nov/11) Tentative recitation dates: 17/Nov/11, 8/Dec/11, 22/Dec/11. More dates will be published later.
(8/Nov/11) Ex1 was posted in the web page of the course. Enjoy!
(6/Nov/11) The recitation moves permanently to Taub 8.
(6/Nov/11) The lecture of Thursday 17/Nov/2011 is canceled. A compensation lecture will be given on Wednesday 16/Nov/2011 12:30-14:30 in Taub 4.
(3/Nov/11) The strike of the junior staff is over! A recitation will be held today (immediately after the lecture).
(3/Nov/11) Reminder: students (and free listeners) are asked to join the mailing list of the course. (Tips about the exam will be distributed only via email.) See instructions below.
(21/Oct/11) All students (including free listeners) are kindly asked to join the mailing list of the course. For this to happen, please e-mail me your full name, id #, faculty, and degree toward which you study. (This is in addition to the formal registration to the course! One can leave this mailing list at any time.)
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, 2000. |
3 Home assignments (dry): ~12.5% (Takef, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (Moed A: Monday 06/Feb/12, 13:00, location TBA;
Moed B: Thursday 15/Mar/12, time TBA, location TBA).
Assignment 1 (dry): given 10/Nov/11, due 24/Nov/11.
Assignment 2 (dry): given 08/Dec/11, due 29/Dec/11.
Assignment 3 (dry): given 29/Dec/11, due 19/Jan/12.
Assignment 4 (wet): given 08/Dec/11, due 08/Jan/12 (Graphics files, FAQ file)