Computational Geometry (236719)
Dr. Gill Barequet (
Spring 2003-04


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.

News and Messages

(30/06/04) A message from Gur Benjamin ( - 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.

Grading Policy

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.

Course summary and slides

(1) Introduction
What is Computational Geometry? Example problems and motivations. Naive, incremental, and divide-and-conquer convex-hull algorithms.

(2) Vectors, Plane sweep
Vector cross product and orientation test. Segment-intersection test. Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.

(3) DCEL, Polygon triangulation
The DCEL data structure. Application of DCEL to a map-overlay algorithm. Its use for polygon union, intersection, and difference. The art-gallery theorem. Partitioning a simple polygon into monotone pieces. Triangulating a monotone polygon.

(4) Linear programming
What is linear programming. A D&C algorithm for half-planes intersection. An incremental algorithm for half-planes intersection. Randomized linear programming. Unbounded linear programming. Smallest enclosing disk of a 2D point set.

(5) Orthogonal range searching
1D range searching. 2D kd-trees. 2D Range trees.

(6) Point location
Slabs structure. Trapezoidal map. A randomized incremental algorithm for computing a trapezoidal map. Worst- and average-case Time/Space analysis of the algorithm. Handling degeneracies.

(7) Voronoi diagram
Definition and variants. A plane-sweep algorithm for computing the Voronoi diagram of a point set.

(8) Duality
A point-line duality in the plane and its properties.

(9) Line Arrangements
Line arrangements and their properties. The zone theorem. Computing an arrangement of lines. Levels in line arrangements. Halfspace discrepancy and its dual problem.

(10) Delaunay triangulation
Triangulation of a point set. Angle vector and the triangulation that maximizes it. Delaunay triangulation and its relation to the angle vector. A randomized incremental algorithm for computing the Delaunay triangulation.

(11) The crossing-number lemma
The crossing-number lemma and applications.

(12) 2-point site Voronoi diagrams
Some 2-point site distance functions and their respective Voronoi diagrams.

(13) A few theorems
The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes.