Department of Information and Computing Sciences

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

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Geometric algorithms

Website:website containing additional information
Course code:INFOGA
Credits:7.5 ECTS
Period:periode 4 (week 17 t/m 26, dwz 24-4-2017 t/m 30-6-2017; herkansing week 28)
Participants:up till now 54 subscriptions
Schedule:Official schedule representation can be found in Osiris
college   di 13.15-15.0017-23 BBG-061 Marc van Kreveld
Wouter van Toll
24 ANDRO-C138
25 BBG-061
di 15.15-17.0020 BBG-005
23 BBG-005
do 9.00-10.4518-20 BBG-023
22-25 BBG-023

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, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications (3rd edition). Springer-Verlag, Heidelberg, 2008. ISBN 978-3-540-77973-5.
Course form:Two lectures of in total 4 hours per week.
Exam form:Homework exams that will be distributed twice (25% and 25%), and in the exam week there will be a final exam (50%). Each item has to be scored with at least a 5 to pass the course, and the weighted average, rounded, must be a 6. The final exam is "closed book". If you do not make or fail (<=4) both homework exams, you fail the course. If you fail one homework exam, you get a new, third homework exam based on later chapters of the book to replace the failed homework. To qualify for the second opportunity of the final exam, you must have a grade of 5 or higher for two homework exams.
Minimum effort to qualify for 2nd chance exam:Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.
Description:Computer graphics, robot motion planning, computer games, simulations, geographic information systems, and CAD/CAM systems all make use of geometric algorithms to perform various tasks. The course on geometric algorithms takes a fundamental viewpoint and discusses the design and analysis of geometric algorithms. We will study various algorithmic techniques and geometric concepts that are useful to solve geometric problems efficiently. These 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, and point location are some examples. Each problem we study is motivated by a practical problem from one of the application areas.