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.
(28/JUL/07) The lecture of Monday, July 30, is canceled.
(16/JUL/07) Ex3 is availbale. Enjoy!
(25/JUN/07) Both Ex2 and Ex4 are availbale. Enjoy!
(18/JUN/07) The due date of Ex1 was set to next Monday 25/6.
(14/May/07) Ex1 is found in the web page of the course. It will formally be distributed when the strike is over.
(11/Apr/07) I will not be able to deliver the lecture of 16/4 (Yom HaZikaron LaSho'a VelaGvura). A compensation lecture will be given in 18/4, 12:30, hall T-8. (modulo strikes 8-).
(10/Apr/07) Those who did not register yet to the mailing list of the course are kindly requetsed to do this ASAP!
(16/Mar/07) CG students are required to join the mailing-list of the course! In order to do this, please send me by e-mail the following details: full name, id, faculty, and degree. (This is in addition to the formal registration to the course!)
|Main text book: Computational Geometry: Algorithms and Applications (2nd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2000.|
|For background: Computational Geometry in C (2nd ed.), J. O'Rourke, Cambridge University Press, 2000.|
3 Home assignments: 12% (Takef, submission in singletons!!);
Running project: 13% (same);
Final exam: 75% (Moed A: Sunday 09/09/07, 9am, hall T-6; Moed B: Tuesday 23/10/07, ???, ???)
Assignment 1 (dry): given ??/05/07, due ??/??/07.
Assignment 2 (dry): given 26/06/07, due 15/07/07.
Assignment 3 (dry): given 16/07/07, due 09/08/07.
Assignment 4 (wet): given 24/06/07, due 24/07/07 (FAQ file)