Adaptive Metrics for Adaptive Samples

Abstract

We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological inference results and to prove topological guarantees using the critical points theory of distance functions. This ultimately leads to an algorithm for homology inference from samples whose spacing depends on their distance to a discrete representation of the complement space.

1. Introduction

1.1. From Points to Topology

Both surface reconstruction and homology inference are algorithmic problems that take points as input and produce a topological representation of the underlying space from which the points were drawn. In surface reconstruction, one often wants a homeomorphic reconstruction in the form of a triangulation, whereas in homology inference, it suffices to compute the homology groups. Although similar in many respects, the general trend is that with weaker conditions on the input (i.e., noisier samples), one can only hope for weaker guarantees on the output (homology rather than homeomorphism). There is one aspect of these theories that directly contradicts this trend: many surface reconstruction algorithms are able to work with an adaptive sample, while most homology inference algorithms require a uniform sample. Here and throughout, we use “uniform” in the Hausdorff sense, not the statistical sense. An adaptive sample has a density that adapts to some local sizing function. Thus, areas that require higher fidelity will have higher density (and a smaller scale), while areas that can get by with less fidelity will have lower density (and larger scale).

There have been some notable works that have bridged this gap between surface reconstruction and homology inference for adaptive samples. Most theoretically guaranteed surface reconstruction algorithms assume an input that is sufficiently dense with respect to the distance to the medial axis, a kind of skeleton describing the complement of the underlying shape. Cazals et al. [1] introduced the conformal alpha shape filtration as a way to build triangulations at different scales that have local connectivity related to the local feature size. Although their stated goal was surface reconstruction, the work employed many of the methods of homology inference. Chazal and Lieutier [2,3] gave a more direct generalization of methods in surface reconstruction with adaptive samples to homology inference, achieving some guarantees for smooth manifolds assuming both upper and lower bounds on the density. Dey et al. [4] gave a homology inference algorithm for manifold data that attempts to sample a subset of the medial axis in order to approximate the local feature size. This work was the main motivation for the current paper, and we adopted their notation of X for the space and L for the approximation to the complement space. We extend these works by providing guaranteed homology inference for a much more general class of samples and spaces; we do not require the space to be a manifold or the sample to adapt to the medial axis.

