What is convex hull? What is the convex hull problem?

For a subset $S$ of $R^d$, the convex hull $conv(S)$ is defined as the smallest convex set in $R^d$ containing $S$.

The convex hull computation means the ``determination'' of $conv(S)$ for a given finite set of $n$ points $S = \{p^1, p^2, \ldots, p^n\}$ in $R^d$.

The usual way to determine $conv(S)$ is to represent it as the intersection of halfspaces, or more precisely, as a set of solutions to a minimal system of linear inequalities. This amounts to output a matrix $A \in R^{m \times d}$ and a vector $b\in R^m$ for some $m$ such that $conv(S) =\{ x \vert A \; x \le b \}$. When $conv(S)$ is full-dimensional, each (nonredundant) inequality corresponds to a facet of $conv(S)$. Thus the convex hull problem is also known as the facet enumeration problem, see Section 2.12.

Some people define the convex hull computation as the determination of extreme points of $conv(S)$, or equivalently that of redundant points in $S$ to determine $conv(S)$. This is much simpler computation than our convex hull problem. In fact, this can be done by solving $O(n)$ linear programs and thus polynomially solvable, see Section 2.19 and 2.20. It is better to name this as the ``redundancy removal for a point set $S$''.