A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach

The reach of a set is a number that captures the geometric properties of its shape. Roughly speaking, it provides a bound on the set’s curvature and quantifies how far apart different parts of the set are from each other. As a key descriptor of a shape’s complexity, the reach plays a crucial role as an assumption in many geometric and topological algorithms.

Formally, the reach of a (closed) set $𝒮\subset {ℝ}^d$ is the minimum of the distance between $𝒮$ and its medial axis, that is, the set of points in ${ℝ}^d$ for which the closest point in $𝒮$ is not unique. We illustrate these notions in Figure 1.

The reach was first introduced by Federer in [20]. Notably, earlier work by Erdős explored what we now refer to as the medial axis, although it did not address the reach itself [18, 19]. While Erdős studied the medial axis and Federer considered its complement, the term “medial axis” itself was coined only later, by Blum [12]. A related notion, the cut locus in Riemannian geometry, has a significantly longer history, with its origins traced to the work of Poincaré [34], Whitehead [38], and Myers [31, 32]¹¹1See [35] for a nice overview of the early history of the cut locus..

Due to their wide applicability, these concepts have been reintroduced multiple times. For instance, the (closure of) medial axis was reintroduced as the central set by Milman and Waksman [30], its complement as the unique footprint set by Kleinjohann [25], and the reach was referred to as the condition number by Niyogi, Smale, and Weinberger [33].

In [20], Federer established that the reach is stable under $C^{1,1}$-diffeomorphisms of the ambient space. Here, $C^{1,1}$ denotes a $C^1$ map whose derivative is Lipschitz, and by a $C^{1,1}$-diffeomorphism, we mean that both the diffeomorphism and its inverse are $C^{1,1}$. Federer also mentioned, without extensive detail [20, Remark 4.20], that the graph of a function has positive reach if and only if the function itself is $C^{1,1}$. Lytchak [27, 28] later proved that a topological submanifold of the Euclidean space without boundary has positive reach if and only if it is a $C^{1,1}$-submanifold. A quantified version of this statement can be found in [26].

The reach encapsulates the geometric complexity of a shape in a single non-negative value, making it a crucial assumption for ensuring the correctness of many geometric and topological algorithms. Several key classes of algorithms that depend on reach assumptions include:

• $\mathrm{■}$

  Triangulation algorithms for surfaces and manifolds (see for example [7, 6, 8, 13, 14, 15]).

• $\mathrm{■}$

  Manifold learning or reconstruction and manipulation (see for example [3, 4, 10, 22, 23, 36, 29, 5]).

• $\mathrm{■}$

  Homotopy inference (see for example [33, 37]).

All these algorithms have as input a point cloud queried from a manifold. Their output, and its correctness, varies:

• $\mathrm{■}$

  Triangulation algorithms produce as output a simplicial complex – often, but not always a variant of the Delaunay triangulation. Such algorithms are perceived as correct if the output complex is (piecewise linearly) homeomorphic to the underlying manifold.

• $\mathrm{■}$

  Manifold learning algorithms output a description of an approximation of the given manifold – for example as the zero set of a function or a projection operator. Such algorithms are correct if the output approximation is homeomorphic to the underlying manifold and sufficiently geometrically close to it.

• $\mathrm{■}$

  Homotopy inference algorithms output a simplicial complex, which is correct if it is homotopy equivalent to the underlying manifold.

For the success of these algorithms, it is essential to provide criteria that guarantee their correctness and quality. Such criteria are often formulated using the reach of the manifold.

In addition, reach estimation in and by itself is an important topic in inference (see for example [1, 2, 11]). The typical setting for this type of problems involves a point cloud, which is drawn from a probability measure whose support is a manifold satisfying a regularity condition. Such condition can, for example, be a guarantee that the reach of the manifold in question is larger than some (very small positive) constant. The goal is to estimate the actual reach of the manifold, with a guaranteed precision margin.

Most of the aforementioned works assume that the manifold in question is at least $C^{\mathrm{𝟐}}$, in addition to having positive reach. This assumption is often made because it allows the use of the full machinery of differential and Riemannian geometry. For instance, the second fundamental form is always well-defined in the $C^2$ setting [16, 17]. Yet, this condition is not entirely natural. Manifolds with positive reach are indeed at least $C^{1,1}$, see [26, 27, 28], and by Rademacher’s theorem [21], they are $C^2$ almost everywhere, but not necessarily everywhere.

On the other hand, requiring the manifold in question to be $C^{1,1}$ is quite natural, as it encompasses many configurations commonly found in modern modeling software, such as computer-aided design (CAD). This is because the majority of manufactured objects can be modeled as $C^{1,1}$ surfaces: For instance, consider a line segment and a circular arc intersecting at a point where their tangents coincide, as illustrated in Figure 2. This configuration has positive reach but is only $C^{1,1}$.

As a consequence of the results presented in this article (primarily Theorem 1), all aforementioned results can be extended from $C^2$ manifolds with positive reach to arbitrary manifolds with positive reach; hence the paper title.

In this work, we identify an embedded manifold locally (in a neighborhood of a point $p$) as a graph of a map from its tangent space to its normal space at $p$. This approach, which we illustrate in Figure 3, allows us to compare homeomorphic manifolds ($ℳ$ and ${ℳ}^{\prime }$ in Figure 3), embedded in Euclidean space of the same dimension, by comparing their corresponding maps and their derivatives ($f$ and $F$ in the figure). We say that two such manifolds are close in the $C^1$ sense, if, roughly speaking, both the manifolds and their tangent spaces are close. Formally, this is a condition on the corresponding maps $f$ and $F$, and we explain it in Definition 11.

Throughout the paper, we denote the dimension of the manifolds $ℳ$ and ${ℳ}^{\prime }$ by $n$, and the dimension of the ambient Euclidean space by $d$.

Our main contribution is the following statement:

In addition, our result can be restated in terms of density in the space of submanifolds:

This reformulation of the main theorem stands in a long line of density results from functional analysis and differential topology²²2We refer to Chapter 2 of [24] for an extensive overview.. Such results have been widely used to extend results from a smaller to a larger class of functions, without any extra effort. Hence, our result establishes a new link between computational geometry, topology, and manifold learning on the one hand, and functional analysis and differential topology on the other.

The main results from this paper might appear trivial to experts in differential topology at first glance: It is well known that Lipschitz functions can be smoothed while preserving the Lipschitz bounds of both the function and its derivative – a fact that is straightforward and proved succinctly in Lemmas 15 and 16. However, this observation alone is far from sufficient to achieve the main result of the paper.

The structure of the paper closely follows the different steps in the proof of Theorem 1. Let us provide you with an outlook:
Step 1: We start with a compact submanifold $ℳ$ of ${ℝ}^d$ of positive reach. For each point $p\in ℳ$, we can find a neighbourhood in which $ℳ$ is a graph of a function from the (affine) tangent to the normal space at $p$. Since the reach of $ℳ$ is positive, this function is $C^{1,1}$, and we use the bound on the Lipschitz constant of its derivative to control the angles between nearby tangent spaces.

We fix an $\epsilon$ and select a sample of points $p\in ℳ$ whose neighbourhoods cover $ℳ$ (see Figure 4). We only work with one neighbourhood at a time.

Step 2: We identify the point $p$ with $0\in {ℝ}^d$, and the tangent and normal spaces $T_pℳ$ and $N_pℳ$ with the first $n$ and last $d-n$ coordinates of ${ℝ}^d$, respectively. Following this identification, we denote the map describing $ℳ$ by $f$, and its domain by $U$.

Our first goal is to smooth $f$ in a neighbourhood of $0$. We split $U$ into three regions: a neighbourhood $U_1$ of $0$, a region $U_3$ covering the vicinity of $\partial U$, and a transition region $U_2$ in between. We then use kernel-based smoothing to define a function

