Computational Geometry (236719)
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Amir Vaxman (avaxman@cs.technion.ac.il)
Fall 2010-11


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

(02/Mar/11) Moed B will be held in T-601 from 14:30 till 17:30.

(02/Mar/11) We will hold the exam in 8/3, as planned, but I have now noticed that it was fixed to a ridiculously late time (17:30-20:30). Unless there is an objection, I will move it to a more reasonable time in the afternoon (starting at 14:00 or so).

(20/Feb/11) Grades of Moed A were published! They will reach the secretariat in a few days.

(18/Jan/11) I will use the recitation hour on Thursday, January 20, 2011, instead of the lecture time.

(17/Jan/11) A corrected "Polygons2" file for Ex4 is found here.

(16/Jan/11) I fixed a meeting sechedule - see here.

(13/Jan/11) Please send me possible dates (in 18-20/1) and times (morning!) for individual short meetings (about 15 minutes).

(13/Jan/11) The due date of Ex4 was changed to January 20, 2011.

(3/Jan/11) Ex3 was posted in the web page of the course. Enjoy!

(1/Jan/11) Please note the first message on this list. Ex grades of stdeunts that did not follow it are not recorded anywhere.

(14/Dec/10) Ex4 was posted in the web page of the course. Enjoy!

(13/Dec/10) The lecture of Thursday, 06/Jan/11, is canceled.

(12/Dec/10) Ex2 was posted in the web page of the course. Enjoy!

(22/Nov/10) Plan for the next lectures:
Thursday 25/11: Gill uses Amir's recitation hour at 10:30 (and then gives a lecture at 12:30 as usual);
Sunday 28/11: Gill gives a compensation lecture at 16:30 in T-3;
Thursday 2/12: Gill's lecture is canceled;
Thursday 9/12: Amir gives both a recitation at 10:30 and a lecture at 12:30.

(13/Nov/10) Ex1 was posted in the web page of the course. Enjoy!

(12/Nov/10) The lecture of Thursday, 18/Nov/10, is canceled.

(21/Oct/10) The lecture of Thursday, 28/Oct/10, is canceled. Half a lecture will be given in the recitation time of Thursday, 4/Nov/10.

(21/Oct/10) All students (including free listeners) are kindly asked to join the mailing list of the course. For this to happen, please e-mail me your full name, id #, faculty, and degree toward which you study. (This is in addition to the formal registration to the course! One can leave this mailing list at any time.)


Bibliography

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, 2000.

Library links


Grading Policy

3 Home assignments (dry): ~12.5% (Takef, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (Moed A: Tuesday 08/Feb/11, 9am, Taub 3; Moed B: Tuesday 08/Mar/11, 2:30pm, Taub 601).

Assignment 1 (dry): given 13/Nov/10, due 02/Dec/10.

Assignment 2 (dry): given 12/Dec/10, due 30/Dec/10.

Assignment 3 (dry): given 03/Jan/11, due 24/Jan/11.

Assignment 4 (wet): given 14/Dec/10, due 20/Jan/11 (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.

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

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

(c) Space Partitioning
BSP tress, 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 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.