Reference no: EM133217287

Question: A convex polygon is a polygon where every 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:

(a) Each guard traverses a path in the shape of a triangle; each vertex of such a triangle must a vertex of the polygon.

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

(c) Every point inside the museum must be covered by some guard.

(d) The triangles traversed by any pair of guards do not overlap in their interiors, although they may share a common edge

Each guard can be specified by the triangle he/she patrols. We call a set of triangles that satisfy these rules legal. 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 triangles that are legal, since they 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 triangles 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 in the image is covered by the pink triangle). Given these constraints, the cost incurred by a guard is the length of the perimeter of the triangle the guard traverses. The total cost of a set of triangles is the sum of the length of their perimeters. Our goal is to find a legal set of triangles such that the total cost of the triangles is as small as possible. Given the x- and y-coordinates of the vertices of the art gallery and the ordering of these vertices along the boundary of the art gallery, 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. You may assume that the length of any line segment is the Euclidean distance between the end-points of the line segment and that this length can be computed in constant time. Since this problem is quite difficult, let us split up into two more digestible pieces. Let the museum be a convex polygon P with n vertices p0, p1, . . . pn-1 ordered consecutively in counter-clockwise order

around P. Except for pn-1p0, which is an edge of the polygon, a line segment pipj is a diagonal if pi and pj are not adjacent vertices, i.e., |i - j| 6= 1. Since P is convex, every point of a diagonal (other than its end-points) lies in the interior of p. Clearly, in any legal set of triangles, every triangle edge is either an edge of P or a diagonal of P. For each of the questions below, you must provide a proof for your answer. Some of the proofs may be short, especially for parts (i) and (iii).

(i) How many diagonals does P contain in total?

(ii) How many diagonals does any legal set of triangles contain?

(iii) Given a legal set of triangles, express the total cost of these triangles in terms of the perimeter of P and the lengths of those edges of the triangles that are diagonals of P.

(iv) To start formulating the dynamic programming recursion, consider the edge p0pn-1. This edge must be part of some triangle T in the optimal solution. Think about where the third vertex in T can be. Since the optimal solution contains a legal set of triangles, the edges of the other triangles in the optimal solution cannot intersect the edges of T. Use this fact to derive a recursion to compute the optimal solution. State and prove the running time of the resulting algorithm.