that is smooth in $U_1$ and equals $f$ in $U_3$ (see Figure 5). To achieve this, we employ a partition of unity function. We revise the background on smoothing and partitions of unity in Section 2.1. These techniques allow us to control the Lipschitz constant of $F$ and its derivative, on which we give explicit bounds in Sections 3.1 and 3.2. We use operator norms to formulate these bounds. The background on operator norms is also presented in Section 2.1.

Step 3: We perform surgery on the manifold $ℳ$, and replace the graph of $p+f$ by the graph of $p+F$. We abuse notation and call this manifold ${ℳ}^{\prime }$, although it is “only” smooth in a neighbourhood of the point $p$ for now. Then we estimate the reach of ${ℳ}^{\prime }$. To this end, we leverage a result by Federer, which characterizes the reach of a manifold through the distance from a point on it to the affine tangent space of another point on it. We pick two points in $p^{\prime },q^{\prime }\in {ℳ}^{\prime }$ and investigate the distance from $q^{\prime }$ to the affine tangent space of $p^{\prime }$. It turns out that bounding this distance is straightforward when $p^{\prime }$ does not lie in the graph of $p+F$. In the other case, we establish the bound using the relationship between the functions $F$ and $f$, and the Lipschitz constants of $f$ and its derivative. We cover these results in Section 3.3.
Step 4: We repeat Steps 2 and 3 iteratively for each point $p$ of our sample, until we have smoothed the whole of $ℳ$. The process is illustrated in Figure 6. In each iteration, we have a one-parameter freedom in the choice of the smoothing kernel.

In this final step of the proof, we show that both the point sample and the smoothing kernels can be chosen in such a way that at the end, the smooth manifold ${ℳ}^{\prime }$ satisfies the conditions of Theorem 1. This final step is described in Section 4.

We indicate all the results in the paper that are (most probably) well known to experts in differential topology as “Folklore”. We provide proofs of these statements,as well as the proofs of all our statements except the main theorem, in the full version of this article.

We proceed as discussed in the introduction.

In the first step we select a sample $𝖯$ of the manifold $ℳ$ (see also Figure 15, right). To this end, we choose a parameter , and let $𝖯$ be a $\sqrt{\delta R}/16$-net⁴⁴4The factor $16$ in $\sqrt{\delta R}/16$ is almost certainly suboptimal. However, it simplifies the proof by a margin. on $ℳ$, meaning that

• $\mathrm{■}$

  for every point $x\in ℳ$ one can find a point $𝗉\in 𝖯$, such that $|x-𝗉|\le \sqrt{\delta R}/16$,

• $\mathrm{■}$

  for all $𝗉,𝗊\in 𝖯$, $|𝗉-𝗊|\ge \sqrt{\delta R}/16$.

Such a net exists thanks to [13, Lemma 5.2, Section 5.1.1].

Due to these properties, the $\sqrt{\delta R}/16$-balls centred at the points of the sample $𝖯$ cover $ℳ$. In addition, we consider balls of radius $\sqrt{\delta R}/2$ centred at the points of $𝖯$.

We need one more ingredient before we start iteratively visiting neighbourhoods of each point $𝗉\in 𝖯$ – a fixed partition of unity function, which we rescale at every iteration. To this end, we split the ball $B(0,4)\subseteq {ℝ}^n$ into three sets,

The two sets $\{V_1\cup V_2,V_2\cup V_3\}$ then cover the ball $B(0,4)$, and we let ${\psi }_0$ be the partition of unity function corresponding to the set $V_1\cup V_2$. Then ${\psi }_0\equiv 1$ on $V_1$, and ${\psi }_0\equiv 0$ on $V_3$.

Next, we select a point $𝗉\in 𝖯$, and restrict our attention to the ball $B(𝗉,\sqrt{\delta R}/2)$ of radius $\sqrt{\delta R}/2$ centred at $𝗉$.

