Computational Geometry (236719)
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Spring 2005-06


Syllabus

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

(01/JUL/06) Due to unexpected Miluyim, the lecture of Thursday 6/7 is canceled.

(19/JUN/06) Ex3 is available. Enjoy!

(18/JUN/06) The lecture of Thursday 22/6 is canceled. A make-up lecture will be given in Wednesday 21/6 at 12:30 in T-6.

(22/MAY/06) Ex2 is available. Enjoy!

(17/MAY/06) A FAQ file for ex4 was initiated.

(09/MAY/06) Ex4 is available. Enjoy!

(28/APR/06) In Sunday 30/4 there will be a 1-hour lecture in T-8 at 14:30.

(24/APR/06, updated 01/MAY/06) There will not be lectures in Thurdays 25/5 and 8/6. I will give two make-up lectures in Sundays 28/5 and 11/6, both at 16:30 in T-8.

(12/APR/06) Ex1 is available. Enjoy!

(27/Mar/06) No recitations will be given in March 30 and April 6, 2006.

(24/Mar/06) There will not be a lecture in Thursday, March 30, 2006.

(04/Mar/06) In order to join the mailing-list of the course, please send me by e-mail the following details: full name, id, faculty, and degree. (This is in addition to the formal registration to the course!)


Bibliography

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.

Library links


Grading Policy

3 Home assignments: ~12.5% (Takef, submission in singletons!!);
Running project: ~12.5% (same);
Final exam: 75% (Moed A: Tuesday 11/07/06, 09:00, T-3; Moed B: Tuesday 23/10/06, 11:00, T-401);

Assignment 1 (dry): given 12/04/06, due 27/04/06.

Assignment 2 (dry): given 22/05/06, due 11/06/06.

Assignment 3 (dry): given 20/06/06, due 06/07/06.

Assignment 4 (wet): given 09/05/06, due 12/06/06 (FAQ file; and more).


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.

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