Website:  website containing additional information 
Course code:  INFOGA 
Credits:  7.5 ECTS 
Period:  period 2 (week 46 through 5, i.e., 13112006 through 222007; retake week 11)
 
Timeslot:  D1+D2 
Participants:  up till now 26 subscriptions 
Schedule:  Dit is een oud rooster!

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).
SpringerVerlag, Heidelberg, 2000.
ISBN 3540656200. 
Course form:  Two lectures of in total 4 hours per week. There will be an extra hour during which assignments can be done.

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 moet de oorspronkelijke uitslag minstens 4 zijn.
To qualify for participation in the 2nd chance exam, the score of the first exam has to be at least 4. 
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 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, point location are some examples. Each problem we study
is motivated by a practical problem from one of the application areas.
