Computational Geometry (Fall 2010)
Messages
- 17/11: Information on exam, January 6-7, 2011.
- 17/11: Project 3 - deadline, December 22.
- 19/10: Tentative dates for the oral exam: January 6-7, 2011.
- 4/10: Project 2 - deadline,
November 17. - 30/9: Deadline for project 1, extended to October 8.
- 1/9: Project 1 - deadline,
October 6. - 24/8: Info om DM i programmering
- 16/2 2010: Course page created.
Objectives
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.
Learning outcomes and competences
The participants must at the end of the course be able to:
- construct algorithms for simple geometrical problems.
- implement computational geometry algorithms.
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).
Lecturer
Time and Place
Wednesdays 9.15-12.00, Lecture room 112, Incuba Science Park, Åbogade 15
Lectures
3 hours per week.
Course plan
| Week | Date | Content | Literature |
|---|---|---|---|
| 34 | 25/8 | Introduction to Computational Geometry Convex hull in 2D |
[BKOS, Chapter 1] [C96, Section 1-2,4] |
| 35 | 1/9 | The doubly-connected edge list (DCEL)
Line segment intersection Overlays of Two Subdivisions Discussion of Project 1 |
[BKOS, Chapter 2] | 36 | 8/9 | Orthogonal Range Searching Lecturer: Elad Verbin |
[BKOS, Chapter 5] | 37 | 15/9 | Polygon Triangulation | [BKOS, Chapter 3] |
| 38 | 22/9 | Point Location | [ST86] [BKOS, Chapter 6.1-6.3+6.5] |
| 39 | 29/9 | Voronoi Diagrams (slides) | [BKOS, Chapter 7.1-7.2] |
| 40 | 6/10 | Delaunay triangulations (slides)
3D Convex Hull(slides) Discussion of Project 2 |
[BKOS, Chapter 9.1-9.3]
[BKOS, Chapter 11.1-11.2] |
| 8/10 | Deadline Project 1 | ||
| Fall break | 44 | 3/11 | Interval trees Priority search trees Segment trees |
[BKOS, Chapter 10] |
| 45 | 10/11 | Binary Space Partitions
Quad trees |
[BKOS, Chapter 12.1-12.3]
[BKOS, Chapter 14] |
46 | 17/11 | Robot Motion Planning
Visibility Graphs Discussion of Project 3 Deadline Project 2 |
[BKOS, Chapter 13]
[BKOS, Chapter 15] |
47 | 24/11 | Duality Simplex Range Searching |
[BKOS, Chapter 8.2] [BKOS, Chapter 16.1-16.3] |
48 | 1/12 | Robustness problems in geometric computations | [KMPSY04] Slides nonrobust_esa_04.pdf |
49 | 8/12 | Euclidian travelling salesman | [A03, Sections 1-2] | 50 | 15/12 | No lecture |
Literature
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. |
Additional readings will be handed out during the course, including:
- [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.
- [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.
- [A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.
Projects
- Project 3 - Theoretical problems (A)-(D). Deadline December 22, 2010.
- Project 2 - Point location. Deadline November 17, 2010, 23.59.
- Project 1 - Line segment intersection. Deadline October 8, 2010, 23.59.
- Information about programming tools for the projects (old).
- Comments about content of project reports.
Quarter
1st and 2nd (Fall 2010).
Credits
10 ETCS points.
Prerequisites
Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.
Course language
Danish or English.
Compulsory programme
3 projects.
Evaluation
Projects and oral examination (20 minutes, no preparation), 7-scale, internal examiner.
The exam will be January 6-7, 2011.
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.