# Projects
Course –
Geometric Algorithms 202-1-4141

Fall 2005

# Prerequisite:
Algorithms

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.

### Bibliography:

###

##### Last update: August 28,
2005