2
$\begingroup$

Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.

In the 2-dimensional case it's fairly trivial, you simply split the square along its diagonals:

if (x < y) then
    if (x + y < 0) then
        // Side 1
    else
        // Side 2
else
    if (x + y < 0) then
        // Side 3
    else
        // Side 4

In 3-dimensions, this becomes more complex; each face creates a 'volume' of points that are closest to it in the shape of a square based pyramid.

Visualisation of the 6 planes that form the 6 pyramids

Of course, given a point, it's possible to determine which side of the 6 planes it lands on and using that information you can determine which face of the cube is closest. However this would involve running 6 separate checks.

Moving this into higher dimensions, a similar algorithm can be run on hypercubes, however, as the number of faces on a n-cube is $2^{n-2}{n \choose 2}$, this quickly becomes computationally very expensive.

However, theoretically a perfect algorithm could cut the search space in half with every check, discarding half the faces each time.

This would give this hypothetical algorithm a runtime of $O(\log_2(2^{n-2}{n \choose 2}))$ which can be simplified, if my rate of growth calculations worked out, to $O(n\log(n))$

Is my logic correct here; can/does such an algorithm exist?

$\endgroup$
  • 1
    $\begingroup$ Am I missing something, or $O(\log(2^{n-2} {{n}\choose{2}}))$ actually simplifies even to $O(n + \log(n))$, which is simply $O(n)$? $\endgroup$ – Vladislav Bezhentsev May 23 at 22:39
  • $\begingroup$ By the way, are you talking about 2-dimensional faces? $\endgroup$ – Vladislav Bezhentsev May 23 at 22:51
  • $\begingroup$ Yes, the OP is asking about 2-faces, according to the formula for their number $\endgroup$ – HEKTO May 26 at 20:13
1
$\begingroup$

After a bit more thinking, I realised it's actually doable in $O(n)$

If you normalise your hypercube onto the origin then to find the face the point lies on you simply need to find the axis of the point with the largest magnitude.

So, if the point is at $(0.2, 0.4, 0.7, 0.5)$, the point will be closest to the face facing in the positive z direction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What does it mean "to face in the positive z direction" in spaces with dimension greater than 3? Can you explicitly specify the closest 2-dim face for your example by enumerating at least 3 of its vertices? $\endgroup$ – Vladislav Bezhentsev May 23 at 22:54
  • $\begingroup$ This self-answer looks, let's say, insufficient... On the contrary, the idea with binary search looks right - the only problem it's only an idea, it's still unclear how you'll get the right face in the end of this search $\endgroup$ – HEKTO May 26 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.