# Curse of Dimensionality

Volume grows exponentially with dimension

## # Example

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

- In 1D, we need $O(1 / \epsilon)$ points
- In 2D, we need $O(1 / \epsilon^2)$ points
- In DD, we need $O(1 / \epsilon^3)$ points

Our nearest neighbour in high-dimensions might be really really far away