Question

Having a set of points P in 2D, the convex hull (CH) is the smallest convex polygon covering P completely.

a) A convex polygon is a polygon whose vertices are less than 180 degrees.
b) The vertices of the CH are a subset of P.
c) Let's e be an edge of CH. Consider the line L passing through e. All points in P are on one side of L (left or right).
d) Calculating whether a point lies on the left or right of a line L takes constant time.
Design a D\&C algorithm that calculate the convex hull of P with O(n³) time complexity.

Answer 1

The question relates to the design of a D&C algorithm for finding the convex hull with a specific time complexity. However, common algorithms like Quickhull offer better average time complexity than O(n³) for computing the convex hull.

Step-by-step explanation:

The student has asked for a Divide and Conquer (D&C) algorithm design to calculate the convex hull of a set of points P with an O(n³) time complexity.

A convex hull is indeed the smallest convex shape that includes all points in P. To confirm the properties of convex polygons and convex hulls: (a) The angles at the vertices of a convex polygon are all less than 180 degrees. (b) The vertices of the convex hull are a subset of the point set P.

(c) Any line passing through an edge of the convex hull will have all points in P on one side of it. And (d) Determining whether a point lies to the left or right of a line can be done in constant time. However, in terms of algorithmic design, while D&C could be used, it is generally more efficient to use algorithms like Quickhull or the Divide and Conquer method by Preparata and Hong, which have a better average case complexity closer to O(n log n) rather than O(n³).