QUESTION 7 (12 Marks) We define a point in the plane as a pair of real numbers (x, y). The aim of this question is to estimate a lower bound for any algorithm that computes the convex-hull of a given set of points in the plane. The statement of the convex-hull problem is as follows: Input: A set S of n points in the plane. Output: Find the smallest convex polygon containing S. A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon A convex polygon in the plane is a closed polygon such that every line segment between two points is included in the polygon. It is encoded as a sequence of points ordered anti-clockwise, starting at the leftmost point. For instance the convex hull of the set of points S = { a, b, c, d, e, f} in Figure 1 is aedcf. Thus, any algorithm that solves the convex-hull algorithm outputs aedef on the input S. a. C2 marks) Provide a formal statement for th ro of sorgn numbers in non-desreasing order. Is it a decision or a search problem? b. (3 marks) Let T be a set of numbers to be sorted. Show that the transformation that maps each 2) on the plane generates a correct reduction from sorting to the number z E T to a point (z, convex-hull problem c. (3 marks) What is the time complexity of the reduction in question 7.b.? (* d. (4 marks) Deduce a lower bound on the complexity of any algorithm that computes the convex hull of a set of n points. QUESTION 7 (12 Marks) We define a point in the plane as a pair of real numbers (x, y). The aim of this question is to estimate a lower bound for any algorithm that computes the convex-hull of a given set of points in the plane. The statement of the convex-hull problem is as follows: Input: A set S of n points in the plane. Output: Find the smallest convex polygon containing S. A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon A convex polygon in the plane is a closed polygon such that every line segment between two points is included in the polygon. It is encoded as a sequence of points ordered anti-clockwise, starting at the leftmost point. For instance the convex hull of the set of points S = { a, b, c, d, e, f} in Figure 1 is aedcf. Thus, any algorithm that solves the convex-hull algorithm outputs aedef on the input S. a. C2 marks) Provide a formal statement for th ro of sorgn numbers in non-desreasing order. Is it a decision or a search problem? b. (3 marks) Let T be a set of numbers to be sorted. Show that the transformation that maps each 2) on the plane generates a correct reduction from sorting to the number z E T to a point (z, convex-hull problem c. (3 marks) What is the time complexity of the reduction in question 7.b.? (* d. (4 marks) Deduce a lower bound on the complexity of any algorithm that computes the convex hull of a set of n points