Computational Geometry (236719)
Lecturer: Prof. Gill Barequet (
TA: Mira Shalah (
Fall 2014-15


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

Mira composed a file with a few solved exam questions: click here.

Janis: please send me an email message. Thanks! Gill

Ex3 was posted in the web page of the course.

There will be no tutorial on Monday 29/Dec/14.

Ex2 and Ex4 were posted in the web page of the course.

This is your chance to influence the day+time in which the course Discrete Algorithmic Geometry (238739) will be given next semester! Send me today by email your preferences and/or constraints.

There will be no tutorial on Monday 8/Dec/14.

There will be no tutorial on Monday 1/Dec/14.

- The tutorial of Monday, November 24, 2014, will be held.
- Mira's reception hour will be held on Mondays at 14:30.
- Home assignments should be submitted to Mira's email address (mshalah@cs) or to her mailbox on floor 5.

There will be no recitation on Monday, November 10, 2014. However, on Monday, November 17, 2014, the recitation will be held.

Correction: There will be recitation on Monday, November 3, 2014.

Slides of all lectures and recitations are available below.

There will be no tutorial this Monday 27/Oct/14.

I brought the issue of the language, in which lectures will be given, to the highest ranks in the faculty, namely the dean and three vice deans. The conclusion was that the lectures will be given in English IF there are non-English speakers in the audience, and Hebrew support (that is, translation to Hebrew) will be given upon request.

(20/Sep/14) All students (including free listeners) are kindly requested to join the mailing list of the course. (This is in addition 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.

Grading Policy

3 Home assignments (dry): ~12.5% (Takef, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Tuesday 17/Feb/15, time TBA, location TBA; 2nd term: Monday 16/Mar/15, hopefully no need to!)

Assignment 1 (dry): given 10/Nov/14, due 24/Nov/14.

Assignment 2 (dry): given 22/Dec/14, due 05/Jan/15.

Assignment 3 (dry): given ??/???/1?, due ??/???/1?.

Assignment 4 (wet): given 22/Dec/14, due 22/Jan/15 (Graphics files, FAQ file)

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.

(a) Planar graphs
Graph definition, planar graphs, Euler's formula, the DCEL structure.

(3) Polygon triangulation
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.

(b) Polygonal skeletons
Straight skeleton of a polygon and a polyhedron. Their complexities, and algorithms to compute them.

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

(c) Fractional cascading
Fractional cascading for range searching.

(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.

(d) Voronoi diagram
More and alternative definitions. Lloyd's algorithm.

(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.

(e) Space Partitioning
BSP trees, quadtress.

(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 a few applications of it.

(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.