# Adaptive Metrics for Adaptive Samples
## 2 Methods  
Let \(L\) and \(X\) be compact subsets of \(\mathbb{R}^{d}\) with respect to the Euclidean metric. For \(x,y\in\mathbb{R}^{d}\), define \(\mathrm{Path}(x,y)\) to be the set of bounded piecewise-\(C_{1}\) paths from \(x\) to \(y\), parametrized by the Euclidean arc-length. Similarly, \(\mathrm{Path}(x,S):=\bigcup\limits_{s\in S}\mathrm{Path}(x,s)\) denotes all paths from \(x\) to a set \(S\). For any compact set \(L\subseteq\mathbb{R}^{d}\), define \(f_{L}(\cdot):\mathbb{R}^{d}\to\mathbb{R}\) by:  
\[f_{L}(x):=\min\limits_{\ell\in L}\|x-\ell\|.\]  
Define:  
\[\mathrm{d}^{L}(x,y):=\min\limits_{\gamma\in\mathrm{Path}(x,y)}\int_{\gamma} \frac{dz}{f_{L}(z)}.\]  
The length of a unit-speed path \(\gamma:[0,a]\to\mathbb{R}^{d}\) is denoted as:  
\[|\gamma|:=\int_{\gamma}dz=\int_{0}^{a}dt.\]  
For \(y\in\mathbb{R}^{d}\), define:  
\[f_{X}^{L}(y):=d^{L}(y,X)=\min\limits_{x\in X}\mathrm{d}^{L}(y,x),\]  
and:  
\[\widehat{f_{X}^{L}}(y):=\min\limits_{x\in X}\frac{\|y-x\|}{f_{L}(x)}.\]  
Note that \(f_{X}^{L}(\cdot)\) is a distance function, while \(\widehat{f_{X}^{L}}(\cdot)\) is not. The latter function can be interpreted as a first-order approximation of the former. Definition 1: For any compact set \(X\subset\mathbb{R}^{d}\setminus L\), for some compact set \(L\subset\mathbb{R}^{d}\), the \(\alpha\)-offsets with respect to \(\mathrm{d}^{L}\) are:  
\[A_{X}^{L}(\alpha):=\{x\in\mathbb{R}^{d}\mid f_{X}^{L}(x)\leq\alpha\}.\]  
The distance function \(f_{L}(\cdot)\) can be transformed into an arbitrarily close smooth function \(\tilde{f}_{L}(\cdot)\)[18], yielding a Riemannian metric \(\tilde{\mathrm{d}}_{L}\) defined in an identical manner as \(\mathrm{d}_{L}\). From this, one has corresponding \(\alpha\)-offsets \(\tilde{A}_{X}^{L}(\alpha)\) that are arbitrarily close to \(A_{L}^{X}(\alpha)\). We will encounter this smoother version in Section 3.3. We will approximate the offsets \(A_{X}^{L}(\alpha)\) by a union of balls as follows. Definition 2: For any compact set \(X\subset\mathbb{R}^{d}\setminus L\), for some compact set \(L\subset\mathbb{R}^{d}\), the approximate \(\alpha\)-offsets with respect to \(\mathrm{d}^{L}\) are:  
\[B_{X}^{L}(\alpha):=(\widehat{f_{X}^{L}})^{-1}[0,\alpha]=\bigcup\limits_{x \in X}\mathrm{ball}(x,\alpha f_{L}(x)).\]  
A useful property of \(f_{X}^{L}(\cdot)\) is that it is a one-Lipschitz function. In general, a function \(f\) between two metric spaces \((X,\mathrm{d}_{X})\) and \((Y,\mathrm{d}_{Y})\) is said to be \(k\)-Lipschitz if for all \(x,y\in X\), \(\mathrm{d}_{Y}(f(x),f(y))\leq k\mathrm{d}_{X}(x,y)\). Lemma 1: _The function \(f_{X}^{L}\) is one-Lipschitz from the metric space \((\mathbb{R}^{d},\mathrm{d}^{L})\) to \(\mathbb{R}\)._  
Proof: Fix any \(a,b\in\mathbb{R}^{d}\). There exists point \(x\in X\) and a path \(\gamma_{1}\in\mathrm{Path}(a,x)\) such that \(f_{X}^{L}(a)=\int_{\gamma_{1}}\frac{dz}{f_{L}(z)}\). Likewise, there exists \(\gamma_{2}\in\mathrm{Path}(a,b)\) such that \(\mathrm{d}^{L}(a,b)=\int_{\gamma_{2}}\frac{dz}{f_{L}(z)}\). This implies that the concatenation of \(\gamma_{1}\) and \(\gamma_{2}\) is a path \(\gamma_{3}\) in \(\mathrm{Path}(b,X)\). Thus, \(f^{L}_{X}(b)\leq\int_{\gamma_{3}}\frac{dz}{f_{L}(z)}\leq f^{L}_{X}(a)+\mathrm{d }^{L}(a,b)\). As this holds for all \(a,b\), we conclude that \(|f^{L}_{X}(a)-f^{X}_{L}(b)|\leq\mathrm{d}^{L}(a,b)\), as desired. We can use \(f^{L}_{X}\) to define the Hausdorff distance, which is a metric between compact sets. This metric is useful for stating bounds on the quality, or uniformity, of a sample near a set. Definition 3: The Hausdorff distance between two compact sets \(X,Y\in(\mathbb{R}^{d},\mathrm{d}^{L})\) is defined as:  
\[\mathrm{d}^{L}_{H}(X,Y)=\max\{\max_{x\in X}f^{L}_{Y}(x),\max_{y\in Y}f^{L}_{X}( y)\}\]  
If the Hausdorff distance between a compact set and a sample is bounded, Lemma 3 shows that their \(\alpha\)-offsets are interleaved at particular scales. Lemma 2: Let \(\widehat{X},X\subseteq\mathbb{R}^{d}\setminus L\) be such that \(\mathrm{d}^{L}_{H}(\widehat{X},X)\leq\delta\).