Geometric algorithms

Website:

website containing additional information

Course code:

INFOGA

Credits:

7.5 ECTS

Period:

periode 2 (week 46 t/m 5, dwz 12-11-2007 t/m 1-2-2008; herkansing week 11)

Timeslot:

D1+D2

Participants:

up till now 47 subscriptions

Schedule:

Dit is een oud rooster!

form	group	time	week	room	teacher
college		wo 13-15	48-51,2-4	BBL-471	Marc van Kreveld Frank van der Stappen
college		vr 09-12	48-51,2-4	BBL-471	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 (together 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.

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?