# Adaptive Metrics for Adaptive Samples
## 3 Results
### Adaptive Sampling  
In this section, we prove that a uniform sample in the induced metric corresponds to an adaptive sample in the Euclidean metric and vice versa. The key to this proof is the following lemma, which will also be used for the more elaborate interleaving results of Section 3.2.  
**Lemma 10**.: _Let \(L\subset\mathbb{R}^{d}\) be a compact set, and let \(a,b\in\mathbb{R}^{d}\setminus L\). Then, the following two statements hold for all \(\delta\in[0,1)\)._  
_(i)_ _If_ \(\mathrm{d}^{L}(a,b)\leq\delta\)_, then_ \(\frac{\|a-b\|}{f_{L}(a)}\leq\frac{\delta}{1-\delta}\)_._  
_(ii)_ _If_ \(\frac{\|a-b\|}{f_{L}(a)}\leq\delta\)_, then_ \(\mathrm{d}^{L}(a,b)\leq\frac{\delta}{1-\delta}\)_._  
Proof.: To prove (i), we assume \(\mathrm{d}^{L}(a,b)\leq\delta\). Let \(\gamma\) be the path in \(\mathrm{Path}(a,b)\) such that \(\mathrm{d}^{L}(a,b)=\int_{\gamma}\frac{dz}{f_{L}(z)}<\delta\). Then, we have the following inequalities following from the Lipschitz property of \(f_{L}\).  
\[|\gamma|=\int_{\gamma}dz =(f_{L}(a)+|\gamma|)\int_{\gamma}\frac{dz}{f_{L}(a)+|\gamma|}\] \[\leq(f_{L}(a)+|\gamma|)\int_{\gamma}\frac{dz}{f_{L}(z)}\] \[\leq(f_{L}(x)+|\gamma|)\delta\]  
It follows that \(|\gamma|\leq\frac{\delta}{1-\delta}f_{L}(x)\). Because \(\|a-b\|\) is the length of the shortest path between \(a\) and \(b\) in the Euclidean metric, we conclude that \(\|a-b\|\leq|\gamma|\leq\frac{\delta}{1-\delta}f_{L}(x)\).  
Next we prove (ii). Assume \(\frac{\|a-b\|}{f_{L}(a)}\leq\delta\). For all points \(z\) in the straight line segment \(\overline{ab}\),  
\[f_{L}(z)\geq f_{L}(a)-\|a-z\|\geq f_{L}(a)-\|a-b\|\geq(1-\delta)f_{L}(a).\]  
This implies the following inequality.  
\[\mathrm{d}^{L}(a,b) =\inf_{\gamma\in\mathrm{Path}(a,b)}\int_{\gamma}\frac{dz}{f_{L}( z)}\] \[\leq\int_{\overline{ab}}\frac{dz}{f_{L}(z)}\] \[\leq\frac{1}{(1-\delta)f_{L}(a)}\int_{\overline{ab}}dz\] \[=\frac{\|a-b\|}{(1-\delta)f_{L}(a)}\] \[\leq\frac{\delta}{1-\delta}.\]  
We can now state the main theorem relating adaptive samples in the Euclidean metric to uniform samples in the metric induced by a set \(L\).  
**Theorem 1**.: _Let \(L\) and \(X\) be compact sets; let \(\widehat{X}\subset X\) be a sample; and let \(\varepsilon\in[0,1)\) be a constant. If \(\widehat{X}\) is an \(\varepsilon\)-sample of \(X\) with respect to the distance to \(L\), then \(\mathrm{d}^{L}_{H}(X,\widehat{X})\leq\frac{\varepsilon}{1-\varepsilon}\). Furthermore, if \(\mathrm{d}^{L}_{H}(X,\widehat{X})\leq\varepsilon<\frac{1}{2}\), then \(\widehat{X}\) is an \(\frac{\varepsilon}{1-\varepsilon}\)-sample of \(X\) with respect to the distance to \(L\)._  
Proof.: Given \(x\in X\), 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}_{\widehat{X}}(x)\leq\frac{\varepsilon}{1-\varepsilon}\). As \(\widehat{X}\subseteq X\), this proves \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\frac{\varepsilon}{1-\varepsilon}\).  
Furthermore, \(\mathrm{d}_{H}^{L}(\widehat{X},X)\leq\varepsilon<\frac{1}{2}\) implies that for all \(x\in X\), \(f_{\widehat{X}}^{L}(x)\leq\varepsilon\); thus, there exists \(p\in\widehat{X}\) such that \(\mathrm{d}^{L}(x,p)\leq\varepsilon\). Thus, by Lemma 10\(\|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 an \(\frac{\varepsilon}{1-\varepsilon}\)-sample of \(X\).