Computational Geometry (Fall 2008) Messages - deadline January 12, 2009 25/11: The exam will be January 19-20, 2009. Project 2 - deadline November 19, 2008, 9.15 18/9: Comments about content of project reports Project 1 - deadline October 8, 2008, 9.15 28/7: Time and place updated. A tentative course plan is now available. 14/5 2008: The ISBN number of the course book has been updated - a 3rd revision of the book has just been released. 13/5 2007: Homepage for the course 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). | |
|