04/09: Project 1 announced!
10/10 : Project 2 announced (deadline 5/12)!
Date for Oral Exam: 17th and 18th Jan. 2013
14/11: Project 3 (A) announced (deadline will be announced together with part B)!
14/11: Project 3 (B), deadline 21st of December!
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.
The participants must at the end of the course be able to:
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).
Peyman Afshani and Gerth Stølting Brodal
Wednesdays 9.15-12.00. Nygaard 184.
3 hours per week.
| Week | Date | Content | Literature |
|---|---|---|---|
| 35 | 29/8 |
Introduction to Computational Geometry Convex hull in 2D | [BKOS, Chapter 1] |
| 36 | 5/9 |
Linear Programming Discussion of Project 1 |
[BKOS, Chapter 4] [KS86] Section 3 of [CSY97] |
| 37 | 12/9 | Orthogonal Range SearchingLecturer: Kasper Green Larsen | [BKOS, Chapter 5] |
| 38 | 19/9 | The doubly-connected edge list (DCEL) Line segment intersection Overlays of Two Subdivisions | [BKOS, Chapter 2] |
| 39 | 26/9 | Polygon Triangulation |
[BKOS, Chapter 3]
|
| 40 | 3/10 | Point Location |
[ST86][BKOS, Chapter 6] |
| 41 | 10/10 |
Arrangements and Duality |
[BKOS, Chapter 8 ] |
| 12/10 | Deadline Project 1 | ||
| Fall break | |||
| 45 | 7/11 |
Voronoi Diagrams | [BKOS, Chapter 7] |
| 46 | 14/11 |
Delaunay triangulations 3D Convex Hull
| [BKOS, Chapter 9] |
| 47 | 21/11 | Interval treesPriority search treesSegment trees | [BKOS, Chapter 10] |
| 48 | 28/11 |
Binary Space Partitions Quad trees | [BKOS, Chapter 12] [BKOS, Chapter 14] |
| 49 | 5/12 | Robot Motion Planning Visibility Graphs Discussion of Project 3 Deadline Project 2 |
[BKOS, Chapter 13] [BKOS, Chapter 15] |
| 50 | 12/12 | Simplex Range Searching | [BKOS, Chapter 16] |
| 51 | 19/12 | No lecture | |
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. The book will be available in Stakbogladen from mid August. |
Additional readings will be handed out during the course. Including:
[KS86] David Kirkpatrick and Raimund Seidel, "The Ultimate Planar Convex Hull Algorithm ?", SIAM Journal on Computing, 1986
[CSY97] Timothy Chan, Jack Snoeyick, and Chee-Keng Yap, Primal dividing and dual pruning: output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams, Discrete & Computational Geometry, 18:433-454, 1997
See up!
1st and 2nd (Fall 2012).
10 ETCS points.
Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.
English.
3 projects.
Projects and oral examination (20 minutes, no preparation), 7-scale, internal examiner.
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.