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.
(13/Jun/19) The exam (first term) will be held in July 7, 2019, at 9:00, hall T-301.
(12/Jun/19) The class of Monday, June 17, 2019 is canceled. We will wrap up the semester on Monday, June 24, 2019.
(09/Jun/19) There will be no class tomorrow, Monday, June 10, 2019. Instead, there will be a guided-reading of the paper whose link was distributed by email. Enjoy!
(03/Jun/19) EX3 was published in the web page. Enjoy!
(03/Jun/19) The recitations of Wednesdays 5/6 and 19/6 will not be held.
(14/May/19) EX2 was published in the web page. Enjoy!
(07/Apr/19) The recitations were moved to Ullmann 708.
(03/Apr/19) EX1 and EX4 were published in the web page. Enjoy!
(15/Mar/19) The first lecture of the semester, planned for Monday, March 18, 2019, will be given by the TA of the course, Mr. Gil Ben-Shachar.
(14/Mar/19) Students who intend to take the course are kindly requested to follow my request from March 3, 2019.
(03/Mar/19) All students (including free listeners) are kindly requested to join the mailing list of the course. (This is in addition, and irrelated, 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.
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, 1998. |
3 Home assignments (dry): ~12.5% (compulsory, submission in
singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Sunday 07/Jul/19, 09:00, at T-301.
2nd term: hopefully no need to!)
Assignment 1 (dry): published 03/Apr/19, due 17/Mar/19
Assignment 2 (dry): published 13/May/19, due 27/May/19
Assignment 3 (dry): published 03/Jun/19, due 17/Jun/19
Assignment 4 (wet): published 03/Apr/19, due 15/May/19 (before ex3!)