Search

# Curse of Dimensionality

Last updated Sep 23, 2022 Edit Source

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