Finding the convex hull

Consider a set $A$ that contains a collection of points $(x_1,y_1),\dots ,(x_n,y_n)$. Then, we can define a convex hull from $A$ as

$$\text{Convex-Hull}(A)=\{z=(x,y)\in \{\mathbb{R}{\}}^2\mid z\text{ is an average of points in }A\}$$

A given point $i$ gets a weight $w_i\ge 0$ such that ${\sum }_{i=1}^n{w}_i=1$ and $z={\sum }_{i=1}^n{w}_i\cdot (x_i,y_i)$.

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 $A$.

Output: a description of $A$‘s convex hull, as a sequence of points $(a_1,b_1),\dots ,(a_k,b_k)$ 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 $O(n^3)$, because there are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=O(n^2)$ pairs of points and it takes $O(n)$ time to check every point for each segment.

What makes divide and conquer applicable?

We make the claim that $A$ can be divided into two sets of points such that $A=A_1\cup A_2$. Then, we claim that

$$\text{Convex-Hull}(\text{Convex-Hull}(A_1)\cup \text{Convex-Hull}(A_2))=\text{Convex-Hull}(A)$$

First attempt at D&C algorithm

We only need to create/add two segments between $A_1$ and $A_2$ in order to merge them.

Consider the line $l$ that we’re using to divide $A$ into two. For each two points, one from $A_1$ and one from $A_2$, we check if the intersection of the line is the highest point on $l$.

We do the symmetric thing for the minimum as well. find the lowest intersection on $l$.

Once again we’re doing $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=O(n^2)$. The recurrence relation is then given by $T(n)=2T\left(\frac{n}{2}\right)+O(n^2)$. By the Master theorem, this recurrence simplifies to $O(n^2)$, which is an improvement

Better merge step

The issue is that the merging takes $O(n^2)$ in our previous attempt. To hit a runtime of $O(n\log n)$, our budget needs to fit in $O(n)$ time.