Projects course - geometric algorithms

Fall 2002

Prerequisite: Algorithms


Please note that all dates mentioned below are strict !

The projects (including the accompanying documentation) will be checked during the last week of the semester.

Project proposal:
Each of the teams is requested to write a project proposal according to these guidelines, and to submit it BEFORE Wednesday, November 13.
On Wednesday the 13th, I will meet with each of the teams to discuss their proposal. The final version of the project proposal should be submitted by Wednesday, November 20; it will be graded and the grade will consist of 10% of the course grade.

Instructor: Matya Katz  ( ) 
Wednesday 12-14
Office hours: Monday 12:15-14:00, Deichmann building (58), room 315, Tel: (08) 6461628

Course description:

Several projects will be offered dealing with the location of guards (human or non-human) in various geometric settings.  For example, assume we need to guard an art gallery by hanging rotating video cameras from the ceiling.  Our goal is to place cameras, such that (i) every point in the gallery is seen by at least one of the cameras, and (ii) the number of cameras that are used is small. This problem (when the art gallery is modeled as a simple polygon) is known as the art gallery problem (posed by Klee in 1973).

Last update: September 29, 2002