Computational Geometry (Fall 2012)


04/09: Project 1 announced!

10/10 : Project 2 announced (deadline 5/12)!

Date for Oral Exam: 17th and 18th Jan. 2013

14/11: Project 3 (A) announced (deadline will be announced together with part B)!

14/11: Project 3 (B), deadline 21st of December!


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).


Peyman Afshani and Gerth Stølting Brodal

Time and Place

Wednesdays 9.15-12.00. Nygaard 184.


3 hours per week.

Course plan


Introduction to Computational Geometry Convex hull in 2D

[BKOS, Chapter 1]

Linear Programming

Discussion of Project 1

[BKOS, Chapter 4]


Section 3 of [CSY97]

3712/9Orthogonal Range SearchingLecturer: Kasper Green Larsen[BKOS, Chapter 5]
3819/9The doubly-connected edge list (DCEL) Line segment intersection Overlays of Two Subdivisions [BKOS, Chapter 2]
3926/9Polygon Triangulation

[BKOS, Chapter 3]

403/10Point Location

[ST86][BKOS, Chapter 6]


Arrangements and Duality

[BKOS, Chapter 8 ]

12/10Deadline Project 1
Fall break

Voronoi Diagrams

[BKOS, Chapter 7]

Delaunay triangulations 3D Convex Hull

[BKOS, Chapter 9]
4721/11Interval treesPriority search treesSegment trees[BKOS, Chapter 10]

Binary Space Partitions Quad trees

[BKOS, Chapter 12] [BKOS, Chapter 14]
495/12Robot Motion Planning Visibility Graphs Discussion of Project 3 Deadline Project 2

[BKOS, Chapter 13]

[BKOS, Chapter 15]

5012/12Simplex Range Searching[BKOS, Chapter 16]
5119/12No 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. The book will be available in Stakbogladen from mid August.

Additional readings will be handed out during the course. Including:

[KS86] David Kirkpatrick and Raimund Seidel, "The Ultimate Planar Convex Hull Algorithm ?", SIAM Journal on Computing, 1986

[CSY97] Timothy Chan, Jack Snoeyick, and Chee-Keng Yap, Primal dividing and dual pruning: output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams, Discrete & Computational Geometry, 18:433-454, 1997


See up!


1st and 2nd (Fall 2012).


10 ETCS points.


Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.

Course language


Compulsory programme

3 projects.


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

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.