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.
Thur 16:00-18:00. Room: Eastern Avenue Seminar Room 310, Sydney Uni.
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.
M. de Berg, M. Overmars, M. van Kreveld and O. Schwarzkopf
Computational Geometry: Algorithms and Application (2nd ed).
Springer-Verlag, Heidelberg, 2000. ISBN 3-540-65620-0.
- Knowledge of basic algorithm design techniques.
- Knowledge of basic analysis techniques such as asymptotic notation, solving
summations and recurrences.
- Knowledge of basic data structures.
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.
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
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 45-61)
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 - kd-trees, Range trees.
5. April 14:
Invited lecture by Godfried Toussaint.
A simple linear algorithm for intersecting convex polygons. [pdf]
Application of Voronoi diagrams to non-parametric decision rules. [pdf]
6. April 21:
Fractional cascading, Interval trees.
7. April 28:
7. May 5:
8. May 12:
Voroni Diagrams and Duality.
9. May 19:
Arrangements and Delaunay triangulation.
10. May 26:
Well-separated pair decompositions.
11. June 2:
Latex and CG links: