As a rst step go to the second page and read the section: Advice on how to do
the home work.
1. Consider the following algorithm to compute the convex hull of a set S of
n points in the plane.
Step 1: Sort the points in S by increasing x-coordinate.
Step 2: Recursively compute the convex hull of the left half of the point
set. The resulting convex hull is denoted H1.
Step 3: Recursively compute the convex hull of the right half of the point
set. The resulting convex hull is denoted H2.
Step 4: From H1 and H2 compute the convex hull H of the entire point
set.
(a) Assume that step 4 can be implemented in time O(n). What is the
running time of the algorithm? Prove your time bound. [2 point]
(b) Consider the edge e connecting the highest point in H1 with the
highest point in H2. Will the edge e be an edge in H? Prove your
answer. [2 points]
(c) Consider the points clockwise along H1 between the highest point
of H1 to the lowest point of H1. Can any of these points be in the
convex hull, H, of the entire set? Prove your answer. [1 points]
(d) Give a correct implementation of step 4, that runs in O(n) time.
Prove the correctness and the running time of your algorithm. [5 points]
2. A simple (hole-free) polygon P is called star-shaped if it contains a point
q such that for any point p in P the line segment pq is contained in P.
Give a fast algorithm that decides if a given polygon is star-shaped or not
(a faster algorithm gives higher marks). [10 points]
3. Let P be a convex polygon with n vertices. The width of P is the minimum
distance between any two parallel lines such that P is between them. Give
an algorithm that computes the width of P in O(n) time. Argue why your
algorithm is correct and why its running time is O(n). You may assume
that the vertices of P are given in, say, counter-clockwise order. [10 points]
4. Given a set S of n axis-aligned rectangles in the plane develop an algorithm
that can decide if there exists a point in the plane that intersects every
rectangle. State the algorithm, its complexity and argue its correctness.
[10 points] Discussion: Can your algorithm be extended to also work for
a set of convex polygons?
Advice on how to do the home work
Be careful with giving multiple or alternative answers. If you give multiple
answers, then we will give you marks only for "your worst answer", as this
indicates how well you understood the question.
Some of the questions are very easy (with the help of the lecture notes or
book). You can use the material presented in the lecture or book (without
proving it). You do not need to write more than necessary (see comment
above).
When giving answers to questions, we always would like you to prove/
explain/motivate your answers.
When giving an algorithm as an answer, the algorithms does not have to
be given as (pseudo-)code.
If you do give (pseudo-)code, then you also have to explain your code and
your ideas.
Unless otherwise stated, we always ask about worst-case analysis, worst
case running times etc. (for example, hashing does not guarantee anything
in the worst case, in general).
As done in the lecture, and as it is typical for an algorithms course, we
are interested in the most e cient algorithms. Hence, the faster your
algorithm, the more points we can give you.
It might help you (and us) if you brie y describe your general idea, and
after that you might want to develop and elaborate on details. If we don’t
see/understand your general idea, we cannot give you points for it.
If you use further resources (books, scienti c papers, the internet,...) to
formulate your answers, then add references to your sources.