Assume that we are given a set of point S, given to you when sorted according to
ID: 3885378 • Letter: A
Question
Assume that we are given a set of point S, given to you when sorted according to their x-coordinates. However, you run Graham scan without changing their order. Consider the point that the Stack S contains when the algorithm terminates. Are they the vertices of CH(S)? Are these all the vertices of CH(S)? Let S be a set of n points. Assume no two points of S have the same x coordinate. Let XMIN(S) be the points of S with the smallest x coordinate, and let XMAX(S) be the point with the largest x coordinate. See Figure 1 As we walk along CH(S) from XMAX to XMIN in the CCW direction, we are walking on the upper part of the convex hull. Assume its vertices are sorted in an array UP[1. n]. Similarly we store the vertices of the lower convex hull LOWER[1..n]. Both arrays are sorted in the order these vertices appear along the convex hull. Given these arrays, suggest an O(log n) time algorithm so when a new point q = (q.x, q.y) is given, you could find in q is in CH(S) in time O(log n).Explanation / Answer
As both the lists for Convex hull is sorted, we can use binary search to find out whether a given point is on the Convex hull or not.The complexity of bibary search is O(log n)