Let $f$ be a function whose graph describes the manifold $ℳ$ in the ball $B(𝗉,\sqrt{\delta R}/2)$. To be more concrete, choose $f:T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)\to N_{𝗉}ℳ$ as in Theorem 27 in the full version of this article, or [26] which gives a more extensive version of Theorem 27. Due to this theorem and our choice of $\delta$, the derivative of $f$ is $\frac{1}{R-\delta }$-Lipschitz on the whole domain $T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)$.

We apply the smoothing construction described in Section 3.2. As ingredients, we need a partition of unity function, and a smoothing kernel.
Partition of unity function: We map the neighbourhood $T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)$ diffeomorphically to the ball $B(0,4)\subseteq {ℝ}^n$ using the canonical identification of the tangent space $T_{𝗉}ℳ$ with ${ℝ}^n$ and the map $x\mapsto \frac{8}{\sqrt{\delta R}}\cdot x$. The preimages of the sets $V_1,V_2$, and $V_3$ under this map are, respectively,

The sets $U_1,U_2,$ and $U_3$ are illustrated in Figure 15, on the left. We define $\psi$ by scaling the partition of unity function ${\psi }_0$: $\psi (x)={\psi }_0\left(\frac{8x}{\sqrt{\delta R}}\right)$. Then $\psi$ is the partition of unity function corresponding to the set $U_1\cup U_2$ in the cover $\{U_1\cup U_2,U_2\cup U_3\}$ of $T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)$, and thereby, $\psi \equiv 1$ on $U_1$, and $\psi \equiv 0$ on $U_3$. Furthermore:

By decreasing $\delta$ if necessary, we can also assume that $\frac{8}{\sqrt{\delta R}}{L}_{{\psi }_0}\le \frac{64}{\delta R}{L}_{D{\psi }_0}$. Thus:

Smoothing kernel: Let $C=\overline{supp\psi }$. For we choose a smoothing kernel ${\phi }_{\rho }:T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)\to ℝ$ such that

Such kernel exists due to Theorem 12. With these choices we define

We write ${ℳ}^{\prime }$ for the manifold that coincides with $ℳ$ outside of the ball of radius $\sqrt{\delta R}/2$ centred at the point $𝗉$, and is the graph of $𝗉+F$ inside this ball.

To be more concrete, we recall that we can write each point $p\in ℳ\cap B(𝗉,\sqrt{\delta R}/2)$ as $p=𝗉+y+f(y)$, with $y\in T_{𝗉}ℳ$. With this in mind we define, for each $p\in ℳ$:

and let ${ℳ}^{\prime }=\{p^{\prime }\mid p\in ℳ\}$.

We stress that

• $\mathrm{■}$

  inside the ball $B(𝗉,\sqrt{\delta R}/16)$, ${ℳ}^{\prime }$ is smooth ($C^{\mathrm{\infty }}$), and

• $\mathrm{■}$

  ${ℳ}^{\prime }=ℳ$ not only outside of the ball $B(𝗉,\sqrt{\delta R}/2)$, but already outside of the ball $B(𝗉,\sqrt{\delta R}/4)$.

Next, we set forth to bound the reach of ${ℳ}^{\prime }$. We choose two points $p^{\prime },q^{\prime }\in {ℳ}^{\prime }$, and estimate the distance between $q^{\prime }$ and the affine tangent space ${\mathrm{Tan}}_{p^{\prime }}{ℳ}^{\prime }$ – our bounds from Lemma 19 and Proposition 22 yield:

Thus, due to Federer’s Theorem [20, Theorem 4.18], the reach of the manifold ${ℳ}^{\prime }$ satisfies $\mathrm{rch}({ℳ}^{\prime })\ge R^{\prime },$ with $R^{\prime }$ as in equation (12).

Here we apply the smoothing construction iteratively for all points of $𝖯$. The correctness of the construction relies on two observations: The first observation is that (12) can be made as close to $R$ as needed. The second observation is that the manifold is locally changed only a finite number of times that (which in the non-compact case requires specific choices of $\delta$, $ϵ$, and $\rho$).

