Let S be a set of n points. Assume no two points of S have the same x coordinate

Question

Let S be a set of n points. Assume no two points of S have the same x coordinates. Let X MIN(s) be the points of S with the smallest x coordinate, and let XMAX (S) be the point with the largest x coordinate. 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[l..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 middot x, q middot y) is given, you could find in q is in CH(S) in time O(log n).

Explanation / Answer

As both the arrays of convext hull is sorted, we can use binary search to find out whether a number is on the convex hull or not.The complexity of this is O(log n).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.