How many points are needed to uniquely specify a box

algebra-precalculuscombinatoricsgeometrylinear algebra

In $\mathbb{R}$, to specify a line segment, we need two points. In $\mathbb{R}^2$, to specify a given rectangle, all we need are three points. Then the fourth point is determined, and there is only one rectangle with those three points as vertices. In $\mathbb{R}^3$, to specify a cuboid, we can do it with just $4$ vertices (e.g. pick any vertex and its three adjacent vertices). Then there is only one cuboid that can have these $4$ vertices.

In general, what is the minimum number of points/vertices needed to uniquely specify a given box in $\mathbb{R}^n$? Is it $n + 1$?

Best Answer

In general, a parallelotope (the generalization of parallelograms to many dimensions) can be specified by $n+1$ points: a vertex $u$ and all the vertices $v_1,\ldots,v_n$ adjacent to that vertex - and, as long as long as there is no hyperplane on which all vertices lie, any collection of $n+1$ vertices really does extend to a parallelotope (since, essentially, one can just take the Minkowski sum of the edge vectors from $u$ to each $v_i$ to get a volume).

It seems like a box, for you, is just a parallelotope in which the faces are perpendicular to one another - they can be specified the same way, except they additionally require that the edge vectors from $u$ to each $v_i$ be pairwise perpendicular - which doesn't really bring down the number of vertices required, but it means that, if we specify $u$ then $v_1$, we would know that $v_2$ lies on some specific hyperplane, then that $v_3$ lives on a codimension two subspace, and so on - bringing down the degrees of freedom. In general, you have $n$ dimensions of choice for $u$ and $v_1$, then $n-1$ for $v_2$ and $n-2$ for $v_3$ and so on, until you only have a single dimension of choice for $v_n$.

All told, you get $n(n+1)$ degrees of freedom in choosing a parallelotope in $n$ dimensions, but only $\frac{n(n+3)}2=n+(1+2+3+\ldots+n)$ degrees of freedom in choosing a box - which is probably a more meaningful measurement than "number of points required."

Related Question