Because $𝖯$ is a $\sqrt{\delta R}/16$-net, it is locally finite. In particular, the number of points of $𝖯$ contained in a ball of radius $\sqrt{\delta R}/2$ centred at any point is $𝒪(8^d)$, as can be seen by a simple packing argument, see e.g. [13, Lemma 5.3, Section 5.1.1] for similar arguments. However, with every iteration of the construction, the points in a $\sqrt{\delta R}/2$ neighbourhood of the point $𝗉$ (which is the centre of the local smoothing operation) move⁵⁵5This $\sqrt{\delta R}/2$ size bound is not tight, in fact it can easily be improved to $\sqrt{\delta R}/4+{(\sqrt{\delta R}/4)}^2$ by noting that the part of $ℳ$ whose projection onto $T_{𝗉}ℳ\cap B(0,\sqrt{\delta R}/2)$ falls outside $U_2$ is not perturbed. by at most $\rho$, due to (5).

This means that the points can move at most by $N_V\rho$, where $N_V$ is the maximal number of times any point is visited. We claim that

Write $N_V(i)$ for the maximal number of times any point is visited after $i$ iterations of the surgery process. The number $N_V(i)$ is upper bounded by the number of points of $𝖯$ that, during the iterative process (up to iteration $i$), end up in a ball of radius $\sqrt{\delta R}/2$ around the displaced point, which can move as well. Because the points move by at most $\rho N_V(i)$ and need to enter the ball of radius $\sqrt{\delta R}/2$, they must initially lie inside a ball of radius $\sqrt{\delta R}/2+2\rho N_V(i)$. In other words, in order for a surgery centered at point $q$ to impact point $p$, the original positions of $p$ and $q$ must lie at distance at most $\sqrt{\delta R}/2+2\rho N_V(i)$ apart. Because the points in the sample are originally $\sqrt{\delta R}/16$ separated, a packing argument gives the following relation:

If we take $\rho$ sufficiently small, for example $\rho \le \frac{\sqrt{\delta R}/16}{2\cdot 8^{d+1}}$, then equation (13) is not satisfied for $N_V(i)=N_C$ with $N_C=8^{d+1}$. This means that for any $i$, we have that $N_V(i)\le N_C$. In particular at the end of the process the maximal number of times any point is visited is upper bounded by $N_C$, i.e. $N_V\le N_C$. $\mathrm{⊲}$

For the given $\epsilon >0$, we now choose $\rho$ and $\delta$ such that $R^{\prime }$ from equation (12) satisfies $|R-R^{\prime }|\le \epsilon /(4N_C)$. This is always possible. One can set $\delta =\epsilon /(4N_C)$; the choice for $\rho$ is a bit more subtle but choosing $\rho =𝒪({\delta }^4)$ works if $\delta$ (and equivalently $\epsilon$) is sufficiently small. Additionally, as we have seen, $\delta$ has to be sufficiently small so that $\rho N_C=8^{d+1}𝒪({\delta }^4)\le \sqrt{\delta R}/32$. This in particular means that even after the iterative process (that moves the points of $𝖯$) the resulting set is still a $\sqrt{\delta R}/8$ cover, which means that every point in the manifold is smoothed. This is the reason we started with a $\sqrt{\delta R}/16$-net and $U_1$ is of size $\sqrt{\delta R}/8$.

Let $p,q\in ℳ$ be arbitrary. We now note that:

• $\mathrm{■}$

  Every pair of points $p$ and $q$ in the manifold is visited/perturbed by the smoothing process at most $N_C$ times (each).

• $\mathrm{■}$

  We have picked $\rho$ and $\delta$ such that $|R-R^{\prime }|\le \epsilon /(4N_C)$, where here the difference between the reach $R$ and $R^{\prime }$ is interpreted as between each iteration of the smoothing process.

This means that the characterization of the reach (for the points $p$ and $q$) of Lemma 24 only changes $2N_C$ times, and thus for a total of less than $\epsilon$. Because the choice of $p$ and $q$ is arbitrary, the reach after the smoothing has decreased by at most $\epsilon$. $◀$