
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).
1st quarter: Thursday 9.1511.00 and Friday 11.1512.00, "Lille Auditorie"
2nd quarter: Tuesday 13.1514.00 and Thursday 9.1511.00, "Lille Auditorie"
Week  Date  Topics  Literature 

35  31/8  Introduction to Computational Geometry Convex hull in 2D  [BKOS, Chapter 1] 
1/9  Convex hull in 2D  [BKOS, Chapter 1] [C96, Section 12,4] 

36  7/9  Line segment intersection The doublyconnected edge list (DCEL) 
[BKOS, Chapter 2.12.2] 
8/9  Overlays of Two Subdivisions Discussion of Project 1 
[BKOS, Chapter 2.32.5]  
37  14/9  Polygon Triangulation  [BKOS, Chapter 3] 
15/9  Orthogonal Range Searching  [BKOS, Chapter 5.15.2 (pages 9399)]  
38  21/9  Orthogonal Range Searching  [BKOS, Chapter 5.25.6 (pages 100113)] 
22/9  Point Location  [ST86]  
39  28/9  Point Location  [BKOS, Chapter 6.16.3] 
29/9  Voronoi Diagrams  [BKOS, Chapter 7]  
40  5/10  Voronoi Diagrams Note: Lecture in "Store auditorie" 
[BKOS, Chapter 7] 
6/10  Delaunay triangulations Note: Lecture in "Store auditorie" 
[BKOS, Chapter 9.19.3]  
41  12/10  3D Convex Hull  [BKOS, Chapter 11.111.2] 
13/10  Deadline project 1 Discussion of Project 2 

4243  Fall break  
44  31/10  Interval trees  [BKOS, Chapter 10] 
2/11  Priority search trees, segment trees  [BKOS, Chapter 10]  
45  7/11  Binary Space Partitions ([T01] gives an Omega(n*log n/loglog n) lower bound for line segments in the plane) 
[BKOS, Chapter 12.112.3] 
9/11  Robot Motion Planning  [BKOS, Chapter 13]  
46  14/11  Quad trees  [BKOS, Chapter 14] 
16/11  Visibility Graphs  [BKOS, Chapter 15]  
47  21/11  Simplex Range Searching  [BKOS, Chapter 16.116.2] 
23/11  Duality, Cutting trees Deadline project 2 
[BKOS, Chapter 8.2+16.3]  
48  28/11  Cache Oblivious Search Trees  [BFJ02] 
30/11  Cache Oblivious Range Searching and Counting  [ABFL05]  
49  5/12  Logarithmic method  [O83, Chapter 7] 
7/12  Implicit Computation Geometry Algorithms
(Henrik Blunck) Slides for viewing and printing (pdf). 
[BV06],[BHSV06],[BCC04],[BIKMMT04]  
50  12/12  Implicit Computation Geometry Algorithms (Henrik Blunck)  [BV06],[BHSV06],[BCC04],[BIKMMT04] 
14/12  Robustness problems in geometric computations Exam discussion 
[KMPSY04] 
The below book will be the primary source for the course. Additional readings will be handed out during the course.
Computational Geometry: Algorithms and Applications.
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf.
Second Edition.
SpringerVerlag, 367 pages, 2000.
ISBN: 3540656200. 
1. and 2. (Fall 2006).
10 ETCS points.
3 projects.
January 1516, 2007
Projects and oral examination, 13scale.