Website:  website containing additional information 
Course code:  INFOGA 
Credits:  7.5 ECTS 
Period:  periode 3 (week 6 t/m 16, dwz 622012 t/m 2042012; herkansing week 22)
 
Timeslot:  B 
Participants:  up till now 38 subscriptions 
Schedule:  Note: from now on the schedule is to be found in Osiris 
Teachers:  Dit is een oud rooster!

Tentamen: 
week: 22  di 2752014  9.0012.00 uur  zaal: BBL169  aanvullende toets 

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, O. Cheong, M. van Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications (3rd edition).
SpringerVerlag, Heidelberg, 2008.
ISBN 9783540779735. The second edition of this book can also be used. 
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. The final exam is "closed book". See the notice on the exam time.

Minimum effort to qualify for 2nd chance exam:  You need to have a score of 4 to qualify for the second chance exam.. 
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 multilevel data structures; geometric concepts include Voronoi diagrams and Delaunay triangulations, arrangements, and duality. We will apply these techniques to solve a variety of problems: convexhull computation, linesegment intersection, polygon triangulation, lowdimensional 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.
