Projects course - "piercing" algorithms

Fall 2000

Prerequisite: Algorithms


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


Last update: November 6, 2000