Computational Geometry (Fall 2008)

Messages

• 28/11: Project 3 - deadline January 12, 2009.
• 25/11: The exam will be January 19-20, 2009.
• 3/10: Project 2 - deadline November 19, 2008, 9.15.
• 18/9: Comments about content of project reports.
• 2/9: Project 1 - deadline October 8, 2008, 9.15.
• 28/7: Time and place updated. A tentative course plan is now available.
• 14/5 2008: The ISBN number of the course book has been updated - a 3rd revision of the book has just been released.
• 13/5 2007: Homepage for the course created.

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:

• construct algorithms for simple geometrical problems.
• implement computational geometry algorithms.

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

.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

• Project 3 - Theoretical problems (A)-(D). Deadline January 12, 2009.
• Project 2 - Point location. Deadline November 19, 2008, 9.15.
• Project 1 - Line segment intersection. Deadline October 8, 2008, 9.15.
• Information about programming tools for the projects.
• Comments about content of project reports.

Quarter

1. and 2. (Fall 2008).

Credits

10 ETCS points.

Prerequisites

• Algorithms and Data Structure 1
• Algorithms and Data Structure 2

Course language

Compulsory programme

3 projects.

Evaluation

Projects and oral examination, 7-scale.

The exam will be January 19-20, 2009.