Spatial data are processed in various subfields of computer science, e.g. in computer graphics, visualization, geographic information systems, robotics etc. The area of computational geometry deals with the design and analysis of geometric algorithms and data structures. In this module we present common techniques and concepts in computational geometry in the context of selected and applied geometric questions. The following topics are covered in the course:
- convex hulls
- line segment intersections
- polygon triangulation
- range queries
- point location
- Voronoi diagrams and Delaunay triangulations
- duality of points and lines
- quadtrees
- well-separated pair decomposition
- visibility graphs
ECTS-Breakdown
25 h attending lectures and exercises
30 h lecture follow-up and preparation of home exercises
19.5 h preparation for oral exam
0.5 h oral exam
------
75 h overall
Please send mails concerning general and organisational issues to alggeom@ac.tuwien.ac.at.
A solid knowledge of the design and analysis of algorithms is recommended.
Lecture slides will be made available to the students.