Computational Geometry - 236719
Dr. Gill Barequet
Spring 2002

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

(10/10/02) The final grades are available here.

(06/08/02) The votes for a new date for Moed B contained one veto on changing it. Therefore the exam will take place in its original date: 7/OCT/2002.

(09/07/02) Ex3 was checked by my TA. You can get your marked solutions either in my office (T-428) or from Debbie Miller (T-427).

(25/06/02) Ex2 was checked by my TA. You can get your marked solutions from Debbie Miller, office T-427.

(20/06/02) Ex3 is available. Enjoy!

(09/06/02) Apropos the previous message. Debbie is NOT my TA, so don't complain to her about grades...

(02/06/02) Ex1 was checked by my TA. You can get your marked solutions from Debbie Miller, office T-427.

(31/05/02) Ex2 is available. Enjoy!

(27/05/02) I got 5 ex1 submissions of people not registered to the course's mailing list. These students are requested to register asap!

(08/05/02) The lectures of 19/5, 23/5 and 6/6 are canceled. There will be one compensation lecture in 16/6 4:30pm in T-6.

(26/04/02) Ex1 is available. Enjoy!

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

(18/03/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 send me 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, M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 1997.

For background:
Computational Geometry in C (2nd edition), J. O'Rourke, Cambridge University Press, 1998.

Grading Policy

Assignments: 30% (Takef, submission in singletons!!);
Final exam: 70% (Moed A: Friday 12/07/02 8am, T-8 and T-9; Moed B: Monday 07/10/02 8:30am, T-8).

Assignment 1: given 26/04/02, due 17/05/02.

Assignment 2: given 31/05/02, due 17/06/02.

Assignment 3: given 20/06/02, due 04/07/02.

Course summary

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

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

(3) 11.4.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. Triangulating a monotone polygon. Partitioning a simple polygon into monotone pieces.

(4) 25.4.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) 2.5.02 Orthogonal range searching
1D range searching. 2D kd-trees. 2D Range trees.

(6) 9.5.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) 30.5.01 Voronoi diagram
Definition and variants. A plane-sweep algorithm for computing the Voronoi diagram of a point set.

(8) 13.6.01 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) 16.6.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) 20.6.01 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) 27.6.01 2-point site Voronoi diagrams
Some 2-point site distance functions and their respective Voronoi diagrams.