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.
(30/06/04)
A message from Gur Benjamin (gur_b@inter.net.il - 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.
(27/06/04)
(The following message is not relevant since I immediately got an
objection.)
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.
(24/06/04)
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.
(28/05/04)
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).
(21/04/04)
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.
(19/03/04)
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.
(1) Introduction
(2) Vectors, Plane sweep
(3) DCEL, Polygon triangulation
(4) Linear programming
(5) Orthogonal range searching
(6) Point location
(7) Voronoi diagram
(8) Duality
(9) Line Arrangements
(10) Delaunay triangulation
(11) The crossing-number lemma
(12) 2-point site Voronoi diagrams
(13) A few theorems