Computational Geometry

Computational Geometry (Fall 2006)

Messages

2/12 2007: Information about the exam.
28/11: Project 3 - new deadline Thursday January 11, 2007.
14/11: The exam will be January 15-16, 2007, and the final project is due January 11, 2007.
12/11: Project 2 - new deadline Thursday November 23.
12/10: Project 2 - ~~deadline Thursday November 16~~.
7/9: Project 1 - deadline Friday October 13.
5/9: Rember to register for the exam using the university's self administration system, in the period September 1-15.
7/8: First lecture is Thursday August 31, 9.15-11.00, in "Lille Auditorie".
19/4 2006: Webpage for Computational Geometry, Fall 2004.
29/9 2005: Homepage for the course created.

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

Lecturers

Time and Place

1st quarter: Thursday 9.15-11.00 and Friday 11.15-12.00, "Lille Auditorie"

2nd quarter: Tuesday 13.15-14.00 and Thursday 9.15-11.00, "Lille Auditorie"

Course plan

Week	Date	Topics	Literature
35	31/8	Introduction to Computational Geometry Convex hull in 2D	[BKOS, Chapter 1]
35	1/9	Convex hull in 2D	[BKOS, Chapter 1] [C96, Section 1-2,4]
36	7/9	Line segment intersection The doubly-connected edge list (DCEL)	[BKOS, Chapter 2.1-2.2]
36	8/9	Overlays of Two Subdivisions Discussion of Project 1	[BKOS, Chapter 2.3-2.5]
37	14/9	Polygon Triangulation	[BKOS, Chapter 3]
37	15/9	Orthogonal Range Searching	[BKOS, Chapter 5.1-5.2 (pages 93-99)]
38	21/9	Orthogonal Range Searching	[BKOS, Chapter 5.2-5.6 (pages 100-113)]
38	22/9	Point Location	[ST86]
39	28/9	Point Location	[BKOS, Chapter 6.1-6.3]
39	29/9	Voronoi Diagrams	[BKOS, Chapter 7]
40	5/10	Voronoi Diagrams Note: Lecture in "Store auditorie"	[BKOS, Chapter 7]
40	6/10	Delaunay triangulations Note: Lecture in "Store auditorie"	[BKOS, Chapter 9.1-9.3]
41	12/10	3D Convex Hull	[BKOS, Chapter 11.1-11.2]
41	13/10	Deadline project 1 Discussion of Project 2
42-43	Fall break
44	31/10	Interval trees	[BKOS, Chapter 10]
44	2/11	Priority search trees, segment trees	[BKOS, Chapter 10]
45	7/11	Binary Space Partitions ([T01] gives an Omega(n*log n/loglog n) lower bound for line segments in the plane)	[BKOS, Chapter 12.1-12.3]
45	9/11	Robot Motion Planning	[BKOS, Chapter 13]
46	14/11	Quad trees	[BKOS, Chapter 14]
46	16/11	Visibility Graphs	[BKOS, Chapter 15]
47	21/11	Simplex Range Searching	[BKOS, Chapter 16.1-16.2]
47	23/11	Duality, Cutting trees Deadline project 2	[BKOS, Chapter 8.2+16.3]
48	28/11	Cache Oblivious Search Trees	[BFJ02]
48	30/11	Cache Oblivious Range Searching and Counting	[ABFL05]
49	5/12	Logarithmic method	[O83, Chapter 7]
49	7/12	Implicit Computation Geometry Algorithms (Henrik Blunck) Slides for viewing and printing (pdf).	[BV06],[BHSV06],[BCC04],[BIKMMT04]
50	12/12	Implicit Computation Geometry Algorithms (Henrik Blunck)	[BV06],[BHSV06],[BCC04],[BIKMMT04]
50	14/12	Robustness problems in geometric computations Exam discussion	[KMPSY04]

Literature

The below book will be the primary source for the course. Additional readings will be handed out during the course.

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.

[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.
[BFJ02] Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, Cache-Oblivious Search Trees via Binary Trees of Small Height. Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 39-48, 2002.
[ABFL05] Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, Morten Laustsen. Cache-Oblivious Planar Orthogonal Range Searching and Counting Proc. 21st Annual ACM Symposium on Computational Geometry, pages 160-169, 2005.
[O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983.
[BV06] Henrik Blunck and Jan Vahrenhold. In-Place Algorithms for Computing (Layers of) Maxima. In: Lars Arge and Rusin Freivalds, editors: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), volume 4059 of Lecture Notes in Computer Science, pages 363-374. Springer, Berlin, 2006. © Springer-Verlag.
[BV06b] Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope Selection. In: Tiziana Calamoneri, Irene Finocchi, and Giuseppe F. Italiano, editors: Proceedings of the 6th Conference on Algorithms and Complexity (CIAC 2006), volume 3998 of Lecture Notes in Computer Science, pages 30-41. Springer, Berlin, 2006. © Springer-Verlag.
[BCC04] H. Brönnimann, T. M. Chan and E. Y. Chen, Towards in-place Geometric Algorithms and Data Structures. In Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG '04)', ACM Press, New York, NY, USA, pp. 239-246, 2004.
[BIKMMT04] H. Brönnimann, J. Iacono,, J. Katajainen, P. Morin, J. Morrison and G. Toussaint, Space-efficient Planar Convex Hull Algorithms. Theoretical Computer Science 321(1), 25-40, 2004.
[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.

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 - Finding the shortest path for a point robot. Deadline January 11, 2007.
Project 2 - Point location. Deadline November 23, 2006, 9.15.
Project 1 - Line segment intersection. Deadline October 13, 2006, 11.15.
Information about programming tools for the projects.

Quarter

1. and 2. (Fall 2006).

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

January 15-16, 2007

Projects and oral examination, 13-scale.

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