Question

33-1 Convex layers Given a set Q of points in the plane, we define the convex layers of Q inductively. The first convex layer of Q consists of those points in Q that are vertices of CH(O). Fori >1, define Qi to consist of the points of Q with all points in convex layers 1,2,.. .i -1 removed. Then, the ith convex layer of Q is CH(Q if Q 0and is undefined otherwise. a. Give an O(n2)-time algorithm to find the convex layers of a set of n points.

Answer 1

solution:

Given that: - convex layers given a set Q of points in the plane, we define the convex layers of Q indictivity. Given an O (n^2)-time algorithm to find the convex layers of a set of n points. The package wrapping Technique can be used to compute convex hull of a set Q given by is march. So, we can say, The running time of the algorithm runs in O (nh), \r\n O (nh), Here h = No. of vertices of CH (Q) So, finally, The total running time for k convex layer and the ith layer contains li points is, O (nl_1 + nl_2 + .... + nk_k) = O (n^2) we know that, [Because sigma^k_i = 1 l_i = n]