
The goal of the course is to introduce the student to fundamental problems within computation geometry, and to make the student familiar with general techniques for solving problems within computational geometry. Furthermore, through project work the student will gain experience with the implementation issues involved in converting computation geometry algorithms into running programs.
This course provides an introduction to the key concepts, problems, techniques and data structures within computational geometry, including: Concepts (points, lines, planes, spheres, duality, subdivisions, degeneracies), problems (line intersections, convex hull, Voronoi diagram, triangulations, Delaunay triangulation, overlay of subdivisions, range searching), techniques (sweepline, randomized incremental construction, fractional cascading), and data structures (doublelinked edgelists, interval trees, segment trees, and priority search trees, Kdtrees, range trees).
Example slide: Voronoi diagram and convex hull (pdf).
Monday 11.1513.00 and Wednesday 9.1510.00, Codd121, Finlandsgade 2426. First lecture Monday August 23.
Week  Date  Topics  Literature 

35  23/8  Introduction to Computational Geometry Convex hull in 2D 
[BKOS, Chapter 1] [C96, Section 12,4] 
25/8  Line segment intersection  [BKOS, Chapter 2.1]  
36  30/8  The DoublyConnected Edge List Overlays of Two Subdivisions  [BKOS, Chapter 2.22.5] 
1/9  Discussion of Project 1  
37  6/9  Cancelled  
8/9  Triangulations  [BKOS, Chapter 3]  
38  13/9  Range searching  [BKOS, Chapter 5] 
15/9  Cancelled  
39  20/9  Planar point location  [BKOS, Chapter 6.1],[ST86] 
22/9  Planar point location  [BKOS, Chapter 6.2]  
40  27/9  Voronoi diagrams  [BKOS, Chapter 7] 
29/9  Delaunay triangulations  [BKOS, Chapter 9.19.3]  
41  4/10  Delaunay triangulations  [BKOS, Chapter 9.19.3] 
6/10  Deadline for Project 1 Discussion of Project 2  
4243  Fall break  
44  25/10  Interval trees, priority search trees, segment trees  [BKOS, Chapter 10] 
27/10  3D Convex Hull  [BKOS, Chapter 11.111.2]  
45  1/11  Binary Space Partitions ([T01] gives an Omega(n*log n/loglog n) lower bound for line segments in the plane)  [BKOS, Chapter 12] 
3/11  Robot Motion Planning  [BKOS, Chapter 13]  
46  8/11  Quad trees  [BKOS, Chapter 14] 
10/11  Visibility Graphs Deadline for Project 2  [BKOS, Chapter 15]  
47  15/11  Simplex Range Searching  [BKOS, Chapter 16.116.2] 
17/11  Discussion of Project 3 Logarithmic method  [O83, Chapter 7]  
48  22/11  Duality, Cutting trees  [BKOS, Chapter 8.2+16.3] 
25/11  Algebraic lower bounds  [S98, Chapter 11]  
49  29/11  Euclidian travelling salesman  [A03, Sections 12] 
1/12  Kinetic algorithms and data structures  [BGH99, Section 1+4]  
50  6/12  Rtrees (by Herman Haverkort)  [H04] 
8/12  Discussion of the exam  
51  17/12  Deadline for Project 3 
Computational Geometry: Algorithms and Applications.
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
Second Edition.
SpringerVerlag, 367 pages, 2000.
ISBN: 3540656200. The book will be available in Gad Stakbogladen, Ny Munkegade, in August. 
1. and 2. (Fall 2004).
10 ETCS points.
3 projects.
Projects and oral examination, 13scale.