1.2. 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 Amenta and Bern [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 Niyogi 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\backslash 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 Clarkson [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.

1.3. Overview

We lay out the main objects of study in Section 2. This includes the induced metric and a discrete approximation. Throughout the paper, we will relate these two objects or variations thereof for different purposes. In Section 3.1, we prove the relationship between the adaptive samples used in surface reconstruction and uniform samples in the induced metric. The definition of the induced metric does not lend itself to direct computation. Therefore, in Section 3.2, we bound the interleaving distance between the induced metric and its discrete approximation. This interleaving is then used in Section 3.3 to give a homology inference algorithm that is guaranteed to recover the homology of a sublevel set of the induced metric under certain sampling conditions.

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):={\displaystyle \bigcup _{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(·):{\mathbb{R}}^d\to \mathbb{R}$ by:

$$f_L(x):=\underset{\ell \in L}{min}\Vert x-\ell \Vert .$$

Define:

$${\mathrm{d}}^L(x,y):=\underset{\gamma \in \mathrm{Path}(x,y)}{min}{\int }_{\gamma }\frac{dz}{f_L(z)}.$$

The length of a unit-speed path $\gamma :[0,a]\to {\mathbb{R}}^d$ is denoted as:

$$\left|\gamma \right|:={\int }_{\gamma }dz={\int }_0^{a}dt.$$

For $y\in {\mathbb{R}}^d$, define:

$$f_X^L(y):=d^L(y,X)=\underset{x\in X}{min}{\mathrm{d}}^L(y,x),$$

and:

$$\widehat{f_X^L}(y):=\underset{x\in X}{min}\frac{\Vert y-x\Vert }{f_L(x)}.$$

Note that $f_X^L(·)$ is a distance function, while $\widehat{f_X^L}(·)$ 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\backslash L$, for some compact set $L\subset {\mathbb{R}}^d$, the α-offsets with respect to ${\mathrm{d}}^L$ are:

$$A_X^L(\alpha ):=\{x\in {\mathbb{R}}^d|f_X^L(x)\le \alpha \}.$$

The distance function $f_L(·)$ can be transformed into an arbitrarily close smooth function ${\tilde{f}}_L(·)$ [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\backslash L$, for some compact set $L\subset {\mathbb{R}}^d$, the approximate α-offsets with respect to ${\mathrm{d}}^L$ are:

$$B_X^L(\alpha ):={(\widehat{f_X^L})}^{-1}[0,\alpha ]=\bigcup _{x\in X}\mathrm{ball}(x,\alpha f_L(x)).$$

A useful property of $f_X^L(·)$ 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))\le 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_X^L(b)\le {\int }_{{\gamma }_3}\frac{dz}{f_L(z)}\le f_X^L(a)+{\mathrm{d}}^L(a,b)$. As this holds for all $a,b$, we conclude that $|f_X^L(a)-f_L^X(b)|\le {\mathrm{d}}^L(a,b)$, as desired. □

We can use $f_X^L$ 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}}_H^L(X,Y)=max\{\underset{x\in X}{max}{f}_Y^L(x),\underset{y\in Y}{max}{f}_X^L(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\backslash L$ be such that ${\mathrm{d}}_H^L(\widehat{X},X)\le \delta$. Then, for all $\alpha \ge 0$, $A_X^L(\alpha )\subseteq A_{\widehat{X}}^L(\alpha +\delta )$ and $A_{\widehat{X}}^L(\alpha )\subseteq A_X^L(\alpha +\delta )$.

Proof. 

Let $y\in A_X^L(\alpha )$ be any point. By the definition of $A_X^L$, we have $f_X^L(y)\le \alpha$. Therefore, there exists $x\in X$ such that ${\mathrm{d}}^L(x,y)\le \alpha$. The Hausdorff assumption that ${\mathrm{d}}_H^L(\widehat{X},X)\le \delta$ implies that for all $x\in X$, we have $f_{\widehat{X}}^L(x)\le \delta$. By Lemma 1, $f_{\widehat{X}}^L(y)\le f_{\widehat{X}}^L(x)+{\mathrm{d}}^L(x,y)\le \delta +\alpha$, implying $y\in A_{\widehat{X}}^L(\alpha +\delta )$. The second inclusion is proven by a symmetric argument.  □

The following is the definition of an adaptive sample we will use throughout. For the special case when X is a manifold and L is its medial axis, it corresponds to the $\epsilon$-sample used in surface reconstruction.

Definition 4.

Given a compact set $L\subset {\mathbb{R}}^d$ and compact sets $X,\widehat{X}\subset {\mathbb{R}}^d\backslash L$ such that $\widehat{X}\subseteq X$, we say that $\widehat{X}$ is an ε-sample of X, for $\epsilon \in [0,1)$, if for all $x\in X$, there exists $p\in \widehat{X}$ such that $\Vert x-p\Vert \le \epsilon f_L(x)$.

This definition is closely related to that of the approximate $\alpha$-offsets, because if $\widehat{X}$ is an $\epsilon$-sample of X, then for all $x\in X$, $\mathrm{ball}(x,\epsilon f_L(x))\cap \widehat{X}\ne \varnothing$.

3. Results

Lemma 3.

Consider $\widehat{X},X\subseteq {\mathbb{R}}^d\backslash L$ to be such that ${\mathrm{d}}_H^L(\widehat{X},X)\le \delta$. Then, for all $\alpha \ge 0$, $A_X^L(\alpha )\subseteq A_{\widehat{X}}^L(\alpha +\delta )$ and $A_{\widehat{X}}^L(\alpha )\subseteq A_X^L(\alpha +\delta )$.

Proof. 

Fix $y\in A_X^L(\alpha )$. By definition, $f_X^L(y)\le \alpha$, which implies that there exists $x\in X$ such that ${\mathrm{d}}^L(x,y)\le \alpha$. ${\mathrm{d}}_H^L(\widehat{X},X)\le \delta$, which implies that for all $x\in X$, $f_{\widehat{X}}^L(x)\le \delta$. Now, by Lemma 1, $f_{\widehat{X}}^L(y)\le f_{\widehat{X}}^L(x)+{\mathrm{d}}^L(x,y)\le \delta +\alpha$, implying $y\in A_{\widehat{X}}^L(\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})\le \epsilon$ for some $\epsilon >0$. For all unit-speed, $\gamma :[0,a]\to {\mathbb{R}}^d\backslash L^{c\epsilon }$, where for some positive c, we have the following inequalities.

$$(1-\frac{1}{c}){\left|\gamma \right|}^{\widehat{L}}\le {\left|\gamma \right|}^L\le (1+\frac{1}{c}){\left|\gamma \right|}^{\widehat{L}}.$$

Proof. 

Take an arbitrary unit-speed path $\gamma :[0,a]\to {\mathbb{R}}^d\backslash L^{c\epsilon }$ where ${\mathrm{d}}_H(L,\widehat{L})\le \epsilon$. Since the image of the path $\gamma$ is a subset of ${\mathbb{R}}^d\backslash L^{c\epsilon }$, then for all $z\in \gamma$, $f_L(z)>c\epsilon$. By the Hausdorff distance between L and $\widehat{L}$, we have $f_L(z)\le f_{\widehat{L}}(z)+\epsilon <f_{\widehat{L}}(z)+\frac{f_L(z)}{c}$. Likewise, we have that $f_L(z)\ge f_{\widehat{L}}(z)-\epsilon >f_{\widehat{L}}(z)-\frac{f_L(z)}{c}$. Rearranging both of these, we have that $\frac{1-\frac{1}{c}}{f_{\widehat{L}}(z)}<\frac{1}{f_L(z)}<\frac{1+\frac{1}{c}}{f_{\widehat{L}}(z)}$.

By the definition of ${\left|\gamma \right|}^L$ and ${\left|\gamma \right|}^{\widehat{L}}$, these inequalities imply that $(1-\frac{1}{c}){\left|\gamma \right|}^{\widehat{L}}\le {\left|\gamma \right|}^L\le (1+\frac{1}{c}){\left|\gamma \right|}^{\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\backslash L$ one is working.

Lemma 5.

Take compact set $L\subset {\mathbb{R}}^d$, compact set $X\subset {\mathbb{R}}^d\backslash L$, and $y\in A_X^L(\delta )$, for $\delta <1$. If γ is the shortest path from y to X with respect to ${\mathrm{d}}^L$, then:

$$\gamma \subset {\mathbb{R}}^d\backslash L^{(1-\frac{\delta }{1-\delta }){\mathrm{d}}_H(X,L)}$$

Proof. 

Since $y\in A_X^L(\delta )$, $f_X^L(y)\le \delta$, so there exists $x\in X$ such that ${\mathrm{d}}^L(x,y)\le \delta$. Take $\gamma$ as the shortest path from y to X. For all $z\in \gamma$, ${\mathrm{d}}^L(x,z)\le {\mathrm{d}}^L(x,y)\le \delta$.

By Lemma 10, $\Vert x-z\Vert \le \frac{\delta }{1-\delta }{f}_L(x)$, and by $f_L$ being Lipschitz, we have that $f_L(z)\ge f_L(x)-\Vert x-z\Vert \ge (1-\frac{\delta }{1-\delta })f_L(x)\ge (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 $\epsilon$-sample, for $\epsilon <1$, of compact $X\subseteq {\mathbb{R}}^d\backslash L$ with respect to $f_L$ for some compact set L as a compact set $\widehat{X}\subseteq {\mathbb{R}}^d\backslash L$ such that for all $x\in X$, there exists $p\in \widehat{X}$ such that $\Vert x-p\Vert \le \epsilon f_L(x)$. Likewise, for all $p\in \widehat{X}$, there exists $x\in X$, such that $\Vert x-p\Vert \le \epsilon f_L(x)$. The following theorems relate a noisy $\epsilon$-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\backslash L$. If $\widehat{X}$ is a noisy ε-sample of X with respect to $f_L$, for $\epsilon <1$, then ${\mathrm{d}}_H^L(\widehat{X},X)\le \frac{\epsilon }{1-\epsilon }$.

Proof. 

Given $x\in X$, by definition, there exists $p\in \widehat{X}$ such that $\Vert x-p\Vert \le \epsilon f_L(x)$. By Lemma 10, ${\mathrm{d}}^L(x,p)\le \frac{\epsilon }{1-\epsilon }$, so for all, $x\in X$, $f_{\widehat{X}}^L(x)\le \frac{\epsilon }{1-\epsilon }$.

Furthermore, given $p\in \widehat{X}$, there exists $x\in X$ such that $\Vert x-p\Vert \le \epsilon f_L(x)$, so for all $p\in \widehat{X}$, $f_X^L(p)\le \frac{\epsilon }{1-\epsilon }$; thus, ${\mathrm{d}}_H^L(\widehat{X},X)\le \frac{\epsilon }{1-\epsilon }$. □

Lemma 7.

Consider compact set L and sets $X,\widehat{X}\subset {\mathbb{R}}^d\backslash L$. If ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon <\frac{1}{2}$, then $\widehat{X}$ is a noisy $\frac{\epsilon }{1-\epsilon }$-sample of X with respect to $f_L$.

Proof. 

${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon$ implies that for all $p\in \widehat{X}$, $f_X^L(p)\le \epsilon$. Thus, there exists $x\in X$ such that ${\mathrm{d}}^L(x,p)\le \epsilon$. By Lemma 10, $\Vert x-p\Vert \le \frac{\epsilon }{1-\epsilon }{f}_L(x)$.

Similarly, ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon$ implies that for all $x\in X$, $f_{\widehat{X}}^L(x)\le \epsilon$; thus, there exists $x\in \widehat{X}$ such that ${\mathrm{d}}^L(x,p)\le \epsilon$, and thus, $\Vert x-p\Vert \le \frac{\epsilon }{1-\epsilon }{f}_L(x)$. Since $\epsilon <\frac{1}{2}$, then $\frac{\epsilon }{1-\epsilon }<1$, so $\widehat{X}$ is a noisy $\frac{\epsilon }{1-\epsilon }$-sample of X. □

Lemma 8.

Given compact set $L\subset {\mathbb{R}}^d$ and compact set $X\subset {\mathbb{R}}^d\backslash L$, for $\epsilon <1$, $A_X^L(\epsilon )\subseteq B_X^L(\frac{\epsilon }{1-\epsilon })$.

Proof. 

Take $y\in A_X^L(\epsilon )$ so that $f_X^L(y)\le \epsilon$. Thus, there exists $x\in X$ such that ${\mathrm{d}}^L(x,y)\le \epsilon$. By Lemma 10, this implies that $\Vert x-y\Vert \le \frac{\epsilon }{1-\epsilon }{f}_L(x)$, which implies that $y\in B_X^L(\frac{\epsilon }{1-\epsilon })$. □

Lemma 9.

Given compact set $L\subset {\mathbb{R}}^d$ and compact set $X\subset {\mathbb{R}}^d\backslash L$, for $\epsilon <1$, $B_X^L(\epsilon )\subseteq A_X^L(\frac{\epsilon }{1-\epsilon })$.

Proof. 

Consider $y\in B_X^L(\epsilon )$. Thus, $y\in \mathrm{ball}(x,\epsilon f_L(x))$, for some $x\in X$, so $\Vert x-y\Vert \le \epsilon f_L(x)$. Applying Lemma 10, we then have that ${\mathrm{d}}^L(x,y)\le \frac{\epsilon }{1-\epsilon }$, and as $f_X^L(y)\le {\mathrm{d}}^L(x,y)$, $y\in A_X^L(\frac{\epsilon }{1-\epsilon })$. □

3.1. 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\backslash L$. Then, the following two statements hold for all $\delta \in [0,1)$.

(i) 

If ${\mathrm{d}}^L(a,b)\le \delta$, then $\frac{\Vert a-b\Vert }{f_L(a)}\le \frac{\delta }{1-\delta }$.

(ii) 

If $\frac{\Vert a-b\Vert }{f_L(a)}\le \delta$, then ${\mathrm{d}}^L(a,b)\le \frac{\delta }{1-\delta }$.

Proof. 

To prove (i), we assume ${\mathrm{d}}^L(a,b)\le \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$.

$$\begin{array}{cc}\hfill \left|\gamma \right|={\int }_{\gamma }dz& =(f_L(a)+\left|\gamma \right|){\int }_{\gamma }\frac{dz}{f_L(a)+\left|\gamma \right|}\hfill \\ \hfill & \le (f_L(a)+\left|\gamma \right|){\int }_{\gamma }\frac{dz}{f_L(z)}\hfill \\ \hfill & \le (f_L(x)+|\gamma |)\delta \hfill \end{array}$$

It follows that $\left|\gamma \right|\le \frac{\delta }{1-\delta }{f}_L(x)$. Because $\Vert a-b\Vert$ is the length of the shortest path between a and b in the Euclidean metric, we conclude that $\Vert a-b\Vert \le \left|\gamma \right|\le \frac{\delta }{1-\delta }{f}_L(x)$.

Next we prove (ii). Assume $\frac{\Vert a-b\Vert }{f_L(a)}\le \delta$. For all points z in the straight line segment $\overline{ab}$,

$$f_L(z)\ge f_L(a)-\Vert a-z\Vert \ge f_L(a)-\Vert a-b\Vert \ge (1-\delta )f_L(a).$$

This implies the following inequality.

$$\begin{array}{cc}\hfill {\mathrm{d}}^L(a,b)& =\underset{\gamma \in \mathrm{Path}(a,b)}{inf}{\int }_{\gamma }\frac{dz}{f_L(z)}\hfill \\ \hfill & \le {\int }_{\overline{ab}}\frac{dz}{f_L(z)}\hfill \\ \hfill & \le \frac{1}{(1-\delta )f_L(a)}{\int }_{\overline{ab}}dz\hfill \\ \hfill & =\frac{\Vert a-b\Vert }{(1-\delta )f_L(a)}\hfill \\ \hfill & \le \frac{\delta }{1-\delta }.\hfill \end{array}$$

 □

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 $\epsilon \in [0,1)$ be a constant. If $\widehat{X}$ is an ε-sample of X with respect to the distance to L, then ${\mathrm{d}}_H^L(X,\widehat{X})\le \frac{\epsilon }{1-\epsilon }$. Furthermore, if ${\mathrm{d}}_H^L(X,\widehat{X})\le \epsilon <\frac{1}{2}$, then $\widehat{X}$ is an $\frac{\epsilon }{1-\epsilon }$-sample of X with respect to the distance to L.

Proof. 

Given $x\in X$, there exists $p\in \widehat{X}$ such that $\Vert x-p\Vert \le \epsilon f_L(x)$. By Lemma 10, ${\mathrm{d}}^L(x,p)\le \frac{\epsilon }{1-\epsilon }$, so for all $x\in X$, $f_{\widehat{X}}^L(x)\le \frac{\epsilon }{1-\epsilon }$. As $\widehat{X}\subseteq X$, this proves ${\mathrm{d}}_H^L(\widehat{X},X)\le \frac{\epsilon }{1-\epsilon }$.

Furthermore, ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon <\frac{1}{2}$ implies that for all $x\in X$, $f_{\widehat{X}}^L(x)\le \epsilon$; thus, there exists $p\in \widehat{X}$ such that ${\mathrm{d}}^L(x,p)\le \epsilon$. Thus, by Lemma 10 $\Vert x-p\Vert \le \frac{\epsilon }{1-\epsilon }{f}_L(x)$. Since $\epsilon <\frac{1}{2}$, then $\frac{\epsilon }{1-\epsilon }<1$, so $\widehat{X}$ is an $\frac{\epsilon }{1-\epsilon }$-sample of X. □

3.2. Interleaving

A filtration is a nested family of sets. In this paper, we consider filtrations F parameterized by a real number $\alpha \ge 0$ so that $F(\alpha )\subset {\mathbb{R}}^d$, and whenever $\alpha <\beta$, we have $F(\alpha )\subseteq F(\beta )$. Often, our filtrations are sublevel filtrations of a real valued function $f:{\mathbb{R}}^d\to \mathbb{R}$. The sublevel filtration F corresponding to the function f is defined as:

$$F(\alpha ):=\{x\in {\mathbb{R}}^d|f(x)\le \alpha \}.$$

Definition 5.

A pair of filtrations $(F,G)$ is $(h_1,h_2)$-interleaved in an interval $(s,t)$ if $F(r)\subseteq G(h_1(r))$ whenever $r,h_1(r)\in (s,t)$ and $G(r)\subseteq F(h_2(r))$ whenever $r,h_2(r)\in (s,t)$. We require that the functions $h_1,h_2$ to be nondecreasing in $(s,t)$.

The following lemma gives us an easy way to combine interleavings.

Lemma 11.

If $(F,G)$ is $(h_1,h_2)$-interleaved in $(s_1,t_1)$ and $(G,H)$ is $(h_3,h_4)$-interleaved in $(s_2,t_2)$, then $(F,H)$ is $(h_3\circ h_1,h_2\circ h_4)$-interleaved in $(s_3,t_3)$, where $s_3=max\{s_1,s_2\}$ and $t_3=min\{t_1,t_2\}$.

Proof. 

If $r,h_3(h_1(r))\in (s_3,t_3)$, then we have $F(r)\subseteq G(h_1(r))\subseteq H(h_3(h_1(r)))$. Similarly, if $r,h_2(h_4(r))\in (s_3,t_3)$, then $H(r)\subseteq G(h_4(r))\subseteq F(h_2(h_4(r)))$. □

3.2.1. Approximating X with $\widehat{X}$

Ultimately, the goal is to relate $A_X^L$, the offsets in the induced metric, to $B_{\widehat{X}}^{\widehat{L}}$, the approximate offsets computed from approximations (or samples) to both X and L. This relationship will be given by an interleaving that is built up from an interleaving for each approximation step. For each of the following lemmas, let $L,\widehat{L}\subset {\mathbb{R}}^d$ and $X,\widehat{X}\subset {\mathbb{R}}^d\backslash (L\cup \widehat{L})$ be compact sets.

Lemma 12.

If ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon$, then $(A_X^L,A_{\widehat{X}}^L)$ are $(h_1,h_1)$-interleaved in $(0,\infty )$, where $h_1(r)=r+\epsilon$.

Proof. 

This lemma is a reinterpretation of Lemma 3 in the interleaving notation. □

3.2.2. Approximating the Induced Metric

It is much easier to use a union of Euclidean balls to model the sublevel sets of the distance function $f_X^L$. Below, we show that this is a reasonable approximation. The following results may also be viewed as a strengthening of the adaptive sampling result of the previous section (Theorem 1).

Lemma 13.

The pair $(A_{\widehat{X}}^L,B_{\widehat{X}}^L)$ is $(h_2,h_2)$-interleaved in $(0,1)$, where $h_2(r)=\frac{r}{1-r}$.

Proof. 

It will suffice to show that for $r\in [0,1)$, $A_{\widehat{X}}^L(r)\subseteq B_{\widehat{X}}^L(\frac{r}{1-r})$, and for $r\in [0,\frac{1}{2})$, $B_{\widehat{X}}^L(r)\subseteq A_{\widehat{X}}^L(\frac{r}{1-r})$.

Take $y\in A_{\widehat{X}}^L(r)$ so that $f_{\widehat{X}}^L(y)\le r$. Thus, there exists $x\in X$ such that ${\mathrm{d}}^L(x,y)\le r$. By Lemma 10, this implies that $\Vert x-y\Vert \le \frac{r}{1-r}{f}_L(x)$, which implies that $y\in B_{\widehat{X}}^L(\frac{r}{1-r})$.

Consider any point $y\in B_{\widehat{X}}^L(r)$. For some $x\in X$, we have $y\in \mathrm{ball}(x,r{f}_L(x))$, so $\Vert x-y\Vert \le r{f}_L(x)$. Applying Lemma 10, we have that ${\mathrm{d}}^L(x,y)\le \frac{r}{1-r}$. Finally, $y\in A_{\widehat{X}}^L(\frac{r}{1-r})$, because $f_{\widehat{X}}^L(y)\le {\mathrm{d}}^L(x,y)$. □

3.2.3. Approximating L with $\widehat{L}$

Usually, the set L is unknown at the start and must be estimated from the input. For example, if L is the medial axis of X, there are several known techniques for approximating L by taking some vertices of the Voronoi diagram [5,6]. We would like to give some sampling conditions that allow us to replace L with an approximation $\widehat{L}$. Interestingly, the sampling conditions for $\widehat{X}$ are dual to those used for $\widehat{L}$: we require ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \epsilon$. In other words, $\widehat{L}$ must be an adaptive sample with respect to the distance to $\widehat{X}$.

Lemma 14.

If ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \delta <1$, then $(B_{\widehat{X}}^L,B_{\widehat{X}}^{\widehat{L}})$ is $(h_3,h_3)$-interleaved in $(0,\infty )$, where $h_3(r)=\frac{r}{1-\delta }$.

Proof. 

Fix any $x\in B_{\widehat{X}}^L(r)$. There is a point $p\in \widehat{X}$ such that $\frac{\Vert x-p\Vert }{f_L(p)}\le r$. Moreover, there is a nearest point $z\in \widehat{L}$ to x such that $f_{\widehat{L}}(p)=\Vert p-z\Vert$. Lemma 10 and the assumption that ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \delta$ together imply that there exists $y\in L$ such that:

$$\Vert y-z\Vert \le \frac{\delta }{1-\delta }{f}_{\widehat{X}}(z).$$

(1)

It then follows from the definitions that:

$$f_{\widehat{X}}(z)=\underset{q\in \widehat{X}}{min}\Vert z-q\Vert \le \Vert z-p\Vert =f_{\widehat{L}}(p).$$

(2)

Therefore, we can bound $f_L(p)$ in terms of $f_{\widehat{L}}(p)$ as follows.

$$\begin{array}{ccc}\hfill f_L(p)& \le \Vert y-p\Vert \hfill & \hfill [y\in L]\\ \hfill & \le \Vert y-z\Vert +\Vert z-p\Vert \hfill & \hfill [\mathrm{triangle} \mathrm{inequality}]\\ \hfill & \le \frac{1}{1-\delta }{f}_{\widehat{L}}(p)\hfill & \hfill \left[\mathrm{by}(1)\mathrm{and}(2)\right]\end{array}$$

Therefore,

$$\begin{array}{cc}\hfill \frac{\Vert x-p\Vert }{f_{\widehat{L}}(p)}& \le \frac{\Vert x-p\Vert }{(1-\delta )f_L(p)}\le \frac{r}{1-\delta }=h_3(r).\hfill \end{array}$$

Therefore, $x\in B_{\widehat{X}}^{\widehat{L}}(h_3(r))$, and so, we conclude that $B_{\widehat{X}}^L(r)\subseteq B_{\widehat{X}}^{\widehat{L}}(h_3(r))$. The proof is symmetric to show that $B_{\widehat{X}}^{\widehat{L}}(r)\subseteq B_{\widehat{X}}^L(h_3(r))$ □

3.2.4. Putting It All Together

We can now use Lemma 11 to combine the interleavings established in Lemmas 12–14.

Theorem 2.

Let $L,\widehat{L}\subset {\mathbb{R}}^d$ and $X,\widehat{X}\subset {\mathbb{R}}^d\backslash (L\cup \widehat{L})$ be compact sets. If ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \delta <1$ and ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon <1$, then $(A_X^L,B_{\widehat{X}}^{\widehat{L}})$ are $(h_4,h_5)$-interleaved in $(0,1)$, where $h_4(r)=\frac{r+\epsilon }{(1-r-\epsilon )(1-\delta )}$ and $h_5(r)=\frac{r}{1-\delta -r}+\epsilon$.

Proof. 

We use Lemma 11 to combine the interleavings from Lemmas 12–14 to conclude that the pair $(A_X^L,B_{\widehat{X}}^{\widehat{L}})$ is $(h_3\circ h_2\circ h_1,h_1\circ h_2\circ h_3)$-interleaved in $(0,1)$. To complete the proof, we expand $h_3\circ h_2\circ h_1$ and $h_1\circ h_2\circ h_3$ as follows.

$$\begin{array}{cc}\hfill (h_3\circ h_2\circ h_1)(r)=(h_3\circ h_2)(r+\delta )& =h_3(\frac{r+\delta }{1-r-\delta })\hfill \\ \hfill & =\frac{r+\delta }{(1-r-\delta )(1-\epsilon )}\hfill \\ \hfill (h_1\circ h_2\circ h_3)(r)=(h_1\circ h_2)(\frac{r}{1-\epsilon })& =h_1(\frac{r}{(1-\epsilon )(1-\frac{r}{1-\epsilon })})\hfill \\ \hfill & =h_1(\frac{r}{1-\epsilon -r})\hfill \\ \hfill & =\frac{r}{1-\epsilon -r}+\delta \hfill \end{array}$$

Therefore, we have that $h_4(r)=\frac{r+\delta }{(1-r-\delta )(1-\epsilon )}$ and $h_5(r)=\frac{r}{1-\epsilon -r}+\delta$. □

3.3. Smooth Adaptive Distance and Homology Inference

In the preceding sections, we showed how to approximate (via interleaving) $A_X^L$, the sublevels of the distance to X in the induced metric, using a finite set of Euclidean balls, $B_{\widehat{X}}^{\widehat{L}}$. Now, we show how and when such an approximation gives a guarantee about the underlying space X itself. This is substantially more difficult, because it requires us to relate the sublevels of the induced metric to an object we do not have direct access to. As such, we will require some stronger hypotheses.

We will first review the critical point theory of distance functions. Then, we show how to smooth the induced metric to an arbitrarily close Riemannian metric, rendering the critical point theory applicable. Then, we put these together to prove the main inference result of the paper, Theorem 3.

3.3.1. Critical Points of Distance Functions

In this section, we give a minimal presentation of the critical point theory of distance functions to explain and motivate the results about interleaving offsets of distance functions in Riemannian manifolds. The main fact we use is that such interleavings lead immediately to results about homology inference (Lemma 16).

For a smooth Riemannian manifold M and a compact subset $X\subset M$, one can consider the function $f_X:M\to \mathbb{R}$ that maps each point in M to the distance to its nearest point in X as measured by the metric on the manifold. The gradient of $f_X$ can be defined on M, and the critical points are those points for which the gradient is zero. The critical values of $f_X$ are those values of r such that $f_X^{-1}(r)$ contains a critical point. The critical point theory of distance functions developed by Grove and others [11] extends the ideas from Morse theory to such distance functions. In particular, the theory gives the following result.

Lemma 15

(Grove [11]). If $[r,r^{\prime }]$ contains no critical values, then $f_X^{-1}([0,r])\hookrightarrow f_X^{-1}([0,r^{\prime }])$ is a homotopy equivalence.

This means that for intervals that do not contain critical values, the inclusion maps in the filtration $F(r):=\{f_X^{-1}([0,r])|r\ge 0\}$ are all homotopy equivalences and therefore induce isomorphisms in homology. This is used to give some information about the homology of filtrations that are interleaved with F.

We write $H_{*}$ to denote homology over a field. Therefore, for a set $X\subseteq {\mathbb{R}}^d$, we have a vector space $H_{*}(X)$, and for a continuous map $f:X\to Y$, we have a linear map $H_{*}(f)$. For the canonical inclusion map $X\hookrightarrow Y$ for a subset $X\subseteq Y$, we will denote the corresponding linear map in homology as $H_{*}(X\hookrightarrow Y)$. The image of this map is denoted $\mathrm{im}{H}_{*}(X\hookrightarrow Y)$.

Lemma 16.

Let $f_X$ be the distance function to a compact set in a Riemannian manifold such that $[r,r^{\prime }]$ contains no critical values of $f_X$. Let F be the sublevel filtration of $f_X$, and let G be a filtration such that $(F,G)$ are $(h_1,h_2)$-interleaved in $(r,r^{\prime })$. If $r^{\prime }<(h_2\circ h_1\circ h_2\circ h_1)(r)$, then:

$$\mathrm{im}{H}_{*}(G(h_1(r))\hookrightarrow G((h_1\circ h_2\circ h_1)(r)))\cong H_{*}(F(r)).$$

Proof. 

The interleaving and the hypotheses imply that we have the following inclusions.

$$F(r)\subseteq G(h_1(r))\subseteq F((h_2\circ h_1)(r))\subseteq G((h_1\circ h_2\circ h_1)(r))\subseteq F((h_2\circ h_1\circ h_2\circ h_1)(r))$$

The preceding lemma implies that the maps $F(r)\hookrightarrow F((h_2\circ h_1)(r))$, $F((h_2\circ h_1)(r))\hookrightarrow F((h_2\circ h_1\circ h_2\circ h_1)(r))$, and $F(r)\hookrightarrow F((h_2\circ h_1\circ h_2\circ h_1)(r))$ all induce isomorphisms in homology. It follows that $\mathrm{im}{H}_{*}(G(h_1(r))\hookrightarrow G((h_1\circ h_2\circ h_1)(r)))\cong H_{*}(F(r))$, because the inclusion of spaces in G is factored through a space in F, and it factors an inclusion of spaces, all of which are isomorphic in homology. □

3.3.2. Smoothing the Metric

To apply the critical point theory of distance functions to the induced metric directly, we would need it to be a smooth Riemannian manifold. Although it is not smooth, we can smooth it with an arbitrarily small change. The process, though a little technical, is not surprising, nor very difficult. It proceeds in three steps.

• We smooth the distance to L. This is the source of non-smoothness in the induced metric. This replaces $f_L$ with a smooth approximation, $\widetilde{f_L}$.
• The smoothed distance to L is used to define the smoothed induced metric $\widetilde{{\mathrm{d}}^L}$ analogously to the original construction of ${\mathrm{d}}^L$.
• The induced distance function $f_X^L$ can then be replaced by its smoothed version $\widetilde{f_X^L}$, and the corresponding smoothed offsets $\widetilde{A_X^L}$ are then well defined.

The complete construction of the smoothed offsets is presented in Appendix A. The end result is an interleaving between the induced offsets $A_X^L$ and the smoothed version $\widetilde{A_X^L}$ as expressed in the following lemma.

Lemma 17.

Given $\alpha ,\beta \in (0,1)$, consider compact sets $\widehat{L}\subseteq L\subset {\mathbb{R}}^d$ and compact sets $\widehat{X}\subseteq X\subset {\mathbb{R}}^d\backslash L^{\beta }$, such that ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \delta <1$ and ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon <1$, then $({\tilde{\mathcal{A}}}_X^L,{\mathcal{B}}_{\widehat{X}}^{\widehat{L}})$ are $(h_8,h_9)$-interleaved on $(0,1)$, where $h_8(r)=\frac{r+\alpha r+\epsilon }{(1-r-r\alpha -\epsilon )(1-\delta )}$ and $h_9(r)=\frac{r}{(1-\alpha )(1-\delta -r)}+\frac{\epsilon }{1-\alpha }$.

Proof. 

The proof can be found in Appendix A.1. □

3.3.3. The Weak Feature Size

Chazal and Leutier [19] introduced the weak feature size ($\mathrm{wfs}$) as the least positive critical value of a Riemannian distance function. We denote the weak feature size with respect to $\widetilde{f_X^L}(·)$ as ${\mathrm{wfs}}^L(X)$. In light of the critical point theory of distance functions, a bound on the weak feature size gives a guaranteed interval with no critical points. This allows one to infer the homology from another filtration (usually one that is discrete and built from data) as long as the second filtration is interleaved in that critical point free interval.

Lemma 18

(Adapted from [19] Theorem 4.2; see also [20]). Let S and $\widehat{S}$ be compact subsets of ${\mathbb{R}}^d$. If ${\mathrm{d}}_H(S,\widehat{S})>\epsilon$ and $\mathrm{wfs}(S)>4\epsilon$, then for all sufficiently small $\eta >0$,

$$H_{*}(A_S(\eta ))\cong \mathrm{im}{H}_{*}(A_{\widehat{S}}(\epsilon )\hookrightarrow A_{\widehat{S}}(3\epsilon )).$$

The key idea in that proof is that the Hausdorff bound gives an interleaving, while the weak feature size bound gives the interval without critical points. The technical condition regarding $\eta$ is present to account for strange compact sets that may be homologically different from their arbitrarily small offsets. It is reasonable to assume that for some sufficiently small $\eta$ that $H_{*}(A_S(\eta ))\cong H_{*}(S)$, and thus, one could “compute” the homology of S using only the sample $\widehat{S}$.

Most previous uses of the weak feature size have been applied in Euclidean spaces, but the critical point theory of distance functions can be applied more broadly to other smooth Riemannian manifolds. This is why we introduced it as ${\mathrm{wfs}}^L$ (with the superscript) to indicate the underlying metric.

3.3.4. Homology Inference

We have now introduced all the necessary pieces to prove our main homology inference result.

Theorem 3.

Given $\alpha ,\beta \in (0,1)$, consider compact sets $\widehat{L}\subseteq L\subset {\mathbb{R}}^d$ and compact sets $\widehat{X}\subseteq X\subset {\mathbb{R}}^d\backslash L^{\beta }$, such that ${\mathrm{d}}_H^{\widehat{X}}(L,\widehat{L})\le \delta <1$ and ${\mathrm{d}}_H^L(\widehat{X},X)\le \epsilon <1$. Define the real-valued functions $\mathsf{\Psi }$ and $\mathsf{\Phi }$ as:

$$\mathsf{\Psi }(r):=\frac{r+\alpha r+\epsilon }{(1-r-\alpha r-\epsilon )(1-\delta )}$$

and:

$$\mathsf{\Phi }(r):=\frac{r}{(1-\alpha )(1-\delta -r)}+\frac{\epsilon }{1-\alpha }.$$

Given any $\eta >0$, such that $\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )<1$, if ${\mathrm{wfs}}_L(X)>\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )$, then:

$$H_{*}({\tilde{A}}_X^L(\eta ))\cong \mathrm{im}(H_{*}(B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }(\eta )))\hookrightarrow B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta ))).$$

