Computationally determine if a given set of points are vertices of an n-dimensional cube.

Question

Problem definition

Given a set of points, determine (true or false) if they are the vertices of an $n$-cube.

Attempted Solutions

The following strategy isn't sufficient:

Calculates the square of the distances between all possible pairs of points (including self-pairs and both $(p_i,p_j)$ and $(p_j,p_i)$ for all points $p_j$ and $p_i$ where $i\neq j$) and normalises them by the smallest non-zero square distance (i.e. the square of the sides of the $n$-cube, $a^2$). For an $n$-cube we should then see a pattern of integers $i = 0,1,2,3,\dots, n$ each occurring $2^{n}{n\choose i}$ times. This corresponds with the $0$s for all the self-pairs, the normalised square of the lengths of all the sides being $\frac{a^2}{a^2}$, and the normalised square of the lengths of all the diagonals being $\frac{2a^2}{a^2}, \frac{3a^2}{a^2},\dots, \frac{na^2}{a^2}$.

Because there are points for which this pattern holds but aren't $n$-cubes. The following is not a square:

$$(1,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,1,1,1)$$

But passes the above test.

So have added a check that all points must also be equidistant from the centre of mass of the points.

Are these now sufficient tests for the vertices of an $n$-cube? Obviously the set of vertices of any given $n$-cube will pass these two tests. But will these two tests also filter out all sets of points that aren't all of the vertices of an $n$-cube?

Answer 1

I wish I knew the answer to the question whether your two conditions are sufficient as it's an interesting one, but I don't have an idea at the moment. Would you be willing to consider an alternative strategy to solve the original problem?

If one of the vectors is the zero vector and if the vectors do form a hypercube, then a unique subset of the vectors will form a spanning set. By spanning set I mean a set such that every vertex is a weighted sum of vectors in the spanning set, with all weights equal either to $0$ or to $1$. A strategy would then be

• identify a vector $v$ in the spanning set;
• check that half of the vectors are orthogonal to $v$ and half are not, and that if $v$ is subtracted from all vectors in the non-orthogonal subset, the result is the orthogonal subset;
• repeat the process on the orthogonal subset, which should be a hypercube of dimension one less;
• stop when the resulting hypercube is zero-dimensional (a single point).

So how do we find a vector $v$ in the spanning set? Identify the vector $z$ with least value in the first coordinate. In the simplest case, there is a unique such vector, and we will assume this initially. Subtract $z$ from all of the vectors. (This means that the set now contains the needed zero vector.) Now the first coordinate of every non-zero vector is positive. The non-zero vector whose first coordinate has the least value must therefore be in the spanning set and we can pick it to be $v$. If more than one non-zero vector has least value in the first coordinate, then all such vectors are in the spanning set and we may select any one of them to be $v$.

What if the original set did not have a unique vector with least first coordinate? In that case, the set of vectors with least first coordinate—call it $V_1$—forms a facet of the hypercube (assuming the points form a hypercube at all). Of those vectors with least first coordinate we then identify those with least second coordinate. Call this set $V_2$. If $V_2$ contains more than one vector, move on to the third coordinate, and so on, until the resulting set $V_r$, which again is a facet of some dimension of the original hypercube, contains a single vector, $z$. Subtract $z$ from all of the original vectors and take $v$ to be the non-zero vector in $V_{r-1}$ (after subtraction of $z$) whose $r^\text{th}$ coordinate has least value.