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.
(28/JUL/08) Ex3 was posted. Enjoy!
(13/JUL/08) Ex4 was posted. Enjoy!
(03/JUL/08) Ex2 was posted. Enjoy!
In Monday 7/7, there will be a 3-hour lecture, starting at 9:30.
In Monday 14/7, the 2-hour lecture will be given from 9:30 to 11:30, followed by a 1-hour tutorial (11:30-12:30).
(10/Jun/08) A compensation lecture will be given in Wednesday 18/6 at 12:30, T-5.
(09/Jun/08) The classes of 16/6 and 30/6 are canceled. Compensation lecture(s) will be announced later.
(02/Jun/08) The next tutorial will take place in 23/6. It will cover straight skeletons and medial axes of polygons.
(01/Jun/08) Ex1 was posted. Enjoy!
(23/May/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.
(23/May/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!)
|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: Tuesday 09/Sep/08, time TBA, hall TBA; Moed B: Tuesday 11/Nov/08, hopefully no need to).
Assignment 1 (dry): given 02/06/08, due 19/06/08.
Assignment 2 (dry): given 07/07/08, due 28/07/08.
Assignment 3 (dry): given 28/07/08, due 18/08/08.
Assignment 4 (wet): given 14/07/08, due 14/08/08 (Graphics files, FAQ file)