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.
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.