Let S be a set of n points. Assume no two points of S have the same x coordinate
ID: 3886009 • Letter: L
Question
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 LOW ER[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).
XMIN XMAX CH(S A set o and its convex hull CH 1n e lower convex hull (red) and the upper convex hull (blue)Explanation / Answer
As both tha arrays are sorted for convex hull, a possible algorithm suggested will be binary search. The complexity of this algorithn is of the order O(log n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.