Computational Geometry (Fall 2010)

Messages

• 17/11: Information on exam, January 6-7, 2011.
• 17/11: Project 3 - deadline, December 22.
• 19/10: Tentative dates for the oral exam: January 6-7, 2011.
• 4/10: Project 2 - deadline, November 17.
• 30/9: Deadline for project 1, extended to October 8.
• 1/9: Project 1 - deadline, October 6.
• 24/8: Info om DM i programmering
• 16/2 2010: Course page 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).

Time and Place

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

Lectures

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
[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]
Fall break
44 3/11 Interval trees
Priority search trees
Segment trees
[BKOS, Chapter 10]
45 10/11 Binary Space Partitions
[BKOS, Chapter 12.1-12.3]
[BKOS, Chapter 14]
46 17/11 Robot Motion Planning
Visibility Graphs
Discussion of Project 3
[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

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.

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.

Quarter

1st and 2nd (Fall 2010).

10 ETCS points.

Prerequisites

Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.

Course language

Danish or English.

3 projects.

Evaluation

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.