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.
(31/Jan/09) Ex3 was posted in the web page. Enjoy!
(26/Jan/09) There is a minor bug-fix in ex4. You may reload the entire graphics package.
(19/Jan/09) Ex4 was posted in the web page. Enjoy!
(14/Jan/09) The recitation planned for Thursday 15/1/09 is canceled; it will be given in Thursday 22/1/09.
(05/Jan/09) Ex2 was posted in the web page. Enjoy!
(24/Dec/08) Amir will give the recitation of 08/01/09.
(17/Dec/08) Ex1 was posted in the web page. Enjoy!
(15/Dec/08) The lecture of Monday 22/12 will take place in T-201.
(17/Nov/08) The next recitation will take place in Thursday 4/12.
(10/Nov/08) Those who did not register yet to the mailing list of the course are kindly requetsed to do this ASAP! Please e-mail me your full name, id #, faculty, and degree toward which you study. (This is in addition to the formal registration to the course!)
(10/Nov/08) The classes of both today (10/11) and next week (17/11) are canceled. Compensation lectures will be announced. We meet next time in 24/11.
(10/Nov/08) I put in this web page links to slightly old (last year's) versions of the course presentations. The "new edition" will only include a few minor typo fixes, and I will announce its posting when this happens.
|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-4 Home assignments: ~12.5% (Takef, submission in singletons!!);
Running project: ~12.5% (same);
Final exam: 75% (Moed A: Monday 16/Feb/08, 9am, T-4; Moed B: Wednesday 25/mar/08, 5:30pm, T-7.)
Assignment 1 (dry): given 17/12/08, due 01/01/09.
Assignment 2 (dry): given 05/01/09, due 19/01/09.
Assignment 3 (dry): given 31/01/09, due 10/02/09.
Assignment 4 (wet): given 19/01/09, due 19/02/09 (Graphics files, FAQ file)