Skip to main content
2 of 3
edited tags; edited tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

$\epsilon$-net under Hausdorff distance

Consider linear subspaces of $\mathbb{R}^n$. For two subspaces $X$ and $Y$, we define their Hausdorff distance as $$ {\displaystyle d_{\mathrm {H} }(X,Y)=\max \left\{\,\sup _{x\in X, |x|_2=1}\inf _{y\in Y,|y|_2=1}d(x,y),\,\sup _{y\in Y,|y|_2=1}\inf _{x\in X, |x|_2=1}d(x,y)\,\right\}.\!} $$

For $\epsilon>0$, the set of subspaces $X_1,\dots,X_m$ is called an $\epsilon$-net under Hausdorff distance if for any subspace $Y$, there is some $X_i$ such that $$ d_{\mathrm {H} }(X_i,Y)<\epsilon. $$ The questions is to provide upper and lower bound of $m$.

gondolf
  • 1.5k
  • 9
  • 15