# Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(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(n\log(n))$$

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

• 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)$? – Vladislav Bezhentsev May 23 at 22:39
• By the way, are you talking about 2-dimensional faces? – Vladislav Bezhentsev May 23 at 22:51
• Yes, the OP is asking about 2-faces, according to the formula for their number – HEKTO May 26 at 20:13

After a bit more thinking, I realised it's actually doable in $$O(n)$$
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.