Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Question

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?

Answer 1

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.