Computational Geometry - 236719
Dr. Gill Barequet (barequet@cs.technion.ac.il)
Fall 2002-3


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

(09/02/03)
1. I am back from Miluyim; if you like to ask me questions before the exam, the preferred way is via e-mail.
2. Checked ex3 is found in Debbie's office (T-427).

(05/01/03)
Checked ex1 and ex2 can be obtained either in my office (T-428) or in Debbie's office (T-427).

(01/01/03)
Ex3 is available. Enjoy!

(25/12/02)
I will be away during the first half of January. Therefore:
1. The lectures of Thursday 9/1/03 and Thursday 16/1/03 are canceled;
2. There will be two compensation lectures on Sunday 29/12/02 16:30 in T-8 and on Sunday 5/1/03 9:30 in T-4 (note the different hours and rooms); and
3. Instructions for how to get back ex1 and ex2, and for how to submit ex3, will be distributed separately.

(17/12/02)
Here is a link to a nice applet for computing the Voronoi diagram of a 2D point set (thanks to Evgeni Krimer).

(10/12/02)
The class of Thursday 12/12 is canceled.

(29/11/02)
Ex2 is available. Enjoy!

(21/11/02)
Most of the course's slides are available here.

(12/11/02)
Ex1 is available. Enjoy!

(12/11/02)
All those not registered to the mailing-list of the course are requested to do that in order to have their ex1 grades recorded.

(16/10/02)
Here is a link to good computational-geometry lecture notes, by David Mount from Univ. of Maryland (thanks to Eyal Rozenberg).

(16/10/02)
In order to register to the mailing list of the course (which has nothing to do with the formal registration to the course), please e-mail me ALL OF your full name, id, e-mail account(s) (to which you want messages to be sent), faculty, and degree toward which you are studying.


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 edition), J. O'Rourke, Cambridge University Press, 1998.


Grading Policy

Assignments: 30% (Takef (compulsory), submission in singletons!!);
Final exam: 70% (1st term: Thursday 13/02/03 8am, Taub 3; 2nd term: Sunday 13/04/03, 9am, Taub 4).

Assignment 1: given 12/11/02, due 28/11/02.

Assignment 2: given 29/11/02, due 19/12/02.

Assignment 3: given 02/01/03, due 23/01/03.


Course summary

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

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

(3) 31.10.02 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) 7.11.02 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) 14.11.02 Orthogonal range searching
1D range searching. 2D kd-trees. 2D Range trees.

(6) 21.11.02 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) 28.11.02 Voronoi diagram
Definition, properties, and complexity. A plane-sweep algorithm for computing the Voronoi diagram of a point set.

(8) 5.12.02 Duality; Arrangements of lines
A point-line duality in the plane and its properties. Halfspace discrepancy and its dual problem. Computing an arrangement of lines. Levels in line arrangements.

(9) 19.12.02 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.

(10) 26.12.02 The crossing-number lemma, Miscellaneous
The crossing-number lemma and applications (see minutes). The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes.

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

(12) 2.1.03 Rehearsal
Solved problems from ex's and exams.

(13) 5.1.03 Video
Video segments presented in the annual ACM conferences on computational geometry.