Given a set of points in the plane, we define the convex layers of Q inductively. The first convex layer of Q consists of those

Question

3 years ago

12

Given a set 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 CHQ). For i > 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 CHQ:) if Qi 70 and is undefined otherwise. Give a O(n)-time algorithm to find the convex layers of a set of n points. Justify the correctness of your algorithm and its running time. Do NOT use Jarvin March algorithm, just adapt Graham Scan.

Mathematics

1 answer:

BigorU [14] · Answer 1 · 2022-02-10T02:07:17+03:00

Answer:

Check the explanation

Step-by-step explanation:

Package wrapping technique can he used to compute convex null of a set Q which was given by Jarvis march

The running time of the algorithm runs in 0(M), where h is the number of vertices of CH (0). The total running time for K convex la, and the I. layer contains li points is.

Kindly check the attached image below to see the step by step explanation to the question above .