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

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

(23/05/05) The submission of ex4 (the mini-project) was postponed to Monday, June 6.

(14/05/05) A make-up lecture will be given in Sunday, May 22, 2005, at 16:30, in T-5.

(14/05/05) In spite of a previous message, the second half of lecture #7 will not be given in the recitation of 16/5.

(09/05/05) The second half of lecture #7 (VD) will be given in the recitation of 16/5.

(02/05/05) The lectures of 19/5 and 9/6 are canceled.
(Part of) a lecture will be given in the recitation of 9/5.

(18/04/05) A FAQ file for ex4 is maintained here.

(03/04/05) Clarification for Q5b in EX1: The question refers to binary trees (node degrees are 1, 2, or 3). (Thanks to Mordo Shalom.)

(27/03/05) Ex4 (running project) was published. Enjoy!

(26/03/05)
(a) Ex1 was published. Enjoy!
(b) The recitation of Monday, April 4, will take place.

(24/03/05) The lecture of 31/3 is canceled.

(20/03/05) Students who did not register yet to the mailing list are urged to do this immediately. Home-assignment submission will not be allowed without this.

(17/03/05) A make-up lecture will take place next Sunday, 20/3, at 16:30, in T-6.

(17/03/05) Due to unexpected late return to Israel, there will be no lecture today. I will attempt to schedule a make-up lecture for next Sunday, 20/3.

(03/03/05) The recitation of Monday 7/3/05 is canceled.

(15/02/05) 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: 10% (Takef, submission in singletons!!);
Running project: 15% (same);
Final exam: 75% (Moed A: Friday 01/07/05, 09:00, T-6; Moed B: Monday 05/09/05, 09:00, T-?);

Assignment 1 (dry): given 26/03/05, due 11/04/05.

Assignment 2 (dry): given 18/04/05, due 05/05/05.

Assignment 3 (dry): given 06/06/05, due 23/06/05.

Assignment 4 (wet): given 27/03/05, due 06/06/05 (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.

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