|Website:||website containing additional information|
|Period:||period 2 (week 46 through 5, i.e., 10-11-2008 through 30-1-2009; retake week 11)
|Participants:||up till now 34 subscriptions|
|Schedule:||Official schedule representation can be found in Osiris|
|Teachers:||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, O. Cheong, M. van Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications (3rd edition).
Springer-Verlag, Heidelberg, 2008.
ISBN 978-3-540-77973-5. 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 (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:||To qualify for participation for the second exam of this course (the second chance), the score for the first exam must be at least 4. And the homework
exams both need to have a grade of 5 or higher, either for the first or the second chance.|
|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, and point location are some examples. Each problem we study
is motivated by a practical problem from one of the application areas.