Fall 2000

Announcements:

**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. The exact date and
time for checking a specific project will be fixed with the project's team
in our meeting on November 22.

**Project proposal:**

Each of the teams is requested to write a project
proposal according to these
guidelines,
and to submit it BEFORE Wednesday, November 22.

On Wednesday the 22th, 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 29; it will be graded and the grade will consist
of 10% of the course grade.

- Instructor: Matya Katz ( matya@cs.bgu.ac.il )
- Wednesday 12-14
- Office hours: Thursday 12:15 - 14:00, Deichmann building (58), room 315, Tel: (07) 6461628

Course description:

Assume we have a collection of flat objects lying on a table (the objects
may overlap), and we need to attach the objects to the table using a __minimum__
number of nails. How do we determine the locations of the nails ?

More formally, A set of points P is a __piercing set__ for
a collection of sets *C,
*if for each set S in* C, *at least
one of the points in P belongs to S. In our context, the sets in *C*
are geometric objects (e.g., disks or axis-parallel boxes), for which we
would like to compute a minimum (or small) piercing set; i.e., a
minimum-size set of points P, such that for each of the objects S in *C*
there exists at least one point of P that lies in S.

We will study several piercing algorithms described in scientific papers,
and implement them.

These algorithms include:

An algorithm for maintaining a minimum (alternatively, small) piercing set for a collection of segments on the x-axis.

An algorithm for computing a piercing set of size at most c (if such a set exists) for a collection of d-dimensional (axis-parallel) boxes, where c is a constant depending on the dimension d.

An algorithm for computing a (small) piercing set for a set of disks in the plane.