What is a dimension of a convex hull?

Question

Let $S$ be a set of data points in $E^d$, a real Euclidean space of dimension $d$. What would be the dimension of the convex hull of that data?

In general, what is the definition of the dimension of the convex hull, and how do you calculate it?

Answer 1

As the paper says, the dimension is just the dimension of the affine hull of the convex set, which is also the affine hull of the set $S$.

To compute this dimension, first translate the data back to the origin, by which I mean, choose some $x_0 \in S$ (dimension will only make sense if $S \neq \emptyset$), and subtract $x_0$ from all the data points in $S$ (including itself, i.e. so that $0 \in S$). Now, the affine hull of $S$ is the linear span of $S$ (or equivalently $S \setminus \{0\}$).

We have now reduced the problem to finding the dimension of the span of a finite set of vectors. If you put these vectors in a matrix (as rows or columns), this is equivalent to computing the rank of the matrix. I'm not really up on efficient methods for doing so; a conceptually simple method for doing so is to row-reduce the matrix and count the pivots. Here's a relevant question from another SE site.