# 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?