Curse of Dimensionality

Volume grows exponentially with dimension. Our nearest neighbour in high-dimensions might be really really far away

If want every location on to have a “neighbor” with distance $ϵ$,

• In 1D, we need $O(1/ϵ)$ points
• In 2D, we need $O(1/{ϵ}^2)$ points
• In DD, we need $O(1/{ϵ}^3)$ points