 | |
Teachers: Herman Haverkort (office: HG 7.35) and Kevin Buchin (office: HG 7.40)
Course dates: spring 2010 (quartile 3 and 4)
Herman Haverkort is on vacation until the end of January.
Please direct any questions about this course to Kevin Buchin. |
To take this course, register before 7 February! See below for details.
|
In many areas of computer science - robotics, computer graphics, 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 techniques and concepts needed for the design and analysis
of geometric algorithms and data structures. Each technique and concept will be
illustrated on the basis of a problem arising in one of the application areas
mentioned above.
At the end of this course participants should be able to decide which algorithm or
data structure to use in order to solve a given basic geometric problem. Participants
should be able to analyze new problems and come up with their own efficient solutions
using concepts and techniques from the course.
There will be one lecture of two hours per week. Each week we will list some
material for self-study, which you will be expected to study yourself (especially if it
has not been covered in class.) There will be three homework assignments and a research project. The research project is to
write a paper of about 5000 words (10 pages) about a geometric computation problem from a list provided by the instructors
(for example, here is the list used in 2009). The papers
are supposed to be written in pairs. Each pair has to select three preferred problems from
the list. We will then assign each pair a topic, if possible one of their preferred problems. You can always drop by the instructors' offices to ask questions concerning the course or
the assignments. If you want to be sure that they have time for you, make an appointment by email.
Note that Herman Haverkort is on sabbatical leave until the course starts; please direct
any questions you have until then to Kevin Buchin. For a more detailed impression of the course, see
last year's course website.
Students who want to take this course need to register on StudyWeb before 7 February.
Book (compulsory):
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars,
Computational Geometry: Algorithms and Applications (3rd edition).
Springer-Verlag, Heidelberg, 2008.
Before taking geometric algorithms you should complete Advanced Algorithms (2IL45).We will expect that you have experience with the following topics:
- basic algorithm design techniques, such as divide-and-conquer, greedy algorithms and
linear programming;
- basic analysis techniques, such as proofs with induction and invariants, O-notation,
solving recurrences and summations, and basic probability theory;
- basic data structures, such as binary search trees and heaps.
The final grade will be based on:
- three homework assignments, which each count for 20% of the final grade;
- the research project, which counts for the remaining 40% of the final grade.
There will be no written examination. If the grade for your research project is a 5 or lower,
then you will fail the course regardless of the points which you got for the homework assignments.
Similarly, if you reach less than 50% of the possible points on the homework assignments, then you
will also fail the course. Should you fail the course on your first try then you will have the opportunity to (1) solve a 4th
homework assignment whose grade will replace your worst assignment grade, and/or (2) prepare an
improved version of your research project. | |
