|Website:||website containing additional information|
|Period:||period 2 (week 46 through 5, i.e., 13-11-2006 through 2-2-2007; retake week 11)
|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).
Springer-Verlag, Heidelberg, 2000.
|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.