600.488 Homework Assignment 3
Due: Wednesday, April 1, 1998
A line segment in the plane is isothetic if it is parallel to either the
x- or y-axis, and a rectangle is isothetic if all of its boundary
line segments are isothetic.
Design efficient algorithms for each of the following problems:
Rectilinear Segment Intersection Counting.
Given n horizontal and vertical line segments in the plane,
determine for each
segment s the number of other segements which intersect s.
Rectangle Searching: Counting Problem.
Given n isothetic rectangles in the plane and n points in the plane
determine for each point p the number of rectangles which contain p
in their interior.
Design an efficient algorithm to solve the following problem:
Given n ``mouse'' robots and n ``cheese'' spots,
whose respective positions are
specificed by points in the plane, such that the mouse robots are
separated from the cheese spots by a vertical line, find a matching of
the mice points with the cheese points by straight line segments so that
every mouse point is matched with a cheese point and such that
no two segments intersect.
Intuitively, this corresponds to the paths the mice will have to make
so that each mouse can get to a piece of cheese without crashing into
any other mouse.
Describe an efficient way to implement the following procedure:
1. Set i to 1.
2. Find the convex hull, H, of S.
3. Mark each point in H as being on ``layer'' i.
4. Remove each point in H from S.
5. Set i to i+1.
6. If S is not empty, then goto Step 2.
The layers defined by the above procedure produce an ``onion'' of
Describe a data structure to quickly determine the layer number that
a query point p would have if it were added to S and we were to
re-run the above procedure.
Shoot for a query time of O(log n) and space/pre-processing of
O(n), given the convex layers of S.
The set distance from a point p to a set of points S
is defined as
q is in S},
where d(a,b) is the
normal Euclidean distance from a to b.
The directed Hausdorf distance from a set of points A to
a set of points B is
a is in A},
and the Hausdorf distance between a set of points A and
a set of points B is
This metric is used to measure
similarity between two sets of points.
Outline an efficient algorithm
for computing the Hausdorf distance between two sets, A and B,
each containing n points in the plane.