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?

"Have found out that there are [sets of] points for which this pattern holds but aren't n-cubes." Can you present an example (for the least possible $n$)? — user, May 13 '20 at 08:34
For 2-cube we should have $(4\times0,8\times1,4\times2)$. But in your example the distance between 1st and 4th points is 4, is not it? — user, May 13 '20 at 08:48
@user Have reworded the question, hopefully now all is clear? — Paul Evans, May 13 '20 at 09:44
You are correct. I missed the fact that $a^2$ may be arbitrary. (+1) for very interesting question. — user, May 13 '20 at 09:52
I think it is obviously that the vertices of any $n$-cube will pass the test. The only question is whether the modified test will filter out all false point sets. — user, May 13 '20 at 10:08
given eight vertices, how to verify they form a cube? was closed, but has two useful answers ($n=3$). — Vepir, May 13 '20 at 11:49
@Vepir Thanks, in fact derived the first test from there. Now need a mathematical verification of sufficiency of these two tests. — Paul Evans, May 13 '20 at 12:14

score 1 · Answer 1 · answered May 14 '20 at 18:02

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.

Yes, I'm very interested in alternate solutions. Will try this out - thanks! +1 — Paul Evans, May 14 '20 at 18:46

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

1 Answers1

Linked