Instructor: Alexander Wolff, HG 7.41, tel. 5576, awolff "at" win "dot" tue "dot" nl

Registration: You must be registered for this course on studyweb.

Course Description: 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.

Course objectives: 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.

Format: One lecture of two hours per week; Thursdays, hours 3 and 4 (from 10:45 to 12:30) in AUD 7. Please check the schedule for the exact dates. It is expected that you study the material listed under "Self-Study" yourself - even (and especially!) if it has not been covered in class.

You can always drop by my office to ask questions concerning the course or the assignments. If you want to be sure that I have time for you, make an appointment by email.

1. Three homework assignments which each count for 20% of the final grade.
2. A 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. Similary, if you reach less than 50% of the possible points on the homework assignments, then you will also fail the course. In both cases your grade will be the minimum of 5 and the grade you achieved.

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. The exact due dates for those will be announced.

I highly recommend the (free!) drawing editor Ipe to draw figures for the inclusion in Latex documents. I'm using ipe to make the slides for this course, too.

Research Project: As part of the course you have to write a paper about one of the problems on the list included in the zip archive about the research report. The papers are supposed to be written in pairs. Each pair has to select three preferred problems from the list. I will then assign each pair a topic if possible from their preferred problems. The requirements for the research project are spelled out in detail in the zip archive.

Hint: Check Simon Peyton Jones's page about research skills and don't miss his slides about "How to write a good research paper" [ppt, pdf].

Academic Dishonesty: All class work has to be done independently or together with your partner in case of the research project. You are of course allowed to discuss the material presented in class, homework assignments, or general solution strategies with me or your classmates, but you have to formulate and write up your solutions by yourself. If you use other sources in producing answers (papers or books, friends or classmates, information found on the internet ...) then you must cite these sources clearly. Problem solving is an important component of this course so it is really in your best interest to try and solve all problems by yourself. If you represent other people's work as your own then that constitutes plagiarism and will be dealt with accordingly.

Schedule:

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications (3rd edition).
Springer-Verlag, Heidelberg, 2008.