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


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(nlog(n))$

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