The current Wikipedia entry on the curse of dimensionality describes the problem well with respect to having enough data for a problem, and also with respect to distance functions. I’m copying these entries here, in case they change or disappear later. Sampling There is an exponential increase in volume associated with adding extra dimensions to a mathematical space. For example, \(10^2=100\) evenly spaced sample points suffice to sample a unit interval (a “1-dimensional cube”) with no more than \(10^{−2}=0.