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.
(09/02/03)
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).
(05/01/03)
Checked ex1 and ex2 can be obtained either in my office (T-428) or in
Debbie's office (T-427).
(01/01/03)
Ex3 is available. Enjoy!
(25/12/02)
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.
(17/12/02)
Here is a
link
to a nice applet for computing the Voronoi diagram of a 2D point set
(thanks to Evgeni Krimer).
(10/12/02)
The class of Thursday 12/12 is canceled.
(29/11/02)
Ex2 is available. Enjoy!
(21/11/02)
Most of the course's slides are available
here.
(12/11/02)
Ex1 is available. Enjoy!
(12/11/02)
All those not registered to the mailing-list of the course are requested
to do that in order to have their ex1 grades recorded.
(16/10/02)
Here is a
link
to good computational-geometry lecture notes, by David Mount from Univ. of
Maryland (thanks to Eyal Rozenberg).
(16/10/02)
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.
For background:
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.