# Adaptive Metrics for Adaptive Samples
## 1 Introduction
### From Surface Reconstruction to Homology Inference  
To reconstruct a surface from a point set, one needs the sample to be sufficiently dense with respect to not just the local curvature of the surface, but also the distance to parts of the surface that are close in the embedding, but far in geodesic distance. Otherwise, algorithms have no way of identifying which geometrically close sample points correspond to local neighborhoods in the surface. Adaptive sampling with respect to the so-called local feature size as introduced by [PERSON] and [PERSON] [5] neatly characterizes such \"good\" samples and was then used in many later works on surface reconstruction with topological guarantees [6]. There is an extensive literature on the problem in high dimensions (see [7, 8] for recent examples), and the problem remains an active research area. Such adaptive samples are in contrast to uniform samples for which a single parameter determines the density. That parameter is usually driven by the minimum of the local feature size and results in a much larger sample.  
Later work on generalizations of surface reconstruction and homology inference related the topology of unions of balls centered at a sample \(\widehat{X}\) near the unknown set \(X\) to the topology of \(X\) itself. The most well-known such results were by [PERSON] et al. [9, 10]. A union of balls with a fixed radius can be viewed as a sublevel set of the distance function to \(\widehat{X}\). If we have an adaptive sample, then we would like to scale the radii of the balls as well. However, if the sample is adaptive with respect to a local feature size defined as the distance to an unknown set \(L\), another approximation \(\widehat{L}\) near \(L\) is necessary. Indeed, one interpretation of some Voronoi-based surface reconstruction algorithms is that an approximation \(\widehat{L}\) to the medial axis \(L\) is computed from the Voronoi diagram of the sample \(\widehat{X}\) of the unknown surface \(X\).  
We present a new perspective on adaptive samples. For any pair of disjoint, compact sets \(X\) and \(L\), we define a metric on \(\mathbb{R}^{d}\setminus L\) with the property that a uniform sample of \(X\) in the new metric corresponds to an adaptive sample in the Euclidean metric. We call this the metric induced by \(L\) or simply the induced metric. This new metric can also be extended to an arbitrarily close Riemannian metric over the same domain. Our main motivation is to connect adaptive sampling theory to the critical point theory of distance functions used extensively to prove topological guarantees in topological data analysis [2, 11, 12]. That theory gives natural topological equivalences between sublevel sets of distance functions to compact sets in Riemannian metrics. Thus, we propose to use the induced metric as the underlying ideal object and then relate it to a union of Euclidean balls constructed from approximations of \(X\) and \(L\). Our metric can be viewed as a smoothed version of a metric used by [PERSON] [13]. Our new formulation reveals connections with work on path planning [14, 15] and density-based distances [16, 17]. These are all constructions where one looks at conformal change of metrics induced by subsets of Euclidean space.