CS 5114 Homework 4 (Spring 2008)

Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution. If you use any new words or phrases, define them, especially if we have not used these words/phrases in class. Do not describe your algorithms only for a specific example you may have worked out. You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Describe an analysis of your algorithm and state its running time.

1. (15 points) Solve exercise 1 in Chapter 6 (pages 312-313) of your textbook.
2. (30 points) Solve exercise 12 in Chapter 6 (pages 323-324) of your textbook.
3. (15 points) Solve exercise 17 in Chapter 6 (pages 327-328) of your textbook.
4. (40 points) A convex polygon is a polygon where very interior angle is less than 180 degrees. A museum is in the shape of a convex polygon with n vertices. The museum is patrolled by guards. The Directory of Security at the museum has the following rules to ensure the most safety in as time-economical a way as possible:
   1. Each guard traverses a path in the shape of a triangle; each vertex of such a triangle must a vertex of the polygon.
   2. A guard can survey all the points inside his or her triangle and only these points; we say that these points are covered by the guard.
   3. Every point inside the museum must be covered by some guard.
   4. The triangles traversed by any pair of guards do not overlap in their interiors, although they may share a common edge.
   Given these constraints, the cost incurred by a guard is the length of the perimeter of the triangle the guard traverses. Our goal is to find a set of guards such that the total cost of the guards (i.e., the sum of the costs of the individual gaurds) is as small as possible. Devise an algorithm whose running time is polynomial in n to solve this problem. Note that we are not trying to minimise the number of guards; we want to minimise the total lengths of the routes patrolled by the guards.

   

   Above are four figures that illustrate the problem. The museum is the polygon ABCDEFG. Each coloured (shaded) triangle corresponds to a guard and the guard will traverse the perimeter of his or her triangle.

   • The top two figures show a set of guards (their triangles) that satisfy the constraints laid down by the Directory of Security. In the top left figure, the guards traverse the boundaries of triangles AFG (blue), ABF (green), BEF (pale red), BDE (light red), and BCD (brown). In the top right figure, the guards traverse ABG (blue), BCG (green), CDG (brown), DFG (light red), and DEF (pale red).
   • The bottom two figures show a set of triangle that do not satisfy these constraints: in the figure on the bottom left, part of the museum is not covered by any guard (the unshaded triangle BEF) while in the figure on the bottom right, the pink triangle (AEF) and the green triangle (BEF) intersect (not that the part of the green triangle is covered by the pink triangle).