Nearest Neighours and k-d tree

Distances in two dimensions or three dimensions are quite common and we sometimes assumes distances in high dimension are friendly too. So why does a simple model like the k-nearest neighbours seem to have difficulties to predict ?

Problem definition

The first notebooks describes the problem.