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.
1. I am back from Miluyim; if you like to ask me questions before the exam, the preferred way is via e-mail.
2. Checked ex3 is found in Debbie's office (T-427).
Checked ex1 and ex2 can be obtained either in my office (T-428) or in Debbie's office (T-427).
Ex3 is available. Enjoy!
I will be away during the first half of January. Therefore:
1. The lectures of Thursday 9/1/03 and Thursday 16/1/03 are canceled;
2. There will be two compensation lectures on Sunday 29/12/02 16:30 in T-8 and on Sunday 5/1/03 9:30 in T-4 (note the different hours and rooms); and
3. Instructions for how to get back ex1 and ex2, and for how to submit ex3, will be distributed separately.
Here is a link to a nice applet for computing the Voronoi diagram of a 2D point set (thanks to Evgeni Krimer).
The class of Thursday 12/12 is canceled.
Ex2 is available. Enjoy!
Most of the course's slides are available here.
Ex1 is available. Enjoy!
All those not registered to the mailing-list of the course are requested to do that in order to have their ex1 grades recorded.
Here is a link to good computational-geometry lecture notes, by David Mount from Univ. of Maryland (thanks to Eyal Rozenberg).
In order to register to the mailing list of the course (which has nothing to do with the formal registration to the course), please e-mail me ALL OF your full name, id, e-mail account(s) (to which you want messages to be sent), faculty, and degree toward which you are studying.
Main text book:
Computational Geometry: Algorithms and Applications (2nd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2000.
Computational Geometry in C (2nd edition), J. O'Rourke, Cambridge University Press, 1998.
Assignments: 30% (Takef (compulsory), submission in singletons!!);
Final exam: 70% (1st term: Thursday 13/02/03 8am, Taub 3; 2nd term: Sunday 13/04/03, 9am, Taub 4).
Assignment 1: given 12/11/02, due 28/11/02.
Assignment 2: given 29/11/02, due 19/12/02.
Assignment 3: given 02/01/03, due 23/01/03.