
The participants will after the course have detailed knowledge of the fundamental problems within computation geometry and general techniques for solving problems within computational geometry and practical experience with implementation issues involved in converting computation geometry algorithms into running programs.
The participants must at the end of the course be able to:
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).
Wednesday 9.1512.00, Shannon 159
Week  Date  Content  Literature 

35  27/8  Introduction to Computational Geometry Convex hull in 2D 
[BKOS, Chapter 1] [C96, Section 12,4] Notes ch.jnt  ch.pdf 
36  3/9  The doublyconnected edge list (DCEL)
Line segment intersection Overlays of Two Subdivisions Discussion of Project 1 
[BKOS, Chapter 2] 
37  10/9  Polygon Triangulation  [BKOS, Chapter 3] 
38  17/9  Orthogonal Range Searching  [BKOS, Chapter 5] Notes range.jnt  range.pdf 
39  24/9  Point Location  [ST86] [BKOS, Chapter 6] 
40  1/10  Voronoi Diagrams  [BKOS, Chapter 7.17.2] 
41  8/10  Delaunay triangulations
3D Convex Hull Discussion of Project 2 Deadline Project 1 
[BKOS, Chapter 9.19.3]
[BKOS, Chapter 11.111.2] 
Fall break  
45  5/11  Interval trees Priority search trees Segment trees 
[BKOS, Chapter 10] Notes trees.jnt  trees.pdf 
46  12/11  Binary Space Partitions
Quad trees 
[BKOS, Chapter 12.112.3]
[BKOS, Chapter 14] 
47  19/11  Robot Motion Planning
Visibility Graphs Deadline Project 2 
[BKOS, Chapter 13]
[BKOS, Chapter 15] 
48  26/11  Duality Simplex Range Searching 
[BKOS, Chapter 8.2] [BKOS, Chapter 16.116.3] 
49  3/12  Robustness problems in geometric computations  [KMPSY04] Slides nonrobust_esa_04.pdf 
50  10/12  Euclidian travelling salesman  [A03, Sections 12] 
51  17/12  No lecture We meet for breakfast rolls at 10.15 in Shannon 159 
.jnt files are Windows Journal files (download viewer)
.pdf files Adobe PDF files (download reader)
The below book will be the primary source for the course. The book will be available at Gad Stakbogladen, Ny Munkegade, in August.
Computational Geometry: Algorithms and Applications.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.
Third Edition.
SpringerVerlag, 386 pages, 2008.
ISBN: 9783540779735. 
Additional readings will be handed out during the course, including:
1. and 2. (Fall 2008).
10 ETCS points.
3 projects.
Projects and oral examination, 7scale.
The exam will be January 1920, 2009.