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

ID: 3111924 • 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 r 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 UPI..n. Similarly we store the vertices of the lower convex hull LOWER[L.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 of the Convex hull is sorted, we can use a binary search algorithm to find out whether a given point lies on the convex hull or not. The search will be of order O(log n).

Navigate

Let S be a set of n points in the plane. Each point p of S is given by its x- an

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

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

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

Question

Explanation / Answer

Related Questions

Navigate