Proof. 

Given $\eta >0$ such that $\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )<1$, we have the following sequence of inclusions as a result of Lemma 17.

$$\begin{gathered} {\tilde{A}}_X^L(\eta )\stackrel{a}{\hookrightarrow }{B}_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }(\eta ))\stackrel{b}{\hookrightarrow }{\tilde{A}}_X^L(\mathsf{\Phi }\mathsf{\Psi }(\eta ))\stackrel{c}{\hookrightarrow }\dots \\ \dots \stackrel{c}{\to }{B}_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta ))\stackrel{d}{\hookrightarrow }{\tilde{A}}_X^L(\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )). \end{gathered}$$

(3)

As we assume that ${\mathrm{wfs}}_L(X)>\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )$, by the definition of the weak feature size, Lemma 16 implies that the inclusions $b\circ a$ and $d\circ c$ are homotopy equivalences. We remind the reader that if two spaces are homotopy equivalent, all the induced homology maps between the spaces are isomorphisms. By applying homology to each space and inclusion in the previous sequence, we have the following sequence of homology groups, where $b_{*}\circ a_{*}$ and $d_{*}\circ c_{*}$ are isomorphisms.

$$\begin{gathered} H_{*}({\tilde{A}}_X^L(\eta ))\stackrel{a_{*}}{\to }{H}_{*}(B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }(\eta )))\stackrel{b_{*}}{\to }{H}_{*}({\tilde{A}}_X^L(\mathsf{\Phi }\mathsf{\Psi }(\eta )))\stackrel{c_{*}}{\to } \\ {H}_{*}(B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )))\stackrel{d_{*}}{\to }{H}_{*}({\tilde{A}}_X^L(\mathsf{\Phi }\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta ))). \end{gathered}$$

