COMP 4045 - Computational Geometry

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.
Instructor:
    Joachim Gudmundsson and Kai Xu (NICTA). Office: Bay 15, Australian Technology Park.

Class Time:
    Thur 16:00-18: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).
    Springer-Verlag, Heidelberg, 2000. ISBN 3-540-65620-0.

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 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.
        Reading material:
          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:
        Point location.
        7. May 5:
        Voronoi diagrams.
        8. May 12:
        Voroni Diagrams and Duality.
        9. May 19:
        Arrangements and Delaunay triangulation.
        10. May 26:
        Well-separated pair decompositions.
        11. June 2:
        Delaunay triangulation


Latex and CG links:


Joachim Gudmundsson
National ICT Australia
Phone: +61 02 83745484
Fax: +61 2 83745527