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/Mar/11) Moed B will be held in T-601 from 14:30 till 17:30.
(02/Mar/11) We will hold the exam in 8/3, as planned, but I have now noticed that it was fixed to a ridiculously late time (17:30-20:30). Unless there is an objection, I will move it to a more reasonable time in the afternoon (starting at 14:00 or so).
(20/Feb/11) Grades of Moed A were published! They will reach the secretariat in a few days.
(18/Jan/11) I will use the recitation hour on Thursday, January 20, 2011, instead of the lecture time.
(17/Jan/11) A corrected "Polygons2" file for Ex4 is found here.
(16/Jan/11) I fixed a meeting sechedule - see here.
(13/Jan/11) Please send me possible dates (in 18-20/1) and times (morning!) for individual short meetings (about 15 minutes).
(13/Jan/11) The due date of Ex4 was changed to January 20, 2011.
(3/Jan/11) Ex3 was posted in the web page of the course. Enjoy!
(1/Jan/11) Please note the first message on this list. Ex grades of stdeunts that did not follow it are not recorded anywhere.
(14/Dec/10) Ex4 was posted in the web page of the course. Enjoy!
(13/Dec/10) The lecture of Thursday, 06/Jan/11, is canceled.
(12/Dec/10) Ex2 was posted in the web page of the course. Enjoy!
(22/Nov/10)
Plan for the next lectures:
Thursday 25/11: Gill uses Amir's recitation hour at 10:30 (and then
gives a lecture at 12:30 as usual);
Sunday 28/11: Gill gives a compensation lecture at 16:30 in T-3;
Thursday 2/12: Gill's lecture is canceled;
Thursday 9/12: Amir gives both a recitation at 10:30 and a
lecture at 12:30.
(13/Nov/10) Ex1 was posted in the web page of the course. Enjoy!
(12/Nov/10) The lecture of Thursday, 18/Nov/10, is canceled.
(21/Oct/10) The lecture of Thursday, 28/Oct/10, is canceled. Half a lecture will be given in the recitation time of Thursday, 4/Nov/10.
(21/Oct/10) 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: Tuesday 08/Feb/11, 9am, Taub 3;
Moed B: Tuesday 08/Mar/11, 2:30pm, Taub 601).
Assignment 1 (dry): given 13/Nov/10, due 02/Dec/10.
Assignment 2 (dry): given 12/Dec/10, due 30/Dec/10.
Assignment 3 (dry): given 03/Jan/11, due 24/Jan/11.
Assignment 4 (wet): given 14/Dec/10, due 20/Jan/11 (Graphics files, FAQ file)