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

Question

Let S be a set of n points. Assume no two points of S have the same z coordinate. Let XMIN(S) be the points of S with the smallest z 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[L.nj, Both arrays are sorted in the order these vertices appear along the convex hull. Given these arrays, suggest an O (logn) time algorithm so when a new point q (q.x.9.y) is given, you could find in q is in CH(S) in time O(log n).

Explanation / Answer

As both the lists of Convext hull is sorted, we can use binary serach algorithm to find out whether a give point lies on the convex hull or not. The search will be of order O(loh n).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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