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:period 2 (week 46 through 5, i.e., 13-11-2006 through 2-2-2007; retake week 11)
Timeslot:D1+D2
Participants:up till now 33 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
college   Wed 13-1546-51,2-4 MIN-211
Fri 09-1246,48-50,2-3 Rup-C
47,51 KRUYT-O111
Fri 9-124 BBL-420
lecture          Marc van Kreveld
Frank van der Stappen
   
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 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 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.
wijzigen?