Let S be a set of n points in the plane Each point p of S is

Let S be a set of n points in the plane. Each point p of S is given by its x- and y-coordinates p_x and p_y, respectively. A point p of S is called maximal in S if its top-right quadrant is empty: - q sum S: q_x > p_x and q_y > p_y. See Figure 1 for an example. Observe that, in general, there is more than one maximal element in S. To avoid special cases, you may assume that no two points in S have the same x-coordinate, and no two points in S have the same y-coordinate Give a divide-and-conquer algorithm (in plain English or pseudocode) that computes all maximal elements in S in O(n log n) time. Explain why your algorithm is correct. Explain why your algorithm always terminates. Analyze the running time of your algorithm when called on a set of n points. Show that it is indeed O(n log n).

Solution

findmaximal(point[], l, r)

If r > l

1.check points are in the same coordinate

Distance =sqrt(((point(i+1)-point(i))+(point(j+1)-point(j)))

While distance !=0

     Find the middle point to divide the point into two halves:

             middle m = (l+r)/2

      Call Sort for first half:  

             Call Sort(point, l, m)

     Call Sort for second half:

             Call Sort(point, m+1, r)

     Merge the two halves sorted in step 2 and 3:

             Call combine(point, l, m, r)

Find maximalpoint(point)

b)

This algorithm is correct because in this first check points are in same coordinate are not by calculating distance if the distance is zero than points are in the same coordinate.after that sort the pointsand after that find the largest point.

c)

if the distance zero than the algorithm is terminates.it means they are in same coordinate

d)

total complexity=calculation of distance+sorting+finding max

for calculation of distance in O(n) times

for finding maximum point= O(n)

for sorting:

Assumption: N is a power of two.

For N = 1: time is a constant (denoted by 1)

Otherwise: time to sort N points= time to sort N/2 pointsplus
time to merge two arrays each N/2 elements.

Time to merge two arrays each N/2 pointsis linear, i.e. N

Thus we have:

(1) T(1) = 1

(2) T(N) = 2T(N/2) + N

we will solve this recurrence relation by Next .First we divide (2) by N:

(3) T(N) / N = T(N/2) / (N/2) + 1

N is a power of two, so we can write

(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1

(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1

          .

          .

          .
(6) T(2) / 2 = T(1) / 1 + 1

the sum of their left-hand sides =sum of their right-hand sides:

After crossing the equal term, we get

(7) T(N)/N = T(1)/1 + LogN

T(1) is 1, hence we obtain

(8) T(N) = N + NlogN = O(NlogN)

Hence the complexity of the Sort algorithm is O(NlogN).

Total complexity= O(n)+ O(NlogN)+ O(n)

                          = O(NlogN).