
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. 
Class Time:
Thur 16:0018:00. Room: Eastern Avenue Seminar Room 310, Sydney Uni.
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.
Text:
M. de Berg,
M. Overmars,
M. van Kreveld and
O. Schwarzkopf
Computational Geometry: Algorithms and Application (2nd ed).
SpringerVerlag, Heidelberg, 2000. ISBN 3540656200.
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.
Course Work:
There will be roughly 4 homework assignments. Normally, late homework will not be accepted.
If you think that you have a legitimate excuse for handing in a homework late, contact us
before the due date.
Academic Dishonesty:
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 site sources clearly (papers or books in the literature, friends or classmates,
information the web, whatever). It is best to try to solve problems on your own, since problem
solving is an important downloaded from these component of the course, but I will not deduct
points if you make use of outside help, provided that you cite your sources clearly.
Representing other people's work as your own, however, is plagiarism and is in violation of
university policies.
Assignments:
Homework excuses?
Assignment 1 [pdf]. Due 7th of April.
Assignment 2 [pdf]. Due 28th of April. Example solutions to three exercises. [pdf]
Assignment 3 [doc]. Due 19th of May.
Assignment 4 [pdf]
. Due 9th of June.
Schedule: The following list of schedule is very tentative.
1. March 10:
Art gallery theorems and polygon triangulation (pages 4561)
2. March 17:
Convex hulls and line segment intersection.
Interesting link: History of the linear time convex hull of a simple polygon.
3. March 24:
Linear programming  Manufacturing.
4. April 7:
Range searching 1  kdtrees, Range trees.
5. April 14:
Invited lecture by Godfried Toussaint.
Reading material:
A simple linear algorithm for intersecting convex polygons. [pdf]
Application of Voronoi diagrams to nonparametric decision rules. [pdf]
6. April 21:
Fractional cascading, Interval trees.
7. April 28:
Point location.
7. May 5:
Voronoi diagrams.
8. May 12:
Voroni Diagrams and Duality.
9. May 19:
Arrangements and Delaunay triangulation.
10. May 26:
Wellseparated pair decompositions.
11. June 2:
Delaunay triangulation
Latex and CG links:
Joachim Gudmundsson