Bachelor
Informatica
Informatiekunde
Kunstmatige intelligentie
Master
Computing Science
Game&Media Technology
Artifical Intelligence
Business Informatics

Website: | website containing additional information | |

Contents: | In many areas of computer science -- robotics, computer graphics and virtual reality, and geographic information systems are some examples -- it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study the design and analysis of geometric algorithms and data structures. | |

Literature: | M. de Berg, M. Overmars, M. van Kreveld, and O. Schwarzkopf.
Computational Geometry: Algorithms and Applications (2nd edition).
Springer-Verlag, Heidelberg, 2000.
ISBN 3-540-65620-0. | |

Course form: | Two lectures of in total 5 hours per week. Throughout the lectures assignments will be done too. | |

Exam form: | Homework exams that will be distributed twice (40%), and in the exam week there will be a final exam (60%). Each item has to be scored with at least a 5 to pass the course. The final exam is "closed book". | |

Minimum effort to qualify for 2nd chance exam: | Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan. | |

Description: | We will study various algorithmic techniques and geometric concepts that are useful to solve geometric problems efficiently. Algorithmic techniques include plane sweep, randomized incremental construction, and multi-level data structures; geometric concepts include Voronoi diagrams and Delaunay triangulations, arrangements, and duality. We will apply these techniques to solve a variety of problems: convex-hull computation, line-segment intersection, polygon triangulation, low-dimensional linear programming, range searching, point location are some examples. Each problem we study is motivated by a practical problem from one of the application areas. |