-
This course covers advanced algorithms and data structures for geometric problems in two and three dimensions. Main topics include:
- Convex hulls in two and higher dimensions,
- Triangulations and planar subdivisions,
- Geometric search and intersection,
- Voronoi diagrams and Fortune's algorithm,
- Delaunay triangulations,
- Line arrangements, and
- Visibility.
For more detailed information, check out the course proposal form.
- Thursdays - 09:40 to 12:30 in G-102.
- At the end of the course, the students will:
- have learnt advanced data structures and algorithms for dealing with geometric problems,
- increase their knowledge about algorithm complexity and correctness analysis by studying advanced geometric algorithms,
- and lear to apply theory on practical real-life geometric problems such as robot motion planning and location a point on a map.
- No formal prerequisites. However, students are expected to know fundamental data structures (CENG 213) and design and analysis of algorithms (CENG 315).
- Textbook:
-
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkoph, "Computational Geometry: Algorithms and Applications, 3rd edition," Springer, 2008, ISBN: 978-3-642-09681-5.
- Reference Material:
- Computational Geometry Algorithms Library. CGAL-3.8. http://www.cgal.org , 2011.
- J. O'Rourke, "Computational Geometry in C, 2nd edition," 1998, ISBN: 978-0521649766
- Written and programming assignments: 30%
- Midterm exam: 35%
- Final exam : 35%