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.
(01/JUL/06) Due to unexpected Miluyim, the lecture of Thursday 6/7 is canceled.
(19/JUN/06) Ex3 is available. Enjoy!
(18/JUN/06) The lecture of Thursday 22/6 is canceled. A make-up lecture will be given in Wednesday 21/6 at 12:30 in T-6.
(22/MAY/06) Ex2 is available. Enjoy!
(17/MAY/06) A FAQ file for ex4 was initiated.
(09/MAY/06) Ex4 is available. Enjoy!
(28/APR/06) In Sunday 30/4 there will be a 1-hour lecture in T-8 at 14:30.
(24/APR/06, updated 01/MAY/06) There will not be lectures in Thurdays 25/5 and 8/6. I will give two make-up lectures in Sundays 28/5 and 11/6, both at 16:30 in T-8.
(12/APR/06) Ex1 is available. Enjoy!
(27/Mar/06) No recitations will be given in March 30 and April 6, 2006.
(24/Mar/06) There will not be a lecture in Thursday, March 30, 2006.
(04/Mar/06) 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: ~12.5% (Takef, submission in singletons!!);
Running project: ~12.5% (same);
Final exam: 75% (Moed A: Tuesday 11/07/06, 09:00, T-3; Moed B: Tuesday 23/10/06, 11:00, T-401);
Assignment 1 (dry): given 12/04/06, due 27/04/06.
Assignment 2 (dry): given 22/05/06, due 11/06/06.
Assignment 3 (dry): given 20/06/06, due 06/07/06.
Assignment 4 (wet): given 09/05/06, due 12/06/06 (FAQ file; and more).