Related to this is the amusing phenomenon of concentration of measure. Take a ball of dimension d and distribute points uniformly at random by area. Take any patch with an area that is half of the total. A hemisphere is a valid choice. Consider its boundary. If you chose the northern(southern) hemisphere, this would be the equator. Strangely enough almost all points will lie within a distance of O(1/sqrt(d)) from that equator. As d grows this defines an incredibly thin band, but it contains almost all the points.

What it means in terms of programming is that if you are searching for K points (chosen uniformly by someone else), you may as well just search over that thin band and you will find almost all of them there. That ratio can easily be in the high 90s.

To give an intuition to why this happen, note that earth's equator is modestly larger than say a 60^degree north latitude. But as you crank up the dimension d this gap grows exponentially fast. So in comparison to equatorial circles, the other latitudes have almost no space at all, even when almost all of the smaller ones are taken together.