Projects Course – Geometric Algorithms 202-1-4141
Fall 2005

Prerequisite: Algorithms



Matya Katz  (

Office hours: TBA, Deichmann building (58), room 315, Tel: (08) 646-1628


Class Time:

Thursday  10-12

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).  For another example, assume we need to place lamps along a wiggly wall, so that every point on the wall is lit by one of the lamps (alternatively, we need to place antennas that require line of sight along a hilly road, so that every point on the road is covered by one of the antennas. Again the goal is to use as few as possible lamps (resp. antennas). In this problem we model the wall (resp. road) by a monotone polygonal line.





Last update: August 28, 2005