Computational Geometry
Spring 99
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.
[CANCELED]
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.
Bibliography
Computational Geometry: Algorithms and Applications,
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Springer, 1997.
Computational Geometry in C,
J. O'Rourke,
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.
Course summary
-
23.3.99
Introduction
-
What is Computational Geometry? Example problems and motivations.
Naive, incremental, and divide-and-conquer convex-hull algorithms.
-
29.3.99
Plane sweep
-
Vector cross product and orientation test. Segment-intersection test.
Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.
-
13.4.99
DCEL (short talk)
-
The DCEL data structure. Application to a map-overlay algorithm.
Its use for polygon union, intersection, and difference.
-
27.4.99
Polygon triangulation
-
The art-gallery theorem. Partitioning a simple polygon into monotone pieces.
Triangulating a monotone polygon.
-
4.5.99
Linear programming, I
-
What is linear programming. Algorithms for half-planes intersection:
1. Divide and conquer; 2. Incremental.
-
11.5.99
Linear programming, II
-
Randomized linear programming. Unbounded linear programming.
Smallest enclosing disk of a 2D point set.
-
18.5.99
Orthogonal range searching
-
1D range searching. kd-trees. Range trees.
-
25.5.99
Point location, I
-
Slabs structure. Trapezoidal map. A randomized incremental algorithm for
computing a trapezoidal map. Time/Space analysis of the algorithm.
-
1.6.99
Point location, II; Voronoi diagram,
-
Handling degeneracies in point location.
A plane-sweep algorithm for computing the Voronoi diagram of a point set.
-
8.6.99
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.
-
15.6.99
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.
-
22.6.99
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.
-
27.6.99
Putting things together
-
Using various techniques for proving the combinatorial complexities of
several 2-point site Voronoi diagrams.