Computational Geometry

Computational Geometry (Fall 2004)

Messages

13/12: Information about the exam.
25/11: Deadline for Project 3 extended to December 17, 2004, 14.00.
17/11: Oral examination: January 10-11, 2005 (tentative).
15/11: Project 3 - deadline ~~December 15, 2004, 14.00~~.
9/11: Deadline for project 2 extended to November 12, 2004, 14.00.
22/10: Eksamenstilmelding: mandag den 25. oktober til og med mandag den 1. november 2004.
5/10: Project 2 - deadline ~~November 10, 2004, 9.15~~.
21/9: Deadline for project 1 extended to October 6, 2004, 9.15.
1/9: Project 1 - deadline ~~September 29, 2004, 9.15~~.
31/8: Information about programming tools for the projects.
10/8: First lecture: Monday August 23.
25/4: Created course homepage.

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.

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

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

[C96] Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996.
[ST86] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 1986, pages 669-679.
[O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983.
[S98] Sven Skyum, Lecture note on Introduction to lower bounds, February 1998.
[A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.
[BGH99] Julien Basch, Leonidas J. Guibas and John Hershberger, Data Structures for Mobile Data, Journal of Algorithms, 31(1), 1999, pages 1-28
[H04] Herman J. Haverkort, Introduction to bounding volume hierarchies, Manuscript, May 2004.

Additional literature

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

Projects

Project 3 - deadline December 17, 2004, 14.00.
Project 2 - deadline November 12, 2004, 9.15.
Project 1 - deadline October 6, 2004, 9.15.
Information about programming tools for the projects.

Quarter

1. and 2. (Fall 2004).

Credits

10 ETCS points.

Prerequisites

Algorithms and Data Structure 1 (dADS 1)
Algorithms and Data Structure 2 (dADS 2)

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>