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?