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.
(16/06/05) In spite of a previous message, there will not be a make-up lecture in 20/6 (the entire material was taught today).
The lecture of 23/6 is canceled.
A make-up lecture will be given in the recitation of 20/6.
(23/05/05) The submission of ex4 (the mini-project) was postponed to Monday, June 6.
(14/05/05) A make-up lecture will be given in Sunday, May 22, 2005, at 16:30, in T-5.
(14/05/05) In spite of a previous message, the second half of lecture #7 will not be given in the recitation of 16/5.
(09/05/05) The second half of lecture #7 (VD) will be given in the recitation of 16/5.
The lectures of 19/5 and 9/6 are canceled.
(Part of) a lecture will be given in the recitation of 9/5.
(18/04/05) A FAQ file for ex4 is maintained here.
(03/04/05) Clarification for Q5b in EX1: The question refers to binary trees (node degrees are 1, 2, or 3). (Thanks to Mordo Shalom.)
(27/03/05) Ex4 (running project) was published. Enjoy!
(a) Ex1 was published. Enjoy! (b) The recitation of Monday, April 4, will take place.
(24/03/05) The lecture of 31/3 is canceled.
(20/03/05) Students who did not register yet to the mailing list are urged to do this immediately. Home-assignment submission will not be allowed without this.
(17/03/05) A make-up lecture will take place next Sunday, 20/3, at 16:30, in T-6.
(17/03/05) Due to unexpected late return to Israel, there will be no lecture today. I will attempt to schedule a make-up lecture for next Sunday, 20/3.
(03/03/05) The recitation of Monday 7/3/05 is canceled.
(15/02/05) In order to join the mailing-list of the course, 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: 10% (Takef, submission in singletons!!);
Running project: 15% (same);
Final exam: 75% (Moed A: Friday 01/07/05, 09:00, T-6; Moed B: Monday 05/09/05, 09:00, T-?);
Assignment 1 (dry): given 26/03/05, due 11/04/05.
Assignment 2 (dry): given 18/04/05, due 05/05/05.
Assignment 3 (dry): given 06/06/05, due 23/06/05.
Assignment 4 (wet): given 27/03/05, due 06/06/05 (FAQ file).