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.
A message from Gur Benjamin (firstname.lastname@example.org - reply to him!):
"Some of us would like to postpone the date of the test to between the 20-23 of July (Due to other tests next week). This will happen only if ALL the students will agree. Please reply to this mail with agree/disagree. If you accept the postponement and agree only to one of the days between the 20-23 of July, do mention it. Please reply as soon as possible, since the original date is next week."
(28/06/04) There will not be a lecture in Thursday 1/7/04. No make-up lecture is planned either. 8-)
(28/06/04) Due to popular demand, the submission of ex3 was extended until Sunday 4/7 noon (12:00). Submission is in Debbie's office (T-428).
(27/06/04) Last reminder: it is COMPULSORY to register to the mailing list of the course in order to pass it. TODAY is the last day for doing this.
(The following message is not relevant since I immediately got an
There is a popular request to delay the exam in 7/7 from 9am to a later time. 1pm is not an option since some students have another exam at that time. So we will attempt to have the exam at 5pm (17:00) that day - place TBA, unless there is any (even a SINGLE) objection. If you object, please let both me and Mika (mika@cs) know.
As mentioned several times, ALL students must register to the mailing list of
the course! (Instructions found in this web page.)
Victoria D., Valery G., and Olga M. - You haven't done this so far, risking that your ex's grades will not be considered.
(24/06/04) The exam was set to 7/7, at 9m (to the best of my knowledge). This is done by the secretariat, not by me. If you wish to change the time and/or date, you need to reach a unanimous consensus and let the secretariat know ASAP. Arie Matsliah (ariem@tx) is coordinating this.
(17/06/04) Ex3 was posted in the web page of the course.
The submission of ex2 was postponed (again!) to Tuesday 1/6/04 10am.
Note that a make-up lecture will take place in Sunday 30/5/04 4:30pm in T-3, and then we'll have a break for about two weeks.
(27/05/04) Thanks again go to Marc Segal for uncovering typos in Q4(a) of ex2. Instead of O(n^2) and O(n), it should be Theta(n^2) and Theta(n), respectively.
(19/05/04) The submission of ex2 was postponed to 30/5/04.
(17/05/04) Two typos in Q2 of ex2 (in the running times) were corrected. Thanks to Marc Segal for uncovering the errors. Please download again ex2.
(15/05/04) As expected, the open-house duty in Thursday 20/5 forces me to cancel the lecture of that date. At the moment no make-up lecture is fixed.
(15/05/04) There are still four students (Dmitry R, Lev G, Valery G, and Olga M) who submit ex's without registering to the course's mailing list (as I explained before, it has nothing to do with registering to the course); this prevents me from keeping records of their grades. If you happen to know these students, please urge them to register to the mailing list asap.
(11/05/04) Ex2 was posted in the web page of the course.
(06/05/04) Checked ex1's are available in Debbie's office (T-427).
(04/05/04) I was notified by the authorities that the make-up lecture of 30/5 will take place in T-2 (instead of T-3).
Note changes in lectures schedule:
Thursday 29/4: no lecture (studies are as in Tuesday).
Thursday 27/5: no lecture (Yom Gesher).
Sunday 30/5: make-up lecture at 16:30 in T-3.
Thursday 3/6: lecture is canceled.
Thursday 10/6: lecture is canceled.
(04/04/04) Ex1 was posted in the web page of the course.
Unfortunately I will not be able to give the make-up lecture scheduled
for Sunday 21/3, so it is canceled.
Also, I will be away 24-31/3. Thus, the lecture of 25/3 is canceled. Actually I will land in the morning of 1/4, so I hope I will be in a good-enough shape to give the lecture of that date.
Finally, there will be another make-up lecture on Sunday 18/4 16:30 Hall T-6.
(18/03/04) I released the slides of the first three lectures. Enjoy!
(18/03/04) ** CANCELED ** There will be a make-up lecture on Sunday 21/3/04 16:30 in T-6.
(17/03/04) In order to join the mailing-list of the course, please write me an e-mail message with all the following details: full name, id, faculty, and degree. This does not replace the formal registration to the course.
|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 ed.), J. O'Rourke, Cambridge University Press, 2000.|
3 or 4 Home assignments: 30% (Takef, submission in singletons!!);
Final exam: 70% (Moed A: 07/07/04; Moed B: 23/09/04);
Assignment 1: given 04/04/04, due 22/04/04.
Assignment 2: given 11/05/04, due 27/05/04.
Assignment 3: given 17/06/04, due 01/07/04.