Question

10. Maxima search a. A point (xi, yi) in the Cartesian plane is said to be dominated by point (xj, уј ) İfxī x; and yi y, with at least one of the two inequalities being strict. Given a set of n points, one of them is said to be a maximum of the set if it is not dominated by any other point in the set. For example, in the figure below, all the maximum points of the set of 10 points are circled. YA Design an efficient algorithm for finding all the maximum points of a given set of n points in the Cartesian plane. What is the time efficiency class of your algorithm? b. Give a few real-world applications of this algorithm.

Answer 1

Sort all points by increasing x coordinates. If two points have the same x coordinate, sort them by decreasing y coordinates. Now, it can be shown that a subset of points is non-dominated if and only if their y coordinates are non-increasing in our sorted sequence, meaning each y coordinate is less than or equal to the previous one in the subsequence.

So the algorithm would be:

1. Sort the points as described above. Time: O(n*logn).
   Use merge sort.
2. Find the longest non-increasing sub-sequence of y coordinates. Time: O(n*logn).
   This can be done by adapting the algorithm for finding the longest increasing sub-sequence.

Longest Increasing Sub-sequence :

The algorithm outlined below solves the longest increasing subsequence problem efficiently with arrays and binary searching. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as X[0], X[1], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i. Note that j ≤ (i+1), because j ≥ 1 represents the length of the increasing subsequence, and k ≥ 0 represents the index of its termination.

P[k] — stores the index of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far. Because the algorithm below uses zero-based numbering, for clarity M is padded with M[0], which goes unused so that M[j] corresponds to a subsequence of length j. A real implementation can skip M[0] and adjust the indices accordingly.

Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is increasing. For, if there is an increasing subsequence of length j ≥ 2 ending at X[M[j]], then there is also a subsequence of length j-1 ending at a smaller value: namely the one ending at X[P[M[j]]]. Thus, we may do binary searches in this sequence in logarithmic time.

Psuedo Code :

P = array of length N
 M = array of length N + 1

 L = 0
 for i in range 0 to N-1:
   // Binary search for the largest positive j ≤ L
   // such that X[M[j]] < X[i]
   lo = 1
   hi = L
   while lo ≤ hi:
     mid = ceil((lo+hi)/2)
     if X[M[mid]] < X[i]:
       lo = mid+1
     else:
       hi = mid-1

   // After searching, lo is 1 greater than the
   // length of the longest prefix of X[i]
   newL = lo

   // The predecessor of X[i] is the last index of 
   // the subsequence of length newL-1
   P[i] = M[newL-1]
   M[newL] = i

   if newL > L:
     // If we found a subsequence longer than any we've
     // found yet, update L
     L = newL

 // Reconstruct the longest increasing subsequence
 S = array of length L
 k = M[L]
 for i in range L-1 to 0:
   S[i] = X[k]
   k = P[k]

 return S

Time complexity :

The algorithm is composed of two steps, each taking O(n*logn) time.
This gives our algorithm O(n*logn) time.

Q2)

• Finding the outer region of any area/city.
• Covering a field or deciding the outer region till when to use crop planes.

******************NOTE******************

If there is any problem with the code.. or If you have some doubts... please ask in the comments. :)
If everything is good, please rate positively ... as it directly affects our payscale :)