Question

How many comparisons are required to
solve convex-hull problem using brute-force
problem solving technique?​

Answer 1

Answer:

O(n³) this is the exect ans

Answer 2

Answer:

Given a set of points P, test each line segment to see if it makes up an edge of the convex hull. In a d-dimensional space, the complexity is O(nd+1)

Explanation:

Algorithm:

Given the set of points for which we have to find the convex hull. Suppose we know the convex hull of the left half points and the right half points, then the problem now is to merge these two convex hulls and determine the convex hull for the complete set.

This can be done by finding the upper and lower tangent to the right and left convex hulls. This is illustrated here Tangents between two convex polygons

Let the left convex hull be a and the right convex hull be b. Then the lower and upper tangents are named as 1 and 2 respectively, as shown in the figure.

Then the red outline shows the final convex hull.

#SPJ3