(4)

The aforementioned isomorphisms $b_{*}\circ a_{*}$ and $d_{*}\circ c_{*}$ factor through $H_{*}(B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }(\eta )))$ and $H_{*}(B_{\widehat{X}}^{\widehat{L}}(\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )))$, respectively, proving that $b_{*}$ is surjective and $c_{*}$ is injective. We then have that $H_{*}({\tilde{A}}_X^L(\eta ))\cong H_{*}({\tilde{A}}_X^L(\mathsf{\Phi }\mathsf{\Psi }(\eta )))\cong \mathrm{im}{b}_{*}\cong \mathrm{im}(c_{*}\circ b_{*})$. □

3.3.5. Computing the Homology

The last step is to relate the smoothed offsets to something that can be computed. It will generally be the case that the approximation $\widehat{X}$ of X is not just compact, but also finite. Then, for any scale $\alpha \ge 0$, we have that $B_{\widehat{X}}^{\widehat{L}}(\alpha )$ is the union of a finite set of Euclidean balls.

The nerve theorem provides a natural way to compute the homology of a union of Euclidean balls. The nerve of a collection U of sets is the set of all subsets of U that have a nonempty intersection. It has the structure of a simplicial complex, whose homology can be directly computed by standard matrix reduction algorithms. When all nonempty intersections are contractible, the cover is said to be good. A cover by Euclidean balls (or any convex shape) is always good. For good covers, the nerve theorem, a standard result in algebraic topology [21], implies that:

