Computational Geometry (Fall 2004)

Project 3 - Finding the shortest path for a point robot

The goal is to be able to find a shortest path for a point robot in an environment of polygonal obstacles.

The running program should support the following operations.

A running program implementing of the algorithm in [BKOS, Chapter 15] is expected.

The project should be done in groups of up to three persons.

Deadline: Wednesday December 17, 2004, 14.00.

Note:The evaluation of the report and implementation will be part of the final grade.

Project 2 - Point location

The goal is to build a data structure for a decomposition of the plane that supports to locate the face containing a given point.

The running program should support the following operations.

A running program implementing one of the planar point location data structures in [BKOS, Chapter 6] or [ST86] is expected.

The project should be done in groups of up to three persons.

Deadline: Friday November 12, 2004, 14.00.

Note:The evaluation of the report and implementation will be part of the final grade.

Project 1 - Line segment intersection

The goal of the project is to be able to input line segments from the screen and a file, compute their intersections and to store them together with their intersections as a planar graph represented in a DCEL structure. A technical goal is to be able to handle DCEL's.

The running program should support the following operations.

A running program implementing the sweep line algorithm in [BKOS, Chapter 2] and a report is expected.

The project should be done in groups of up to three persons.

Deadline: Wednesday October 6, 2004, 9.15.

Note:The evaluation of the report and implementation will be part of the final grade.


This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>