Computational Geometry (Fall 2010)
- 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,
- 30/9: Deadline for project 1, extended to October 8.
- 1/9: Project 1 - deadline,
- 24/8: Info om DM i programmering
- 16/2 2010: Course page created.
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.
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
Wednesdays 9.15-12.00, Lecture room 112, Incuba Science Park, Åbogade 15
3 hours per week.
|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]|
[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
|[BKOS, Chapter 10]|
|45||10/11||Binary Space Partitions
|[BKOS, Chapter 12.1-12.3]
[BKOS, Chapter 14]
|46||17/11||Robot Motion Planning
Discussion of Project 3
Deadline Project 2
|[BKOS, Chapter 13]
[BKOS, Chapter 15]
Simplex Range Searching
|[BKOS, Chapter 8.2]
[BKOS, Chapter 16.1-16.3]
|48||1/12||Robustness problems in geometric computations||[KMPSY04]
|49||8/12||Euclidian travelling salesman||[A03, Sections 1-2]||50||15/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.
Springer-Verlag, 386 pages, 2008.
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.
- 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.
1st and 2nd (Fall 2010).
10 ETCS points.
Algoritmer og Datastrukturer 1 + Algoritmer og Datastrukturer 2.
Danish or English.
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.