The intersection of convex sets is apparently a convex set. The convex hull $\ch(P)$ of a set $P$ in the plane is the smallest convex set containing the set $P$, which can be written in the following way:
$$\ch(P)=\bigcap_{K\supseteq P \text{ convex}}K.$$
We will deal with algorithms which find the convex hull of a finite set $P$ effectively. In this case we use the fact that the convex hull is
$$\ch(P)=\bigcap_{H\supseteq P \text{ a halfplane }}H.$$
We do not need to consider all such halfplanes. It is enough to intersect only those halfplanes that are determined by a pair of points from $P$ and that also contain all the other points from $P.$ Therefore the convex hull of a finite nonempty set with at least two points is a convex polygon which can degenerate to a line segment.
Naive algorithm.
In this section we show that only knowledge of mathematical definition does not suffice to create a good algorithm. Our naive algorithm will search for oriented segments $pq$ which form the clockwise boundary of the convex hull. It is based on the fact that for such an oriented segment there is no point of the set $P$ lying to the left of the oriented line $pq$.
Picture 1.2 To the left of the oriented line $pq$ there is no point of the set $P$.
The fact that a point $r$ lies to the left of the oriented line $pq$ can be expressed mathematically by the following condition on the determinant the rows of which are the coordinates of the vectors $q-p$ and $r-p$:
Output. A list $\mathcal L$ containing the vertices of $\mathcal{CH}(P)$ in clockwise order.
$E\leftarrow \emptyset$
for all ordered pairs $(p,q)\in P\times P$ with $p$ not equal to $q$
do valid $\leftarrow$ true
for all points $r\in P$ not equal to $p$ or $q$
do if $r$ lies to the left of the directed line from $p$ to $q$
thenvalid$\leftarrow$ false.
ifvalidthen Add the directed edge $\overrightarrow{pq}$ to $E$.
From the set $E$ of edges construct a list $\mathcal L$ of vertices of $\mathcal{CH}(P)$, sorted in clockwise order.
The time complexity of this algorithm for $n$ points in the entry is $O(n^3)$ since we go through all oriented lines determined by $n$ points and for every such line we test if remaining points lie to the left. The next shortage is the fact that the algorithm is unstable. If three points $p_1$, $p_2$, $p_3$ lie on one line, it can happen that oriented segments $p_1p_2$, $ p_2p_3$ and $p_1p_3$
are elements of the set $E$ of boundary segments. However then we can have a problem with ordering them to the sequence in clockwise order.
Picture 1.3 Three points of the set $P$ being on only one boundary line segment.
Better algorithm - Graham's scan.
We get a much better result if we order the points of the set $P$ in a suitable way before we start with searching boundary segments of the convex hull. We use lexicographic layout of points, first according to the coordinate $x$ and then according to the coordinate $y$. Explicitly,
$$p \lt q \quad\text{ iff } p_x \lt q_x \text{ or }(p_x=q_x \text{ and }p_y \lt q_y).$$
In this arrangement let us denote the points from the smallest to the biggest
The point $p_1$ which is the "most left" and the point $p_n$ which is the "most right" have to lie on the boundary of the convex hull and split this boundary into an upper and a lower part. To omit long formulations we will talk (not exactly) about an upper and lower convex hull instead of talking about an upper and a lower part of the boundary of the convex hull.
Picture 1.4 The upper (blue) and the lower (green) convex hull.
The clockwise arrangement of the points of the upper convex hull corresponds with their lexicographic order. That is why our algorithm will search for the upper convex hull of the sets
$$P_i=\{p_1,p_2,\dots,p_i\}$$
from $i=2$ to $i=n$. Then it will search for the lower convex hull of the sets
$$\{p_{n-i},p_{n-1+1}\dots, p_{n-1},p_n\}$$
for $i=1$ to $n-1$ in a similar way.
Let $\mathcal L$ be the lexicographically ordered list of the vertices of the upper convex hull of the set $P_i$. It always contains points $p_1$ and $p_i$.
Now we show how to change the list $\mathcal L$ to contain the vertices of the upper convex hull of the set $P_{i+1}$. The lexicografically biggest point $p_{i+1}$ has to be in the upper convex hull, so we start by adding it into $\mathcal L$.
The points which do not belong to the upper convex hull of the set $P_{i+1}$ will be discarded from the list $\mathcal L$ gradually in the following way: We take the last three points $p_j \lt p_i \lt p_{i+1}$ in the list $\mathcal L$. If the point $p_{i+1}$ lies to the right of the oriented line $p_jp_i$, we will say that the points $p_j$, $p_i$ and $p_{i+1}$ form a right turn. In this case we will not change the list $\mathcal L$ since the points of the set $P_{i-1}$ lie to the right of the oriented line $p_ip_{i+1}$. So we have the list of vertices of the upper convex hull of the set $P_{i+1}$ and we can start to search for the list of vertices of the upper convex hull for the set $P_{i+2}$,
if $i+2\le n$.
Picture 1.5 Right turn.
If the points $p_j$, $p_i$ and $p_{i+1}$ do not form a right turn, we exclude the middle one, i. e. $p_i$, from the list $\mathcal L$. If $p_i$ lies on the segment $p_jp_{i+1}$, we do not need it for the description of the upper convex hull (although it lies in it). If $p_i$ lies to the right of the oriented line $p_jp_{i+1}$, it is not in the upper convex hull of the set $P_{i+1}$ and has to be discarded.
Picture 1.6 Cases in which the last three points of the list $\mathcal L$ do not form a right turn.
After discarding the point $p_i$ from the list $\mathcal L$ we take again the last three points of this list, if they exist, and we carry out the same procedure with them. We repeat this process until
either only two points remain in the list $\mathcal L$,
or the last three points in the list $\mathcal L$ form a right turn.
This completes the searching for the list of vertices of the upper convex hull of the set $P_{i+1}$. We illustrate this process using the following animation.
The vertices of the lower convex hull can be found analogously.
Pseudocode and time complexity.
The above verbal description can be formalized by the following pseudocode
AlgorithmConvexHull($P$)
Input. A set $P$ of points in the plane.
Output. A list containing the vertices of $\mathcal{CH}(P)$ in clockwise order.
Sort the points by $x$-coordinate, then $y$-coordinate, resulting in a sequence $p_1,\ldots,p_n$.
Put the points $p_1$ and $p_2$ in a list $\mathcal L_{\text{upper}}$, with $p_1$ as the first point.
for $i\leftarrow 3$ to $n$
do Append $p_i$ to $\mathcal L_{\text{upper}}$.
while $\mathcal L_{\text{upper}}$ contains more than two points and the last three points in $\mathcal L_{\text{upper}}$ do not make a right turn
do Delete the middle of the last three points from $\mathcal L_{\text{upper}}$.
Put the points $p_n$ and $p_{n-1}$ in a list $\mathcal L_{\text{lower}}$, with $p_n$ as the first point.
for $i\leftarrow n-2$ downto $1$
do Append $p_i$ to $\mathcal L_{\text{lower}}$.
while $\mathcal L_{\text{lower}}$ contains more than two points and the last three points in $\mathcal L_{\text{lower}}$ do not make a right turn
do Delete the middle of the last three points from $\mathcal L_{\text{lower}}$.
Remove the first and the last point from $\mathcal L_{\text{lower}}$ to avoid duplication of the points where the upper and lower hull meet.
Append $\mathcal L_{\text{lower}}$ to $\mathcal L_{\text{upper}}$, and call the resulting $\mathcal L$.
return $\mathcal L$
Theorem 1.1
The above algorithm is correct and its time complexity depending on the number of points of the set $P$ is $O(n\log n)$.
Důkaz
The proof that the algorithm gives us the list of vertices of the convex hull of the set $P$ ordered clockwise reduces to the proof that we get the list of vertices of the upper and lower convex hulls ordered lexicographically. The proof for the upper convex hulls proceeds by induction: We show that the algorithm will create the list for the upper convex hull of the set $P_{i+1}$ from the list of vertices of the upper convex hull of the set $P_{i}$. We can carry it out by similar considerations as we did during the verbal description of the algorithm. Practically focused readers will no longer be tired of them. Theoretically focused readers can try to handle the proof by themselves.
As for the time complexity, the first step of the algorithm -- to order $n$ points lexicographically takes the time $O(n\log n)$ as it is well known.
The rest of the algorithm takes only the time $O(n)$.
We put each of the points of the set $P$ into the list $\mathcal L$ once, and we take it out at most once. So the time required for the list to be created must be proportional to the number of points.
The reader will surely come up with a number of ways to improve this algorithm.
However, none of them improves the estimate $O(n\log n)$.
\(\Box\)
Another algorithm.
There are a lot of other algorithms for the convex hull of a finite set in the plane. Let us indicate one of them, which is suitable to use if we know in advance that the number of vertices of the convex hull is limited by a number $k$ which is small with respect to $n$, the number of points of the set $P$. The process of the algorithm is reminiscent of packaging, so it is called Gift wrapping.
For simplicity, let's assume that no three points lie in a line. First, we find the left most point of the set $ P $ (more precisely, the smallest in the above lexicographic layout) and mark it $ p_1 $. We make lines from the point $p_1$ to other points of the set $P$ and consider their slopes.
Let $p_2$ be such a point that $p_1p_2$ has the biggest slope from all these lines.
Now, we link the point $p_2$ to the remaining $ n-2 $ points of the set $P$. We select a point $p_3$ so that the convex angle $ \angle p_1p_2p_3 $ is the largest. In this way we proceed until we get back to the point $p_1$. This is how we wrapped the set $P$ into the convex hull. If the convex hull is a polygon with $k$ vertices, the time complexity of this algorithm is $O(kn)$. In each of the $k$ vertices, we spend $O(n)$ time.
