Announcements:
Instructor:
Matya
Katz (
matya@cs.bgu.ac.il )
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.