$$H_{*}(\mathrm{Nrv}({\{\mathrm{ball}(x,\alpha f_{\widehat{L}}(x))\}}_{x\in \widehat{X}}))\cong H_{*}(B_{\widehat{X}}^{\widehat{L}}(\alpha )).$$

This is the most basic way to compute the homology of union of balls and is used throughout topological data analysis.

In our case, we are not just computing the homology of the union, but also the homology of the inclusion map. This computation will require a slightly stronger result. The persistent nerve lemma [20], applied to Diagram (4) when combined with the above isomorphisms, yields the following.

$$H_{*}({\tilde{A}}_X^L(\eta ))\cong \mathrm{im}{H}_{*}(\mathrm{Nrv}({\{\mathrm{ball}(x,\mathsf{\Psi }(\eta )f_{\widehat{L}}(x))\}}_{x\in \widehat{X}}))\hookrightarrow \mathrm{Nrv}({\{\mathrm{ball}(x,\mathsf{\Psi }\mathsf{\Phi }\mathsf{\Psi }(\eta )f_{\widehat{L}}(x))\}}_{x\in \widehat{X}})).$$

This last statement turns the isomorphism into an algorithm, because standard algorithms [22] can compute the homology of the inclusion of the nerves.

4. Conclusions

We present an alternative metric in Euclidean space that connects adaptive sampling and uniform sampling. We show how to apply classical results from the critical point theory of distance functions to infer topological properties of the underlying space from such samples. This provides a connection between methods in surface reconstruction (based on adaptive sampling) and homology inference (based on uniform sampling).

We show in Theorem 1 that there is a precise relationship between samples that are uniformly taken with respect to ${\mathrm{d}}^L$ at some scale, to those same samples being adaptive in the Euclidean metric. In Theorem 2, we show that we can interleave the sublevel sets of our distance function under this alternative metric with the metric balls resulting from our approximation of the metric, assuming that both $\widehat{X}$ and $\widehat{L}$ are uniformly well sampled with respect to the Hausdorff distance of ${\mathrm{d}}^L$ and ${\mathrm{d}}^{\widehat{X}}$. Finally, we show how to fully extend the critical point theory of distance functions and the weak feature size to give theoretical guarantees on homology inference from finite samples of X and L using the induced metric (Theorem 3).

The main limitation of adaptive metrics is that they require two sets as input, one to define the set and one to define the metric. In many instances, this is not available. However, we expect that the approach could find wider use in problems with labeled data. For example, data with binary labels may be viewed as the two sets X and L. Then, each set defines a metric on the other, where the metric is scaled according to how close it is to the other set. This is the subject of ongoing and future work.