The course covers fundamental algorithms for solving geometric
problems such as computing convex hulls, intersection of line
segments, Voronoi diagrams, polygon triangulation, and linear
programming in low-dimensional space.
News and Messages
The 29/6 class is canceled; it will be given in 27/6 instead in F-413.
Ex3 will be given in 15/6. The due date (strict this time) is 29.6.
The due date of ex2 was 8/6. I will not accept submissions later than 15.6.
The exam stays on 13/7/99. Hour will be published later.
Please notify me by E-mail ASAP if you want/don't want to move
the exam from 13/7/99 to 29/6/99.
The exam date was set to Tuesday 13.7.99.
The due date of ex1 is 27/4. I will not accept submissions later than 6.5.
All students who are not on my mailing list should send me an E-mail note.
Computational Geometry: Algorithms and Applications,
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry in C,
Cambridge University Press.
Assignments and Grades
Assignments: 30-40%; Final exam: 60-70%.
Assignment 1: given 13/4/99, due 27/4/99.
Assignment 2: given 25/5/99, due 8/6/99.
Assignment 3: given 15/6/99, due 29/6/99.
What is Computational Geometry? Example problems and motivations.
Naive, incremental, and divide-and-conquer convex-hull algorithms.
Vector cross product and orientation test. Segment-intersection test.
Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.
DCEL (short talk)
The DCEL data structure. Application 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.
Linear programming, I
What is linear programming. Algorithms for half-planes intersection:
1. Divide and conquer; 2. Incremental.
Linear programming, II
Randomized linear programming. Unbounded linear programming.
Smallest enclosing disk of a 2D point set.
Orthogonal range searching
1D range searching. kd-trees. Range trees.
Point location, I
Slabs structure. Trapezoidal map. A randomized incremental algorithm for
computing a trapezoidal map. Time/Space analysis of the algorithm.
Point location, II; Voronoi diagram,
Handling degeneracies in point location.
A plane-sweep algorithm for computing the Voronoi diagram of a point set.
Duality; Arrangements of lines
A definition of duality in the plane. Halfspace discrepancy and its dual
problem. Computing an arrangement of lines. Levels in line arrangements.
Delaunay triangulation, I
Triangulation of a point set. Angle vector and the triangulation that
maximizes it. Delaunay triangulation and its relation to the angle vector.
Delaunay triangulation, II; Miscellaneous
A randomized incremental algorithm for computing the Delaunay triangulation.
The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems.
Envelopes of lines and planes. The crossing-number lemma.
Putting things together
Using various techniques for proving the combinatorial complexities of
several 2-point site Voronoi diagrams.