In many areas of computer science - robotics, computer graphics, virtual reality, and geographic information systems are some examples - it is necessary to store, analyse, 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.

Lecturers:
  Joachim Gudmundsson and Thomas Wolle
  Office: Level 5 West, School of Information Technology
  Email: joachim.gudmundsson and thomas.wolle (at) nicta.com.au
  Phone: 02 8306 0758 and 02 8306 0757

Class Time and Venue: (see Schedule)
    Thursdays, 14:00 - 16:00
    4th of March 2010 to 3rd of June 2010
    New Law School Seminar room 028

Course Objectives:
This is an introductory course to computational geometry and its applications. We will discuss techniques needed in designing and analyzing efficient algorithms for problems in geometry, including convex hulls, geometric intersections, Voronoi diagrams, Delaunay triangulations, geometric data structures, and motion planning.

Textbook:
    M. de Berg, O. Cheong, M. van Kreveld and M. Overmars .
    Computational Geometry: Algorithms and Application (3rd ed).
    Springer-Verlag, Heidelberg, 2008. ISBN 978-3-540-77973-5.
    (2nd edition is also fine).

Prerequisites:
Knowledge of basic algorithm design techniques. Knowledge of basic analysis techniques such as asymptotic notation, solving summations and recurrences. Knowledge of basic data structures.

Home Work:
There will be 3 homework assignments. The solutions have to be non-handwritten and handed in on time as a pdf-file by email. Late homework will not be accepted. If you think that you have a legitimate excuse for handing in a homework late, contact us well in advance.
The assignments are due:
    Assignment 1: deadline: 2010-04-15, see "News" page
    Assignment 2: deadline: 2010-05-06, see "News" page
    Assignment 3: deadline: 2010-05-28, see "News" page

Advice on how to do the home work:
- Please make sure you write your name and page number on every page.
- Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for "your worst answer", as this indicates how well you understood the question.
- Some of the questions are very easy (with the help of the lecture notes or book). You can use the material presented in the lecture or book (without proving it). You do not need to write more than necessary (see comment above).
-When giving answers to questions, we always would like you to prove/explain/motivate your answers.
-When giving an algorithm as an answer, the algorithms does not have to be given as (pseudo-)code.
-If you do give (pseudo-)code, then you also have to explain your code and your ideas.
- Unless otherwise stated, we always ask about worst-case analysis, worst case running times etc. (for example, hashing does not guarantee anything in the worst case, in general).
- As done in the lecture, and as it is typical for an algorithms course, we are interested in the most efficient algorithms. Hence, the faster your algorithm, the more points we can give you.
- It might help you (and us) if you briefly describe your general idea, and after that you might want to develop and elaborate on details. If we don't see/understand your general idea, we cannot give you points for it.
-If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then add references to your sources.

Exam and final mark:
There will be an exam at the end of the course. You have to pass this exam to pass the course. Your final mark will be calculated as the average of the three assignments and the exam.

Academic Dishonesty:
In general all class work is to be done independently. You are allowed to discuss class material, homework problems, and general solution strategies with your classmates. When it comes to formulating and writing solutions you must work alone. If you make use of other sources in coming up with your answers you must cite sources clearly (papers or books in the literature, friends or classmates, information on the web, whatever).
Note that we reserve the right to have an oral examination of the assignments if we believe it is necessary.
Representing other people's work as your own, however, is plagiarism and is in violation of university policies.