Computational Geometry (Fall 2008)

Messages

Objectives

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:

Contents

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

Lecturer

Gerth Stølting Brodal

Time and Place

Wednesday 9.15-12.00, Shannon 159

Course plan

Week Date Content Literature
35 27/8 Introduction to Computational Geometry
Convex hull in 2D
[BKOS, Chapter 1]
[C96, Section 1-2,4]
Notes ch.jnt | ch.pdf
36 3/9 The doubly-connected 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.1-7.2]
41 8/10 Delaunay triangulations
3D Convex Hull
Discussion of Project 2
Deadline Project 1
[BKOS, Chapter 9.1-9.3]
[BKOS, Chapter 11.1-11.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.1-12.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.1-16.3]
49 3/12 Robustness problems in geometric computations [KMPSY04]
Slides nonrobust_esa_04.pdf
50 10/12 Euclidian travelling salesman [A03, Sections 1-2]
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)

Literature

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. [O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983.
  4. [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.
  5. [A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.

Projects

Quarter

1. and 2. (Fall 2008).

Credits

10 ETCS points.

Prerequisites

Course language

Danish or English.

Compulsory programme

3 projects.

Evaluation

Projects and oral examination, 7-scale.

The exam will be January 19-20, 2009.


This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>