Consider a set that contains a collection of points . Then, we can define a convex hull from as
A given point gets a weight such that and .
Another definition of a convex hull is to consider the set of points that make up the boundary of the convex hull. Then, a segment makes up part of the boundary if and only if there does not exist points on both sides of the segment, if we extended the ends towards infinity.
If points existed on both sides then we’re not bounding/enclosing the points and therefore this is not a boundary.
Problem
Input: list of points .
Output: a description of ‘s convex hull, as a sequence of points that describe the boundary in a counter-clockwise order.
Naive algorithm
For each pair of points, we draw a segment between them, and then check if there exists points on both sides of the segment. If so, then it’s not a boundary. Otherwise, it is.
This algorithm runs in , because there are pairs of points and it takes time to check every point for each segment.
What makes divide and conquer applicable?
We make the claim that can be divided into two sets of points such that . Then, we claim that
First attempt at D&C algorithm
We only need to create/add two segments between and in order to merge them.
Consider the line that we’re using to divide into two. For each two points, one from and one from , we check if the intersection of the line is the highest point on .
We do the symmetric thing for the minimum as well. find the lowest intersection on .
Once again we’re doing . The recurrence relation is then given by . By the Master theorem, this recurrence simplifies to , which is an improvement
Better merge step
The issue is that the merging takes in our previous attempt. To hit a runtime of , our budget needs to fit in time.