Computational Geometry (Fall 2004)

Messages

Aims

The goal of the course is to introduce the student to fundamental problems within computation geometry, and to make the student familiar with general techniques for solving problems within computational geometry. Furthermore, through project work the student will gain experience with the implementation issues involved in converting computation geometry algorithms into running programs.

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

Example slide: Voronoi diagram and convex hull (pdf).

Lecturers

Lectures

Monday 11.15-13.00 and Wednesday 9.15-10.00, Codd-121, Finlandsgade 24-26. First lecture Monday August 23.

Course plan

WeekDateTopicsLiterature
35 23/8Introduction to Computational Geometry
Convex hull in 2D
[BKOS, Chapter 1]
[C96, Section 1-2,4]
25/8Line segment intersection[BKOS, Chapter 2.1]
36 30/8The Doubly-Connected Edge List
Overlays of Two Subdivisions
[BKOS, Chapter 2.2-2.5]
1/9Discussion of Project 1 
37 6/9Cancelled 
8/9Triangulations[BKOS, Chapter 3]
38 13/9Range searching[BKOS, Chapter 5]
15/9Cancelled 
39 20/9Planar point location[BKOS, Chapter 6.1],[ST86]
22/9Planar point location[BKOS, Chapter 6.2]
40 27/9Voronoi diagrams[BKOS, Chapter 7]
29/9Delaunay triangulations[BKOS, Chapter 9.1-9.3]
41 4/10Delaunay triangulations[BKOS, Chapter 9.1-9.3]
6/10Deadline for Project 1
Discussion of Project 2
 
42-43 Fall break
44 25/10Interval trees, priority search trees, segment trees[BKOS, Chapter 10]
27/103D Convex Hull[BKOS, Chapter 11.1-11.2]
45 1/11Binary Space Partitions ([T01] gives an Omega(n*log n/loglog n) lower bound for line segments in the plane)[BKOS, Chapter 12]
3/11Robot Motion Planning[BKOS, Chapter 13]
46 8/11Quad trees[BKOS, Chapter 14]
10/11Visibility Graphs
Deadline for Project 2
[BKOS, Chapter 15]
47 15/11Simplex Range Searching[BKOS, Chapter 16.1-16.2]
17/11Discussion of Project 3
Logarithmic method
[O83, Chapter 7]
48 22/11Duality, Cutting trees[BKOS, Chapter 8.2+16.3]
25/11Algebraic lower bounds[S98, Chapter 11]
49 29/11Euclidian travelling salesman[A03, Sections 1-2]
1/12Kinetic algorithms and data structures[BGH99, Section 1+4]
50 6/12R-trees (by Herman Haverkort)[H04]
8/12Discussion of the exam 
51 17/12Deadline for Project 3 

Literature

Computational Geometry: Algorithms and Applications. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Second Edition. Springer-Verlag, 367 pages, 2000. ISBN: 3-540-65620-0.

The book will be available in Gad Stakbogladen, Ny Munkegade, in August.
  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. [S98] Sven Skyum, Lecture note on Introduction to lower bounds, February 1998.
  5. [A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.
  6. [BGH99] Julien Basch, Leonidas J. Guibas and John Hershberger, Data Structures for Mobile Data, Journal of Algorithms, 31(1), 1999, pages 1-28
  7. [H04] Herman J. Haverkort, Introduction to bounding volume hierarchies, Manuscript, May 2004.

Additional literature

  1. [T01] Csaba D. Tóth, A note on binary plane partitions, Proceedings of the seventeenth annual symposium on Computational geometry, 151-156, 2001.

Projects

Quarter

1. and 2. (Fall 2004).

Credits

10 ETCS points.

Prerequisites

Course language

Danish or English.

Compulsory programme

3 projects.

Evaluation

Projects and oral examination, 13-scale.


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