Department of Computer Science Aarhus University Department of Comptuer Science Faculty of Science

Computational Geometry (Fall 2010)



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.

Learning outcomes and competences

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 (sweep-line, randomized incremental construction, fractional cascading), and data structures (double-linked edge-lists, interval trees, segment trees, and priority search trees, Kd-trees, range trees).


Gerth Stølting Brodal

Time and Place

Wednesdays 9.15-12.00, Lecture room 112, Incuba Science Park, Åbogade 15


3 hours per week.

Course plan

Week Date Content Literature
34 25/8 Introduction to Computational Geometry
Convex hull in 2D
[BKOS, Chapter 1]
[C96, Section 1-2,4]
35 1/9 The doubly-connected edge list (DCEL)
Line segment intersection
Overlays of Two Subdivisions
Discussion of Project 1
[BKOS, Chapter 2]
36 8/9 Orthogonal Range Searching
Lecturer: Elad Verbin
[BKOS, Chapter 5]
37 15/9 Polygon Triangulation [BKOS, Chapter 3]
38 22/9 Point Location [ST86]
[BKOS, Chapter 6.1-6.3+6.5]
39 29/9 Voronoi Diagrams (slides) [BKOS, Chapter 7.1-7.2]
40 6/10 Delaunay triangulations (slides)
3D Convex Hull(slides)
Discussion of Project 2
[BKOS, Chapter 9.1-9.3]
[BKOS, Chapter 11.1-11.2]
8/10 Deadline Project 1  
Fall break
44 3/11 Interval trees
Priority search trees
Segment trees
[BKOS, Chapter 10]
45 10/11 Binary Space Partitions
Quad trees
[BKOS, Chapter 12.1-12.3]
[BKOS, Chapter 14]
46 17/11 Robot Motion Planning
Visibility Graphs
Discussion of Project 3
Deadline Project 2
[BKOS, Chapter 13]
[BKOS, Chapter 15]
47 24/11 Duality
Simplex Range Searching
[BKOS, Chapter 8.2]
[BKOS, Chapter 16.1-16.3]
48 1/12 Robustness problems in geometric computations [KMPSY04]
Slides nonrobust_esa_04.pdf
49 8/12 Euclidian travelling salesman [A03, Sections 1-2]
50 15/12 No lecture


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. Springer-Verlag, 386 pages, 2008. ISBN: 978-3-540-77973-5.

Additional readings will be handed out during the course, including:

  1. [C96] Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996.
  2. [ST86] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 1986, pages 669-679.
  3. [KMPSY04] Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Classroom Examples of Robustness Problems in Geometric Computations. In: Proc. of the 12th Annu. European Sympos. Algorithms (ESA'04), Bergen, Norway. LNCS 3221, Springer, pp. 702-713, September, 2004.
  4. [A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.



1st and 2nd (Fall 2010).


10 ETCS points.


Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.

Course language

Danish or English.

Compulsory programme

3 projects.


Projects and oral examination (20 minutes, no preparation), 7-scale, internal examiner.

The exam will be January 6-7, 2011.

The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the projects and the material covered in class (see "course plan" above). The final grade will be based on the project reports and the oral examination.