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.
The lecture of January 22, 2013, is canceled due to the general elections.
With a grain of smile, here is a piece of
propaganda I got from a colleague
(26/Dec/12) Ex3 was posted in the web page of the course.
(18/Dec/12) Ex4 was posted in the web page of the course.
(02/Dec/12) Ex2 was posted (well ahead of time) in the web page of the course.
(27/Nov/12) Recitation slides about fractional cascading were posted in the web page.
(20/Nov/12) The class of today is canceled.
(04/Nov/12) Ex1 was posted in the web page of the course.
(21/Sep/12) All students (including free listeners) are kindly requested to join the mailing list of the course. (This is in addition to the formal registration to the course! One can leave this mailing list at any time.) For joining the mailing list, please e-mail me (barequet@cs) your full name, id #, faculty, and degree toward which you study.
(20/Sep/12) Since I will be abroad at that time, the second term (Moed B) of the course will NOT be held in March 13, 2013! Hopefully there will not be a need for such an exam. If yes, an alternative date will be coordinated with the relevant student(s).
|Main text book: Computational Geometry: Algorithms and Applications (3rd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2008.|
|For background: Computational Geometry in C (2nd ed.), J. O'Rourke, Cambridge University Press, 2000.|
3 Home assignments (dry): ~12.5% (Takef, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (Moed A: Tuesday 05/Feb/13, time TBA, location TBA; no Moed B!)
Assignment 1 (dry): given 06/Nov/12, due 20/Nov/12.
Assignment 2 (dry): given 11/Dec/12, due 28/Dec/12.
Assignment 3 (dry): given 01/Jan/13, due 22/Jan/13.
Assignment 4 (wet): given 18/Dec/12, due 29/Jan/13 (Graphics files, sample input files, FAQ file)