Computational Geometry (Fall 2006)

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

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

WeekDateTopicsLiterature
35 31/8 Introduction to Computational Geometry
Convex hull in 2D
[BKOS, Chapter 1]
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]
8/9 Overlays of Two Subdivisions
Discussion of Project 1
[BKOS, Chapter 2.3-2.5]
37 14/9 Polygon Triangulation [BKOS, Chapter 3]
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)]
22/9 Point Location [ST86]
39 28/9 Point Location [BKOS, Chapter 6.1-6.3]
29/9 Voronoi Diagrams [BKOS, Chapter 7]
40 5/10 Voronoi Diagrams
Note: Lecture in "Store auditorie"
[BKOS, Chapter 7]
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]
Discussion of Project 2

42-43 Fall break
44 31/10 Interval trees [BKOS, Chapter 10]
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]
9/11 Robot Motion Planning [BKOS, Chapter 13]
46 14/11 Quad trees [BKOS, Chapter 14]
16/11 Visibility Graphs [BKOS, Chapter 15]
47 21/11 Simplex Range Searching [BKOS, Chapter 16.1-16.2]
23/11 Duality, Cutting trees
[BKOS, Chapter 8.2+16.3]
48 28/11 Cache Oblivious Search Trees [BFJ02]
30/11 Cache Oblivious Range Searching and Counting [ABFL05]
49 5/12 Logarithmic method [O83, Chapter 7]
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]
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.
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. [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.
4. [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.
5. [O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983.
6. [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.
7. [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.
8. [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.
9. [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.
10. [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.

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

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

10 ETCS points.

Prerequisites

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

Course language

Danish or English.

3 projects.

Evaluation

January 15-16, 2007

Projects and oral examination, 13-scale.