# Adaptive Metrics for Adaptive Samples
## 3 Results  
Lemma 3: Consider \(\widehat{X},X\subseteq\mathbb{R}^{d}\setminus L\) to be such that \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\delta\). Then, for all \(\alpha\geq 0\), \(A^{L}_{X}(\alpha)\subseteq A^{L}_{\widehat{X}}(\alpha+\delta)\) and \(A^{L}_{\widehat{X}}(\alpha)\subseteq A^{L}_{X}(\alpha+\delta)\). Proof: Fix \(y\in A^{L}_{X}(\alpha)\). By definition, \(f^{L}_{X}(y)\leq\alpha\), which implies that there exists \(x\in X\) such that \(\mathrm{d}^{L}(x,y)\leq\alpha\). \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\delta\), which implies that for all \(x\in X\), \(f^{L}_{\widehat{X}}(x)\leq\delta\). Now, by Lemma 1, \(f^{L}_{\widehat{X}}(y)\leq f^{L}_{\widehat{X}}(x)+\mathrm{d}^{L}(x,y)\leq\delta+\alpha\), implying \(y\in A^{L}_{\widehat{X}}(\alpha+\delta)\). By a symmetric argument, the other statement holds. Lemma 4 relates the length of a path \(\gamma\) with respect to two distance-to-set functions, assuming they have a close Hausdorff distance with respect to a Euclidean metric. Lemma 4: Let \(L,\widehat{L}\) be two compact sets such that \(\mathrm{d}_{H}(L,\widehat{L})\leq\varepsilon\) for some \(\varepsilon>0\). For all unit-speed, \(\gamma:[0,a]\to\mathbb{R}^{d}\setminus L^{\varepsilon}\), where for some positive \(c\), we have the following inequalities. \[(1-\frac{1}{c})|\gamma|^{\widehat{L}}\leq|\gamma|^{L}\leq(1+\frac{1}{c})| \gamma|^{\widehat{L}}.\]  
Proof: Take an arbitrary unit-speed path \(\gamma:[0,a]\to\mathbb{R}^{d}\setminus L^{\varepsilon}\) where \(\mathrm{d}_{H}(L,\widehat{L})\leq\varepsilon\). Since the image of the path \(\gamma\) is a subset of \(\mathbb{R}^{d}\setminus L^{\varepsilon}\), then for all \(z\in\gamma\), \(f_{L}(z)>c\varepsilon\). By the Hausdorff distance between \(L\) and \(\widehat{L}\), we have \(f_{L}(z)\leq f_{\widehat{L}}(z)+\varepsilon<f_{\widehat{L}}(z)+\frac{f_{L}(z)}{c}\). Likewise, we have that \(f_{L}(z)\geq f_{\widehat{L}}(z)-\varepsilon>f_{\widehat{L}}(z)-\frac{f_{L}(z)}{c}\). Rearranging both of these, we have that \(\frac{1-\frac{1}{\widehat{L}}}{f_{\widehat{L}}(z)}<\frac{1}{f_{L}(z)}<\frac{1+ \frac{1}{\varepsilon}}{f_{\widehat{L}}(z)}\). By the definition of \(|\gamma|^{L}\) and \(|\gamma|^{\widehat{L}}\), these inequalities imply that \((1-\frac{1}{\varepsilon})|\gamma|^{\widehat{L}}\leq|\gamma|^{L}\leq(1+\frac{ 1}{\varepsilon})|\gamma|^{\widehat{L}}\). The following lemma provides a bound on how close to \(L\) a shortest path to a compact set \(X\) can be and a constant \(c\) to satisfy Lemma 4 that is dependent on what compact set \(X\subset\mathbb{R}^{d}\setminus L\) one is working. Lemma 5: _Take compact set \(L\subset\mathbb{R}^{d}\), compact set \(X\subset\mathbb{R}^{d}\setminus L\), and \(y\in A^{L}_{X}(\delta)\), for \(\delta<1\). If \(\gamma\) is the shortest path from \(y\) to \(X\) with respect to \(\mathrm{d}^{L}\), then:_  
\[\gamma\subset\mathbb{R}^{d}\setminus L^{(1-\frac{\delta}{1-\delta})\mathrm{d }_{H}(X,L)}\]  
Proof: Since \(y\in A^{L}_{X}(\delta)\), \(f^{L}_{X}(y)\leq\delta\), so there exists \(x\in X\) such that \(\mathrm{d}^{L}(x,y)\leq\delta\). Take \(\gamma\) as the shortest path from \(y\) to \(X\). For all \(z\in\gamma\), \(\mathrm{d}^{L}(x,z)\leq\mathrm{d}^{L}(x,y)\leq\delta\). By Lemma 10, \(\|x-z\|\leq\frac{\delta}{1-\delta}f_{L}(x)\), and by \(f_{L}\) being Lipschitz, we have that \(f_{L}(z)\geq f_{L}(x)-\|x-z\|\geq(1-\frac{\delta}{1-\delta})f_{L}(x)\geq(1- \frac{\delta}{1-\delta})\mathrm{d}_{H}(X,L)\). This means that every point on the path \(\gamma\) is at least distance \((1-\frac{\delta}{1-\delta})\mathrm{d}_{H}(X,L)\) away from \(L\). We define a noisy \(\varepsilon\)-sample, for \(\varepsilon<1\), of compact \(X\subseteq\mathbb{R}^{d}\setminus L\) with respect to \(f_{L}\) for some compact set \(L\) as a compact set \(\widehat{X}\subseteq\mathbb{R}^{d}\setminus L\) such that for all \(x\in X\), there exists \(p\in\widehat{X}\) such that \(\|x-p\|\leq\varepsilon f_{L}(x)\). Likewise, for all \(p\in\widehat{X}\), there exists \(x\in X\), such that \(\|x-p\|\leq\varepsilon f_{L}(x)\).