I understand how the curse of high dimensionality works when most features are irrelevant in this highly cited article: A Few Useful Things to Know About Machine Learning, but I get stuck in reading the following illustration:
This is because in high dimensions all examples look alike. Suppose, for instance, that examples are laid out on a regular grid, and consider a test example $x_t$. If the grid is d-dimensional, $x_t$’s 2d nearest examples are all at the same distance from it. So as the dimensionality increases, more and more examples become nearest neighbors of $x_t$, until the choice of nearest neighbor (and therefore of class) is effectively random
The first sentence is unintuitive. Especially, why If the grid is d-dimensional, $x_t$’s 2d nearest examples are all at the same distance from it?
To make it concrete, there are two coordinates(A and B) in a 2d plane:
Suppose that (0, 0) is the test example, and we can see that A is closer to it than B. I wonder if B would be as close to the test example as A in any higher dimensional space? If so, how? If not, how would all samples look alike?