# Adaptive Metrics for Adaptive Samples
## 3 Results
The following theorems relate a noisy \(\varepsilon\)-sample to the Hausdorff distance between the sample \(\widehat{X}\) and the set \(X\) and vice versa. Lemma 6: _Consider compact set \(L\) and compact \(X,\widehat{X}\subset\mathbb{R}^{d}\setminus L\). If \(\widehat{X}\) is a noisy \(\varepsilon\)-sample of \(X\) with respect to \(f_{L}\), for \(\varepsilon<1\), then \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\frac{\varepsilon}{1-\varepsilon}\)._  
Proof: Given \(x\in X\), by definition, there exists \(p\in\widehat{X}\) such that \(\|x-p\|\leq\varepsilon f_{L}(x)\). By Lemma 10, \(\mathrm{d}^{L}(x,p)\leq\frac{\varepsilon}{1-\varepsilon}\), so for all, \(x\in X\), \(f^{L}_{X}(x)\leq\frac{\varepsilon}{1-\varepsilon}\). Furthermore, given \(p\in\widehat{X}\), there exists \(x\in X\) such that \(\|x-p\|\leq\varepsilon f_{L}(x)\), so for all \(p\in\widehat{X}\), \(f^{L}_{X}(p)\leq\frac{\varepsilon}{1-\varepsilon}\); thus, \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\frac{\varepsilon}{1-\varepsilon}\). Lemma 7: _Consider compact set \(L\) and sets \(X,\widehat{X}\subset\mathbb{R}^{d}\setminus L\). If \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\varepsilon<\frac{1}{2}\), then \(\widehat{X}\) is a noisy \(\frac{\varepsilon}{1-\varepsilon}\)-sample of \(X\) with respect to \(f_{L}\)._  
Proof: \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\varepsilon\) implies that for all \(p\in\widehat{X}\), \(f^{L}_{X}(p)\leq\varepsilon\). Thus, there exists \(x\in X\) such that \(\mathrm{d}^{L}(x,p)\leq\varepsilon\). By Lemma 10, \(\|x-p\|\leq\frac{\varepsilon}{1-\varepsilon}f_{L}(x)\). Similarly, \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\varepsilon\) implies that for all \(x\in X\), \(f^{L}_{\widehat{X}}(x)\leq\varepsilon\); thus, there exists \(x\in\widehat{X}\) such that \(\mathrm{d}^{L}(x,p)\leq\varepsilon\), and thus, \(\|x-p\|\leq\frac{\varepsilon}{1-\varepsilon}f_{L}(x)\). Since \(\varepsilon<\frac{1}{2}\), then \(\frac{\varepsilon}{1-\varepsilon}<1\), so \(\widehat{X}\) is a noisy \(\frac{\varepsilon}{1-\varepsilon}\)-sample of \(X\). Lemma 8: _Given compact set \(L\subset\mathbb{R}^{d}\) and compact set \(X\subset\mathbb{R}^{d}\setminus L\), for \(\varepsilon<1\), \(A^{L}_{X}(\varepsilon)\subseteq B^{L}_{X}(\frac{\varepsilon}{1-\varepsilon})\)._  
Proof: Take \(y\in A^{L}_{X}(\varepsilon)\) so that \(f^{L}_{X}(y)\leq\varepsilon\). Thus, there exists \(x\in X\) such that \(\mathrm{d}^{L}(x,y)\leq\varepsilon\). By Lemma 10, this implies that \(\|x-y\|\leq\frac{\varepsilon}{1-\varepsilon}f_{L}(x)\), which implies that \(y\in B^{L}_{X}(\frac{\varepsilon}{1-\varepsilon})\). Lemma 9: _Given compact set \(L\subset\mathbb{R}^{d}\) and compact set \(X\subset\mathbb{R}^{d}\setminus L\), for \(\varepsilon<1\), \(B^{L}_{X}(\varepsilon)\subseteq A^{L}_{X}(\frac{\varepsilon}{1-\varepsilon})\)._  
Proof: Consider \(y\in B^{L}_{X}(\varepsilon)\). Thus, \(y\in\mathrm{ball}(x,\varepsilon f_{L}(x))\), for some \(x\in X\), so \(\|x-y\|\leq\varepsilon f_{L}(x)\). Applying Lemma 10, we then have that \(\mathrm{d}^{L}(x,y)\leq\frac{\varepsilon}{1-\varepsilon}\), and as \(f^{L}_{X}(y)\leq\mathrm{d}^{L}(x,y)\), \(y\in A^{L}_{X}(\frac{\varepsilon}{1-\varepsilon})\).