![[topimage]](IMADA_en.png)
Exercises
-
Exercises 12.3, 12.4, 12.5.
In 12.4, you should read "size" as "number of fragments".
-
A simple polygon path is the same as a simple polygon,
except that the curve
can start and end at different vertices, i.e., it does not have to be closed.
Recall that simple means that paths do not self-intersect.
Angles of 180° at vertices are allowed.
- Design and analyze an algorithm for computing a simple polygon path connecting n input points.
- Can any simple polygon path over n point be obtained from a simple polygon by removing an edge?
- Design and analyze an algorithm for computing a simple polygon connecting n input points.
-
A point q in the plane is dominated by a point p
if p.x ≥ q.x and p.y ≥ q.y.
A point from an input set of n points
is called dominating if it is not dominated by any other point.
The dominating set of a set of points S is the
set of all dominating points in S.
- Design a divide-and-conquer algorithm for computing the dominating set.
- Assume that somebody will provide a lexicographically sorted input set. Design a linear time algorithm for computing the dominating set.
-
Assume that we have n mice located under the x-axis
and n cheeses located above. You may assume that the mice
and cheeses are in general position.
We would like to assign one cheese to each mouse so that when
the mouse runs straight to its cheese, it will not bump into
another mouse, independent of their relative speeds.
- Does it work to sort both mice and cheeses on their x-coordinates and assign them pair-wise in that order?
- Design and analyze an algorithm that solves the problem in time O(n2log n).
- Make reasonable assumptions and show that this problem cannot be solved in time faster than Θ(n log n).
-
A matryoshka is a Russian doll with smaller dolls recursively inside.
Here we try to find one-dimensional matryoshkas.
Given a set of n line segments, I1, ..., In,
a one-dimensional matryoshka is a subset
Ij1, ..., Ijk
such that Ij1 ⊂ Ij2, ...,
Ijk-1 ⊂ Ijk
and k is the size of the matryoshka.
To make it clear, the line segments are in one dimension, so
a line segment can be represented as a starting and ending x-coordinate.
For instance, the line segment (2,4) is a subset of (1,5),
but not a subset of (1,3).
- Design and analyze an algorithm for finding the size of the largest matryoshka.