Ryan Cotsakis
email: ryan.cotsakis@univ-cotedazur.fr

Computable bounds for the reach and r-convexity of subsets of R d

Keywords: double offset, beta-reach, medial axis, high-dimensional, point clouds, geometric inference

Computable bounds for the reach and r-convexity of subsets of R d

Introduction

A number of concepts from convex geometry generalize from convex sets to much larger classes of sets. A classic example from [START_REF] Federer | Curvature measures[END_REF] is the extension of kinematic formulas (in particular, Steiner's formula) for convex sets to sets with positive reach (see Definition 2). Another example is the notion of the convex hull of a set, which can be weakened to the r-convex hull, for r > 0. This weak notion of a convex hull, instead of being expressed as the intersection of halfspaces, is expressed in terms of intersections of the complements of open balls of radius r. The resulting intersection is said to be r-convex (see Definition 4), which differs subtly from the notion of reach, and these differences have been studied in [START_REF] Colesanti | Geometric and isoperimetric properties of sets of positive reach in E d[END_REF] and [START_REF] Cuevas | On Statistical Properties of Sets Fulfilling Rolling-Type Conditions[END_REF] for example. Both the reach and r-convexity-ranging from 0 to ∞ inclusive-can be seen as measures of the degree to which a set is convex. This paper introduces methods of computing upper bounds for these quantities from point cloud data in several, general settings.

There is a vast literature on properties of r-convex sets, dating from [START_REF] Perkal | Sur les ensembles ϵ-convexes[END_REF]. Their relations to other classes of sets that generalize convexity have been studied in [START_REF] Colesanti | Geometric and isoperimetric properties of sets of positive reach in E d[END_REF][START_REF] Cuevas | On Statistical Properties of Sets Fulfilling Rolling-Type Conditions[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Walther | On a Generalization of Blaschke's Rolling Theorem and the Smoothing of Surfaces[END_REF]. The use of r-convexity in image smoothing has been suggested in [START_REF] Cuevas | A nonparametric approach to the estimation of lengths and surface areas[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Walther | On a Generalization of Blaschke's Rolling Theorem and the Smoothing of Surfaces[END_REF] as well as for set estimation in [4, 30-32, 43, 45]. In other literature, the r-convex hull of a set is referred to as its double offset [START_REF] Chazal | Shape Smoothing Using Double Offset[END_REF][START_REF] Chazal | Stability of curvature measures[END_REF][START_REF] Kim | Homotopy reconstruction via the cech complex and the vietoris-rips complex[END_REF]. In [START_REF] Cuevas | On Boundary Estimation[END_REF], the authors use a rolling-type condition (weaker than rconvexity) to improve the rate of convergence of their set boundary estimator. Efforts towards estimating the largest r such that a set is r-convex have been made in [START_REF] Rodríguez Casal | A fully data-driven method for estimating the shape of a point cloud[END_REF]; the authors test the uniformity of a point cloud on its r-convex hull using the statistical test of uniformity proposed in [START_REF] Berrendero | A multivariate uniformity test for the case of unknown support[END_REF].

The reach is a popular measure of convexity largely due to its link with the Steiner formula; for the larger the reach of a set, the larger the interval on which the volume of a dilation of the set is polynomial in the dilation radius [START_REF] Federer | Curvature measures[END_REF]Theorem 5.6]. The positivity of the reach implies a number of desirable properties, and so positive reach is a common hypothesis to guarantee convergence rates of statistical estimators of geometric quantities [START_REF] Biermé | Lipschitz-Killing curvatures of excursion sets for two-dimensional random fields[END_REF][START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF][START_REF] Cotsakis | On the perimeter estimation of pixelated excursion sets of 2D anisotropic random fields[END_REF][START_REF] Cuevas | Set estimation: Another bridge between statistics and geometry[END_REF][START_REF] Rataj | Sets with positive reach[END_REF][START_REF] Thäle | 50 years sets with positive reach-a survey[END_REF]. In the field of geometric data analysis, the reach constitutes a commonly used measure of regularity of a set's boundary, and is hence also referred to as the condition number [START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF]. In topological data analysis, a set's reach is shown to quantify the ability to infer its homology from point cloud data [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in rn from noisy data samples[END_REF][START_REF] Kim | Homotopy reconstruction via the cech complex and the vietoris-rips complex[END_REF][START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF][START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF]. The statistical estimation of the reach has been of particular interest in recent literature. [START_REF] Aamari | Estimating the reach of a manifold[END_REF] and [START_REF] Aamari | Nonasymptotic rates for manifold, tangent space and curvature estimation[END_REF] suggest estimating the reach of a smooth submanifold of R d by measuring distances between it and its tangent spaces-a strategy inspired by the formulation of the reach in [START_REF] Federer | Curvature measures[END_REF]Theorem 4.18]. These works obtain bounds on the minimax rate of convegence for this estimator when the manifold is C 3 -smooth, and when its tangent spaces are known. Following up to these works, [START_REF] Aamari | Optimal reach estimation and metric learning[END_REF] establishes an optimal convergence rate for minimax estimators of the reach of C k -smooth submanifolds of R d without boundary. The rates that they establish adapt to the smoothness of the manifold, and to the type of phenomenon that limits the reach (see Remark 8). [START_REF] Berenfeld | Estimating the Reach of a Manifold via its Convexity Defect Function[END_REF] looks to the convexity defect function introduced in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] and suggests an estimator for the reach of C k -smooth manifolds by establishing a link between the convexity defect function and the reach. Convergence rates of their estimator are given for k ≥ 3. In [START_REF] Cholaquidis | Universally consistent estimation of the reach[END_REF], the authors introduce a complete and tractable method for estimating the reach from point cloud data involving the computation of graph distances in a spatial network defined over the point cloud. Their approach is based on the formulation of the reach introduced in [16, Theorem 1]. Other strategies for estimating the reach involve a prior estimation of the medial axis (see Definition 3) [START_REF] Dey | Normal and feature approximations from noisy point clouds[END_REF][START_REF] Dey | Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee[END_REF]. The λ-medial axis [START_REF] Chazal | The "λ-medial axis[END_REF], µ-medial axis [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF], and (λ, α)-medial axis [START_REF] Lieutier | Hausdorff and gromov-hausdorff stable subsets of the medial axis[END_REF] are all generalizations of the medial axis, and the reach can conceivably be approximated by the minimal distance from a set to the estimate of the medial axis of its complement. Such a strategy is suggested in [START_REF] Cuevas | On the estimation of the medial axis and inner parallel body[END_REF] for the λ-medial axis, where the authors heavily rely on the notion of r-convexity in their construction. A number of other authors have taken an interest in the mathematical properties of the reach. [START_REF] Poliquin | Local Differentiability of Distance Functions[END_REF] identifies the sets of reach r with the r-proximally smooth sets introduced in [START_REF] Clarke | Proximal Smoothness and the Lower-C 2 Property[END_REF], implying that the reach can be characterized by the gradients of the distance-to-set function. [START_REF] Colesanti | Geometric and isoperimetric properties of sets of positive reach in E d[END_REF] makes a number of insightful connections between the reach and other geometrical properties of sets. [START_REF] Attali | Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape[END_REF] studies Vietoris-Rips complexes via the reach, proving that the reach of a set can only increase if intersected by sufficiently small balls. An alternative characterization of the reach, involving pairwise geodesic distances, is provided in [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF]. The authors also study the relationship between midpoints of pairs of points in a set, and the set's reach [16, Lemma 1]. We base the construction of our bound for the reach on this result (see Theorem 2). This paper makes steps towards providing computationally tractable methods for bounding the reach and r-convexity of subsets of R d given point cloud data that represent the underlying sets. Firstly, we establish some facts about the reach of closed subsets of R d . We prove that the r-convexity and reach are equivalent for compact subsets of R d whose topological boundary is a C 1 -smooth, (d -1)-dimensional manifold without boundary (see Theorem 1). In addition, for closed subsets of R d , we introduce the β-reach (see Definition 6), a quantity that loosely represents the reach of a set when features of size less than β ∈ [0, ∞) are ignored. Indeed, the β-reach is identified with the reach for β = 0 (see Theorem 2). These ideas are used to create methods of inferring bounds on the reach and r-convexity of sets from point cloud data. For general, closed subsets of R d (possibly having finite d-volume, and having no smoothness conditions on their topological boundaries), we provide an upper bound of the r-convexity of the set based on samples of the set and its complement at sampling locations that extend over R d . We show that, as the sampling locations become dense in R d , this bound converges to the largest r such that the set is r-convex (see Theorem 3). An example on real data in 3 dimensions shows that this method identifies regions where the underlying set is not locally r-convex, for r > 0, with a test specificity of 100%. Similarly, for any closed set A ⊆ R d , we define an upper bound on the reach based on a set of points known to reside in A. As the set of points converges in the Hausdorff metric to A, we show that the bound converges to the reach of A, and provide the rate of convergence in terms of the Hausdorff distance between A and the sample points (see Theorem 4). A weak regularity condition on the β-reach of A, for β near 0, is used to show the convergence of our upper bound with a rate. In practice, both the β-reach of a point cloud and the upper bound on the reach can be computed efficiently in high-dimension. The computational complexity of the method increases only linearly with the dimension of the ambient space d.

The organization of the paper is as follows. Section 2 introduces the notation that we use throughout the document, explores the relationships between the reach and r-convexity, and introduces the β-reach. Section 3 describes the three methods that we propose for inferring bounds and approximations for the reach and r-convexity of general compact subsets of R d from point cloud data. The bounds for the r-convexity and reach are studied in Sections 3.1 and 3.2 respectively. Section 3.3 elaboates on how the β-reach of point clouds can be used to approximate the β-reach of the sets that they represent. In Section 4, we provide numerical studies that underline the computability of our methods. An application of the methods on real data is given in Section 4.1. In Section 4.2, the methods are tested against simulated data for which the reach and r-convexity are known, and empirical rates of convergence are provided. Some technical proofs and auxiliary results are postponed to Section 5.

Definitions and important notions

The sets that we study in this paper are subsets of R d , endowed with the Euclidean metric ∥•∥ 2 . For a set S ⊆ R d , let ∂S denote its topological boundary, let cl(S) := S ∪ ∂S denote its closure, and let S c denote its complement in R d . Denote the closed ball with radius r ∈ R + centered at s ∈ R d by B(s, r) := {t ∈ R d : ∥t -s∥ 2 ≤ r}. For t ∈ R d , denote the distance between t and a non-empty set S by δ S (t) := inf{∥t -s∥ 2 : s ∈ S}.

Set dilation, set erosion, and combinations of the two

Definition 1 (Operations on subsets of R d ). We recall the Minkowski addition of two sets A, B ⊆ R d ,

A ⊕ B := {x + y : x ∈ A, y ∈ B}.

The Minkowski difference is given by

A ⊖ B := y∈B (A ⊕ {y}) = (A c ⊕ B) c , where A c denotes the complement of A in R d . For r ∈ R, let A r := A ⊕ B(0, r),
for r ≥ 0, A ⊖ B(0, -r), for r < 0, denote either the dilation or erosion of a set A, depending on the sign of r. Finally, define A •r := (A r ) -r to be the closing of A by B(0, r) if r ≥ 0 and the opening of A by B(0, -r) if r < 0.

For r ≥ 0 and A ⊆ R d closed, it follows from Definition 1 that A r (also known as the r-offset of A in, e.g., [START_REF] Chazal | Shape Smoothing Using Double Offset[END_REF]) denotes all the points in R d within a distance r of the set A. The set A -r denotes all the points in A a distance of at least r from ∂A.

With these notions established, the Hausdorff distance between two closed sets

A, B ⊆ R d is defined as d H (A, B) := inf{r ∈ R + : A ⊆ B r , B ⊆ A r }.
Lemma 1. Let r, s > 0, and let A ⊆ R d . The following identities hold:

(a) (A r ) c = (A c ) -r , (b) A ⊆ A •r , (c) (A r ) s = A r+s , (d) (A r ) -s ⊇ A r-s , (e) (A -r ) s ⊆ A s-r .
Proof of Lemma 1 Fix r, s > 0. The identity in (a) follows directly from Definition 1. Item (b) is proved by contradiction. Let a ∈ A and suppose a ∈ (A•r) c = (Ar) c ⊕ B(0, r). Then there is a p ∈ (Ar) c such that a ∈ B(p, r) ⇔ ∥p -a∥ 2 ≤ r ⇔ p ∈ B(a, r) ⇔ p ∈ Ar; thus, a contradiction. To prove (c), remark that B(0, r)⊕B(0, s) = B(0, r+s) and that Minkowski addition is associative. To prove (d), consider the case where r ≥ s, then (Ar) -s = (A r-s+s ) -s = ((A r-s )s) -s = (A r-s )•s ⊇ A r-s . For the case r < s, write (Ar) -s = (Ar) r-s-r = ((Ar) -r ) r-s = (A•r) r-s ⊇ A r-s . To show (e), consider the complements of the sets in (d) and apply (a) repeatedly. □

The reach and related concepts

Definition 2 (The reach). Recall from [START_REF] Federer | Curvature measures[END_REF] that the reach of a set A ⊆ R d is given by reach(A) := sup r ∈ R + : ∀y ∈ A r ∃!x ∈ A nearest to y .

If reach(A) > 0, then A is said to have positive reach.

A useful notion related to the reach of a closed set A is the medial axis of A c , originally proposed in [START_REF] Blum | A transformation for extracting new descriptions of shape. Models for the perception of speech and visual form[END_REF]. The reach of a closed set A can be alternatively expressed as

reach(A) = inf{∥a -x∥ 2 : a ∈ A, x ∈ M(A c )}. (1)

Connections to r-convexity

Definition 4 (r-convexity). A set A ⊆ R d is said to be r-convex for r ∈ R + if it is closed and A •s = A for all s ∈ (0, r) (see, e.g., [START_REF] Perkal | Sur les ensembles ϵ-convexes[END_REF]). Define the quantity rconv(A) := sup{r ∈ R :

A •r = A}.
An equivalent definition of r-convexity is as follows: a set A ⊆ R d is r-convex if and only if it can be expressed as the complement of a union of open balls of radius r.

Theorem 1. Let A be closed in R d . It holds that reach(A) ≤ rconv(A). (2)
Moreover, if ∂A is a C 1 -smooth (d-1)-dimensional manifold without boundary, then

reach(A) = rconv(A). (3)
Equation ( 2) is proven in Cuevas et al. [32, Proposition 1] for compact A.

Nonetheless, we reprove the statement for closed A in the proof of Theorem 1, which we postpone to Section 5. The novelty in Theorem 1 is that it provides a class of subsets of R d for which the reach and r-convexity are equal.

To see that the r-convexity and the reach of a set are indeed distinct notions for general subsets of R d , Figure 1 provides an example of a closed set A for which reach(A) < rconv(A). Consider also the following remark. Recently, a counterexample to Borsuk's conjecture that r-convex sets are locally contractible, was published in [START_REF] Cholaquidis | A counter example on a borsuk conjecture[END_REF]. The conjecture is easily seen to be false by mapping a closed set in R d-1 that is not locally contractible to a (d -1)-dimensional hyperplane in R d under an isometry. Here, we provide some corollaries to Theorem 1 that provide alternative sets of sufficient conditions for the equality of the reach and the r-convexity. The first applies to sets in Serra's regular model [50, p. 144].

Corollary 1. Let A ⊂ R d be non-empty, compact, and path-connected. If rconv(cl(A c )) > 0, then reach(A) = rconv(A).

The proof of Corollary 1, which relies heavily on Theorem 1 in [START_REF] Walther | On a Generalization of Blaschke's Rolling Theorem and the Smoothing of Surfaces[END_REF], is postponed to Section 5. Likewise, we prove the following result in Section 5.

Corollary 2.

Let A be a closed set in R d and let ϵ ∈ R + . Then reach(A ϵ ) = rconv(A ϵ ).

The β-reach

We show in Theorem 2 below, that the reach of a set can be formulated in terms of pairs of points in the set, and the distance to the set from their midpoints. We define a parametrized version of the reach by restricting to pairs of points whose midpoints are sufficiently far from the set. The so-called β-reach is constructed from the following family of functions.

Definition 5 (Spherical cap geometry). Define for α ∈ [0, ∞) and x ∈ [0, α/2],

g α (x) := α 2 8x + x 2 , x > 0, ∞, x = 0, (4)
and its inverse for r ≥ α/2, See Figure 3 for a geometric interpretation of the function in (4) and its inverse in [START_REF] Adler | Random fields and geometry[END_REF]. Evidently from the figure, this function is derived from the height of a spherical cap; it is written about in [START_REF] Attali | Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape[END_REF][START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF][START_REF] Berenfeld | Estimating the Reach of a Manifold via its Convexity Defect Function[END_REF][START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF][START_REF] Divol | Minimax adaptive estimation in manifold inference[END_REF] in reference to the reach.

g -1 α (r) := r -r 2 - α 2 4 . (5)
Definition 6 (The β-reach). For a closed set A ⊆ R d and β ∈ [0, ∞), let the β-reach of A be defined as

reach β (A) := inf g ∥a2-a1∥ 2 (x) : a 1 , a 2 ∈ A, x = δ A a 1 + a 2 2 ≥ β ,
where g ∥a2-a1∥ 2 (x) is defined in [START_REF] Aaron | Estimation of surface area[END_REF]. Recall that δ A : R d → R maps each point in R d to its distance from A. See Figure 4 for a visual aid.

By restricting to pairs of points a 1 , a 2 ∈ A in Figure 4 that yield x ≥ β, the β-reach of A is the largest lower bound of the resulting values of g ∥a2-a1∥ 2 (x).

a 1 , a 2 ∈ A satisfying x ≥ β. p A a 1 a1+a2 2 a 2 g -1 ∥a2-a1∥ 2 (δ A (p))
Fig. 5: The interior of the large ball centered at p does not intersect A, so the distance from the midpoint (a 1 +a 2 )/2 to the set A is at least g -1 ∥a2-a1∥ 2 (δ A (p)). This construction is used in the proof of Theorem 2.

If one does not restrict the size of x (i.e., for β = 0), then this largest lower bound is precisely reach(A). This is formalized by the following theorem.

Theorem 2. Let A be closed in R d . The map β → reach β (A) for β ∈ R + is non-decreasing; moreover, lim β↘0 reach β (A) = reach 0 (A) = reach(A). ( 6
)
Proof of Theorem 2 The non-decreasing property is seen immediately via the inclusion

(a 1 , a 2 ) ∈ A 2 : δ A a 1 + a 2 2 ≥ β 2 ⊆ (a 1 , a 2 ) ∈ A 2 : δ A a 1 + a 2 2 ≥ β 1 , for all β 1 , β 2 ∈ R satisfying β 1 < β 2 .
Now, we start by proving the second equality in [START_REF] Attali | Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape[END_REF]. The proof is largely supplied by Lemma 1 of [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF] which provides

reach(A) ≤ g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 , (7)
for all a 1 , a 2 ∈ A, since gα(x) is non-increasing in x. What remains to show is that reach(A) is the largest lower bound in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]; i.e., if r > reach(A) then there exist a 1 , a 2 ∈ A such that r exceeds the right-hand side of [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. Let r > reach(A) and let r ∈ (reach(A), r). By the definition of reach(A) (Definition 2), ∃p ∈ A r and a 1 ,

a 2 ∈ A such that ∥a 1 -p∥ 2 = ∥a 2 -p∥ 2 = δ A (p) ≤ r. Since the interior of B(p, δ A (p)) does not intersect A, we have δ A a 1 + a 2 2 ≥ g -1 ∥a2-a1∥ 2 (δ A (p)),
(see Figure 5) and

g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 ≤ δ A (p) ≤ r < r.
This proves that reach 0 (A) = reach(A).

Finally, we show the first equality in [START_REF] Attali | Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape[END_REF]. The non-decreasing property gives lim β↘0 reach β (A) ≥ reach 0 (A). Now, it suffices to show the reverse inequality. For any ϵ > 0, there exists a 1 , a 2 ∈ A satisfying

g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 < reach 0 (A) + ϵ.
Any such pair (a 1 , a 2 ) must satisfy δ A a1+a2 2

> 0, and so for

β ∈ 0, δ A a1+a2 2 , it holds that reach β (A) < reach 0 (A) + ϵ. Thus, lim β↘0 reach β (A) ≤ reach 0 (A). □ Remark 2.
For any α ∈ [0, ∞) and x ∈ [0, α/2], one has g α (x) ≥ x (see Figure 2). Thus, for any closed set A and

β ∈ R + , reach β (A) ≥ β.
Intuitively, this means that the β-reach excludes small, reach-limiting features of the set that have scale less than β. The values of β for which reach β (A) = β are the distances from the critical points of the generalized gradient function [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF] to the set A.

Remark 3. Other generalizations of the reach are constructed similarly to the β-reach, in that they formulate the reach as an infimum or supremum over some set, and add or remove elements in the set using some real parameter (in our case, β). For example, [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF]Theorem 1] expresses the reach of a set A ⊂ R d as the supremum over a subset of R + that satisfies a certain condition relating to A. By "continuously" weakening the condition with a parameter δ ∈ [0, ∞), the authors in [START_REF] Aamari | Optimal reach estimation and metric learning[END_REF] introduce the spherical distortion radius as the supremum of the larger subset of R + satisfying the weaker condition parametrized by δ.

The spherical distortion radius is identified with the reach for δ = 0. In an earlier work, [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF] introduces the µ-reach by considering the shortest distance from an element in the set to the µ-medial axis, a filtered version of the medial axis by considering regions where the generalized gradient function [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF] is less than some µ ∈ (0, 1]. The β-reach, the µ-reach, and the spherical distortion radius, are all generalizations of the reach that exclude "small-scale" features as decided by the corresponding parameter β, µ, or δ.

One significant advantage of the β-reach is its computability for highdimensional point cloud data (see Section 3.3). In this setting, the formulation of the reach in terms of the β-reach for β = 0 can also be used to construct an upper bound for the reach of any compact A ⊂ R d (see Section 3.2).

For a closed set A ⊆ R d , one can study the map β → reach β (A) for β ∈ [0, ∞), which we refer to as the β-reach profile of the set A. We will see in Section 3 that a set's β-reach profile provides pertinent information regarding the estimation of the reach from point cloud data, especially through its firstorder approximation at β = 0. Some exemplary sets and their β-reach profiles are considered in the several examples that follow.

Example 1 (The β-reach of a corner). For two line segments in R d with ends joined by an angle θ ∈ (0, π), the β-reach of their union is β 2 1 + sec 2 θ 2 , for sufficiently small β > 0. See Figure 6 for an illustration.

Example 2 (The β-reach of an arc). The β-reach of a circular arc of angle at most π is equal to the radius of the arc, for sufficiently small β > 0.

Example 3 (The β-reach of a bottleneck structure). If the reach of a set A ⊂ R d is determined by a bottleneck structure like those described in [START_REF] Aamari | Estimating the reach of a manifold[END_REF],

:= {(x, f (x)) : -1 ≤ x ≤ 1} ⊂ R 2 satisfies reach(A) = 1 2h ′ (0) (8)
and

reach β (A) = 1 2h ′ (0) + 1 2 - h ′′ (0) 4h ′ (0) 3 β + o(β), (9)
for sufficiently small β > 0. Justifications for Equations ( 8) and ( 9) are provided at the end of Section 5. Figure 7 depicts a special case of this example with h(x) = x/2.

Methods for point cloud data

In practice, one might be interested in identifying bounds on the reach and r-convexity of a set A ⊆ R d given a discrete set of points that are known to reside in A. The goal of this section is to provide computational methods for bounding the reach and the r-convexity from above, and producing diagnostics for possible approximations. The three main settings that we consider are:

(a) One has access to a point cloud that extends over R d in the sense that R d can be covered by balls of fixed radius ϵ centered at each point. Moreover, one knows the partition of the points that lie in A ⊆ R d , and those that lie in A c . See section 3.1 for a treatment of this setting. (b) One has access to a set of points for which it is known that A ⊆ R d can be covered by balls of fixed radius ϵ centered at each point. Here, ϵ is known. See section 3.2. (c) The set A is a submanifold of R d of dimension m < d. One has access to a set of points that is known to be contained in A. See section 3.3.

The mathematical results that we present in this section hold in arbitrary dimension d. Nevertheless, the computational complexity of the method described in Section 3.1 for setting (a) increases quite drastically as higher dimensions are considered.

For the method that we present for setting (b) described in Section 3.2, its computation time depends on the ambient dimension only through the computation of distances in R d , which is linear in d. The algorithm is largely dependent on the number of points used, which may be large in high dimension to ensure small ϵ. The computational complexity of visualizing the β-reach profile of the manifold in setting (c) is also linear in the dimension of the ambient space, and so the algorithm that we describe in Section 3.3 can adapt to large values of d. Contrast this with existing methods that aim to approximate the reach by first approximating the medial axis [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF][START_REF] Chazal | The "λ-medial axis[END_REF][START_REF] Cuevas | On the estimation of the medial axis and inner parallel body[END_REF][START_REF] Dey | Normal and feature approximations from noisy point clouds[END_REF][START_REF] Dey | Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee[END_REF][START_REF] Lieutier | Hausdorff and gromov-hausdorff stable subsets of the medial axis[END_REF], where in high dimension, accessing the medial axis becomes computationally challenging.

The relationship between d, m, n, and our method's performance is elaborated on in Remark 10 in Section 3.3.

An upper bound for the r-convexity of a set

In this section, we introduce a method for identifying when sets are not rconvex, for r > 0, with a true negative rate of 100%. That is, given a set A ⊂ R d that is observed over some grid of points (possibly lacking structure), we show how to correctly identify for which values of r > 0 the set A is certainly not r-convex. The smallest of these values of r provides an upper bound for rconv(A), and by Equation ( 2), an upper bound for reach(A). Moreover, if the sampling becomes dense in R d , we show that this upper bound converges to rconv(A).

Here, we define operations analogous to dilation and erosion, for discrete sets of points.

Definition 7. Let Φ be a point cloud in R d , i.e., a countable subset of R d . For a set A ⊆ Φ, we make a slight abuse of notation and denote for r ∈ R,

A r := {p ∈ Φ : δ A (p) ≤ r}, for r ≥ 0, {a ∈ A : δ Φ\ A (a) > -r}, for r < 0. (c) (b) (a)
Fig. 8: An example where ( A r ) -r in (c) is strictly larger than A in (a), while the underlying set A is r-convex. The boundary ∂A is shown as a dashed line and r is three times the pixel width.

Remark 4. We emphasize that for a point cloud Φ, a subset A ⊆ Φ, and a real number r ∈ R, Definition 7 implies that A r ⊆ Φ. Contrast this with the set A ⊕ B(0, |r|), which is not contained in Φ for r > 0.

Let us illustrate the operations in Definition 7 using the example in Figure 8. The set A ⊂ R 2 occupies the bottom left corner of the domain, just until the dashed line. When sampled on a square lattice Φ, one obtains the image in panel (a); each pixel is centered on a point in Φ, and grey if the point lies in A. Dilating the grey pixels A by r = 3 × (pixel width), one obtains the grey pixels in panel (b), A r . If one then erodes A r by r (equivalent to dilating Φ \ A r by r and taking complements), one obtains the grey pixels in panel (c), ( A r ) -r . Notice, however, that there is a point in ( A r ) -r that is not in A. This might be surprising since we chose a set A such that A •r = A. This illustration shows that naively testing for r-convexity using the discrete dilation and erosion operations mistakenly classifies sets as not r-convex when indeed they are. The following theorem shows how to correctly identify sets as not being rconvex, and gives an upper bound for the r-convexity of a set that is tight in some sense. Theorem 3. For n ∈ N + , let Φ (n) be a point cloud in R d , and suppose that

ϵ n := sup δ Φ (n) (q) : q ∈ R d ( 10
)
is finite. Let A be a compact subset of R d , and for n ∈ N + , define A (n) := A ∩ Φ (n) and the corresponding bound, r-ϵn ) -(r+ϵn) contains the dark grey pixels, which are not contained in A (n) . Thus, r ≥ rconv(A). Here, r is nine times the pixel width.

r (ϵn) ( A (n) ) := inf r > ϵ n : ( A (n) r-ϵn ) -(r+ϵn) ⊈ A (n) . ( 11
) (b) (a)
It holds that inf n∈N + r (ϵn) ( A (n) ) ≥ rconv(A). (12)
Moreover, if

ϵ n → 0 and d H ( A (n) , A) → 0 as n → ∞, then lim n→∞ r (ϵn) ( A (n) ) = rconv(A). ( 13
)
Theorem 3 provides a method for correctly identifying which subsets of R d are not r-convex. If a dilation of the the discretization A (n) by r-ϵ n followed by an erosion of r+ϵ n produces a set that is not contained in A (n) , then rconv(A) ≤ r.

See Figure 9 for an example of a set A for which ( A

(n) r-ϵn ) -(r+ϵn) ⊈ A (n)
. The precise regions where r-convexity does not hold are highlighted by the method.

Remark 5. Note that r (ϵn) ( A (n) ) in ( 11) can be computed using entirely available information, since ϵ n in ( 10) is a feature of the point cloud Φ (n) and not of the unknown set A. In particular, there is no need to estimate d H ( A (n) , A) for the construction of r (ϵn) ( A (n) ). A binary search algorithm, along with the discrete dilation operations in Definition 7, are sufficient for the numerical calculation of r (ϵn) ( A (n) ). Remark 6. The requirement that Φ (n) extends over all of R d (see Equation [START_REF] Berenfeld | Estimating the Reach of a Manifold via its Convexity Defect Function[END_REF]) allows for a mathematical simplification and is not needed in practice. In real applications, one only requires that d H (Φ (n) , T ) = ϵ n for some compact T ⊂ R d that contains A rconv(A)+2ϵn . In the case where A is lower dimensional than the embedding space R d , one can add any finite number of points uniformly distributed on T to Φ (n) , and they will almost surely not belong to A. Fig. 10: A discrete dilation of the set A (n) (black points) by the length of the green arrows (rconv(A) -ϵ n ) followed by a discrete erosion by the length of the longer blue arrow (rconv(A) + ϵ n ) leaves all of the white points out of the resulting set. The boundary of A rconv(A)-ϵn is shown as a dashed line.

The proof of Theorem 3 is quite technical, and so we postpone it to Section 5. Nevertheless, Figure 10 provides an intuitive illustration that helps understand Equation ( 12). This is an example of a worst-case scenario, in that a dilation of A (n) by any more than rconv(A)-ϵ n results in all of Φ (n) being consumed. The dilation radius rconv(A) -ϵ n is maximal in the sense that, by dilating any less, there is guaranteed to be at least one element of Φ (n) that is not in the dilation. The distance between this one remaining element of Φ (n) and the other points in Φ (n) \ A (n) might be anywhere up to r +ϵ n , where r -ϵ n ∈ (0, rconv(A)-ϵ n ) is the dilation radius. Therefore, an erosion by at least r + ϵ n is necessary to guarantee that the resulting set is a subset of A (n) . In this sense, the bound in ( 12) is tight. The following result from [START_REF] Rodríguez Casal | A fully data-driven method for estimating the shape of a point cloud[END_REF], while interesting on its own, is instrumental in the proof of Equation [START_REF] Biermé | Lipschitz-Killing curvatures of excursion sets for two-dimensional random fields[END_REF].

Proposition 1 (Lemma 8.3 in [START_REF] Rodríguez Casal | A fully data-driven method for estimating the shape of a point cloud[END_REF]). Let r ∈ R + and let A ⊂ R d be a closed set satisfying rconv(A) < r. The set

A •r \ A contains an open subset of R d .
The relationship between Proposition 1 and Equation ( 13) is that, for r > rconv(A), as the point cloud Φ (n) becomes more dense in R d , the open subset in A •r \ A fills with points that remain in ( A

(n) r-ϵn ) -(r+ϵn) for ϵ n sufficiently small. Thus, lim n→∞ r (ϵn) ( A (n) ) < r,
and since r ∈ (rconv(A), ∞) is arbitrary, the limit is at most rconv(A). Equality then holds by Equation [START_REF] Biermé | The effect of discretization on the mean geometry of a 2D random field[END_REF]. The full proof of Theorem 3 and an alternative proof of Proposition 1 are provided in Section 5.

Remark 7. Equation ( 13) is provided without a rate of convergence. This is due to the fact that Proposition 1 provides no guarantees on the size of the open subset that can be found in A •r \A for r > rconv(A). To provide a rate of convergence, a deeper analysis is needed to understand the rate at which the size of the largest open ball in A •r \ A decreases as r ↘ rconv(A). Conversely, the bound that we construct for the reach in Section 3.2 converges to the reach at a known rate (see Theorem 4 below).

An upper bound for the reach of a set

We have already seen that r (ϵn) ( A (n) ) in ( 11) is an upper bound for the reach by Equations ( 2) and [START_REF] Biermé | The effect of discretization on the mean geometry of a 2D random field[END_REF]. In this section, we introduce another computable bound for the reach based on the expression for the β-reach in Definition 6.

The context in which one can apply this bound was introduced as setting (b) at the start of Section 3: a countable set of points A (n) is known to be included in a compact set A ⊂ R d , and its Hausdorff distance to A is known to be at most ϵ n .

A very weak regularity condition is imposed on the set A in terms of its βreach profile near 0; it is used to prove the rate at which our upper bound converges to reach(A) as A (n) → A in the Hausdorff metric.

Assumption 1. Suppose that the set A ⊂ R d is compact, and that there exists δ > 0 such that the map β → reach β (A) for β ∈ R is either constant or strictly increasing on [0, δ]. In addition, suppose that

K A := lim β↘0 reach β (A) -reach(A) β ( 14
)
exists and is finite.

Assumption 1 is imposed on the β-reach of A, as opposed to the regularity of ∂A, since the β-reach lends very naturally to the proof of Theorem 4. Moreover, Assumption 1 allows for most compact sets in R d , excluding some pathological counterexamples such as hypothetical sets admitting the β-reach profiles in Figure 11. Assumption 1 is seen to hold in all of Examples 1 through 4 in Section 2.2.2.

Theorem 4. Let A ⊆ R d be closed. For each n ∈ N + , let A (n) be a countable subset of A. Suppose that A (n) → A in the Hausdorff metric. i.e., there is a sequence (ϵ n ) n≥1 in R + tending to 0 as n → ∞ such that ϵ n ≥ d H ( A (n) , A) for all n ∈ N + . For each n ∈ N + , define the corresponding bound on reach(A) by where g ∥a2-a1∥ 2 is defined in (4). Then, rch

rch (ϵn) ( A (n) ) := inf g ∥a2-a1∥ 2 (x -ϵ n ) : a 1 , a 2 ∈ A (n) , (15)
x = δ A (n) a 1 + a 2 2 ≥ ϵ n ,
( A (n) ) ≥ reach(A), (ϵn)
for n ∈ N + . Furthermore, if A satisfies Assumption 1 and is not convex, then there exists n 0 ∈ N + such that rch (ϵn)

( A (n) ) -reach(A) ≤ (2 reach(A) + K A ) √ ϵ n , (17)
for all n ≥ n 0 , where K A is defined as in [START_REF] Blum | A transformation for extracting new descriptions of shape. Models for the perception of speech and visual form[END_REF].

Proof of Theorem 4 We begin by showing [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF] in the case where A is not convex (for A convex, the result is trivial since rch

(ϵn) ( A (n) ) = reach(A) = ∞ [39]
). Suppose that for some fixed n ∈ N + , we have ϵn ≥ d H ( A (n) , A). We write,

reach 0 (A) = inf g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 : a 1 , a 2 ∈ A ≤ inf g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 : a 1 , a 2 ∈ A (n) δ A (n) a 1 + a 2 2 ≥ ϵn . (18)
The equality in ( 18) is an application of Definition 6, and the inequality holds since the infimum is taken over a smaller subset. For any a 1 , a 2 ∈ A, there exists a projection of a1+a2 2 onto A, namely a π ∈ A, satisfying . Ticks have a spacing of ϵ n .

a π - a 1 + a 2 2 2 = δ A a 1 + a 2 2 . δ A a1+a2 2 δ A (n) p1+p2 2 δ A p1+p2
By the triangle inequality and the fact that ϵn

≥ d H ( A (n) , A), δ A (n) a 1 + a 2 2 ≤ δ A (n) (a π ) + a π - a 1 + a 2 2 2 ≤ ϵn + δ A a 1 + a 2 2 .
Rearranging gives,

δ A (n) a 1 + a 2 2 -ϵn ≤ δ A a 1 + a 2 2 . ( 19
)
Since g ∥a2-a1∥ 2 is non-increasing, the rightmost expression in (18) cannot decrease

when δ A a1+a2 2 is replaced by δ A (n) a1+a2 2 -ϵn. Thus, rch (ϵn)
( A (n) ) ≥ reach 0 (A) = reach(A),
where the latter equality is an application of Theorem 2. Now, we proceed to show [START_REF] Boissonnat | Locally uniform anisotropic meshing[END_REF]. Recall the equality in [START_REF] Chazal | A Sampling Theory for Compact Sets in Euclidean Space[END_REF], and split the analysis into two cases.

Case 1: There exists a 1 , a 2 ∈ A such that a 1 ̸ = a 2 and reach(A

) = g ∥a2-a1∥ 2 • δ A a1+a2 2 . For this pair a 1 , a 2 ∈ A there exists p 1 , p 2 ∈ A (n) satisfying ∥p 2 -a 2 ∥ 2 , ∥p 1 -a 1 ∥ 2 ≤ ϵn. This implies p 1 + p 2 2 - a 1 + a 2 2 2 ≤ ϵn. (20)
Equation ( 20) tells us that the two midpoints are close, and so their distances to A cannot differ by more than the distance between them. i.e.,

δ A a 1 + a 2 2 -δ A p 1 + p 2 2 ≤ ϵn.
Since Equation ( 19) holds for p 1 , p 2 ∈ A, and

δ A p1+p2 2 ≤ δ A (n) p1+p2 2
, we also have

δ A a 1 + a 2 2 -ϵn ≤ δ A (n) p 1 + p 2 2 ≤ δ A a 1 + a 2 2 + 2ϵn, (21)
by the triangle inequality (see Figure 12). Now, suppose that n is sufficiently large such that 2ϵn < y := δ A a1+a2 2

. Then, by [START_REF] Chazal | The "λ-medial axis[END_REF],

x := δ A (n) p1+p2 2
-ϵn > 0 and so rch (ϵn)

( A (n) ) ≤ g ∥p2-p1∥ 2 (x) = ∥p 2 -p 1 ∥ 2 2 8x + x 2 ≤ (∥a 2 -a 1 ∥ 2 + 2ϵn) 2 8x + x 2 ≤ (∥a 2 -a 1 ∥ 2 + 2ϵn) 2 8(y -2ϵn) + y + ϵn 2 . ( 22
)
The second inequality in [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in rn from noisy data samples[END_REF] holds since ∥p 2 -p 1 ∥ 2 ≤ ∥a 2 -a 1 ∥ 2 + 2ϵn, and the final inequality holds by Equation [START_REF] Chazal | The "λ-medial axis[END_REF].

Recall that reach(A) = ∥a2-a1∥ 2 2 8y + y 2 . The difference between this and the final expression in ( 22) is of the order O(ϵn), which is stronger than required.

Case 2: reach(A) < g ∥a2-a1∥ 2 • δ A a1+a2 2
for all distinct a 1 , a 2 ∈ A. By Assumption 1, for all sufficiently large n, the function reach β (A) is strictly increasing for β in a neighbourhood of βn := √ ϵn + 2ϵn. For each of these values of n,

define Ψn := {(a 1 , a 2 ) ∈ A 2 : δ A a 1 + a 2 2 ≥ βn},
which is compact by Assumption 1, and the continuous map fn : Ψn → R + by

fn (ψ 1 , ψ 2 ) = g ∥ψ2-ψ1∥ 2 • δ A ψ 1 + ψ 2 2 .
Remark that reach βn (A) = inf ψ∈Ψn fn(ψ), and so there is an element

ψ * n := (ψ * 1n , ψ * 2n ) ∈ Ψn for which reach βn (A) = fn(ψ * n ). By Definition 6, reach β (A) ≤ fn(ψ * n ) for β = δ A ψ * 1n +ψ * 2n 2 . The β-reach profile of A is thus constant on the interval βn, δ A ψ * 1n +ψ * 2n 2
by Theorem 2, but by Assumption 1, any such interval must have length 0. Therefore,

βn = δ A ψ * 1n + ψ * 2n 2 .
Again by Assumption 1,

reach βn (A) = ∥ψ * 2n -ψ * 1n ∥ 2 2 8βn + βn 2 = reach(A) + K A βn + o(βn).
Therefore,

ψ * 2n -ψ * 1n 2 2 = 8βn reach(A) + (8K A -4)β 2 n + o(β 2 n ) = 8
√ ϵn reach(A) + (16 reach(A) + 8K A -4)ϵn + o(ϵn). As seen in Case 1, Equation [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in rn from noisy data samples[END_REF], rch

(ϵn) ( A (n) ) ≤ (∥ψ * 2n -ψ * 1n ∥ 2 + 2ϵn) 2 8(βn -2ϵn) + βn + ϵn 2 = reach(A) + (2 reach(A) + K A ) √ ϵn + o( √ ϵn). □ Remark 8.
The split of the proof of Theorem 4 into two cases is natural in the context of reach estimation. Recall Theorem 3.4 in [START_REF] Aamari | Estimating the reach of a manifold[END_REF]: For a compact set A with 0 < reach(A) < ∞, there is either a bottleneck structure (two distinct points

a 1 , a 2 ∈ A such that ∥a 2 -a 1 ∥ 2 = 2δ A a1+a2 2
= 2 reach(A)) or an arc-length parametrized geodesic of A with curvature 1/reach(A). The convergence rate developed in Case 1 applies to sets whose reach is decided by a bottleneck structure, and that of Case 2 applies to sets whose reach is decided by a region of high curvature.

Remark 9. In [START_REF] Aamari | Optimal reach estimation and metric learning[END_REF], the authors provide a minimax optimal rates of convergence for statistical estimators of the reach. The authors proceed by assuming that A ⊂ R d is a C k -smooth manifold without boundary, with k ≥ 3. The minimax rates in [START_REF] Aamari | Optimal reach estimation and metric learning[END_REF]Theorem 6.6] are expressed in terms of k, the number of continuous derivatives of the underlying manifold. It is not surprising that our bound on the reach-for sets satisfying the very general Assumption 1-does not converge to the reach at the optimal rates given in [START_REF] Aamari | Optimal reach estimation and metric learning[END_REF]. Nevertheless, we do observe a similar phenomenon in that the rate of convergence derived for a set whose reach is determined by a bottleneck structure (O(ϵ n ) in Case 1 in the proof of Theorem 4) is faster than the rate when the reach is determined by a region of high curvature (O( √ ϵ n ) in Case 2).

The β-reach profiles of high-dimensional point clouds

Here, we tackle the problem of approximating the reach of smooth manifolds of low dimension embedded in high-dimensional Euclidean space. As discussed in the introduction, this setting is the focus of many works. Given a C 1 -smooth manifold M ⊂ R d of dimension m < d, we suppose that one has access to a set of points M ⊂ M from which one would like to infer reach(M ).

Recall from Definition 6 that the β-reach of a point cloud is easily computable, and the computation time does not heavily depend on the dimension d of the ambient space. The β-reach profile of a point cloud can be obtained by considering pairs of points in the point cloud and computing the distance from their midpoint to the closest neighbour in the point cloud. For a fixed number of points, the computation time for calculating the exact β-reach profile of the point-cloud scales linearly in d. Of course, the beta-reach profile of M is not identical to that of M , however, we argue here that it provides a good approximation for the values of β away from 0.

Recall that the bounds developed in Sections 3.1 and 3.2 are for subsets of R d that possibly have positive d-volume. This means that a point cloud A contained in a set A ⊂ R d can recede a distance ϵ := d H ( A, A) from the topological boundary of A. Thus, the distance from a point in A c to A can be up to ϵ shorter than the distance to the nearest point in A. Conversely, for a smooth manifold M embedded in R d , projection of an element p ∈ R d onto M is along a vector normal to M at the projection in M . Thus, the distance from p to its nearest point in M is more similar to the length of the projection vector, so in this setting, the bounds constructed previously are overly robust. Moreover, existing algorithms for computing a mesh from point cloud data can be leveraged to improve quality of the estimate of the distance to the nearest point in M , thus improving the estimate of the β-reach.

Example 5 (3-dimensional point cloud on a 2-dimensional manifold). Let M ⊂ R 3 be a section of a two-dimensional paraboloid, where its reach is decided by a point of maximal curvature at the vertex (reach(M ) = 4). Let M ⊂ M be a realization of 1500 points uniformly distributed on M shown in [START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF], and the mesh in Figure 13 (b), one may compute an improved approximation (green dashed curve) to the β-reach of the underlying manifold M (red dotted curve).

Figure 13 (a). Using the Python library pyvista [START_REF] Sullivan | PyVista: 3D plotting and mesh analysis through a streamlined interface for the Visualization Toolkit (VTK)[END_REF], we construct a mesh M( M ) over the point cloud M (see Figure 13 (b)). This allows for an improved approximation of the β-reach profile of M , The β-reach of M can be computed exactly as reach β (M ) = 4 + β 2 , for β between 0 and some positive constant. As seen in Figure 14, this is well approximated by reach β ( M ) for β > 1.3, and by reach M β ( M ) for β > 0.4; both approximations are efficiently computable from the point cloud M .

reach M β ( M ) := inf g ∥a2-a1∥ 2 (x) : a 1 , a 2 ∈ M , (23)
x = δ M( M ) a 1 + a 2 2 ≥ β .
To estimate reach(M ) from the β-reach profiles in Example 5, one can perform a linear regression on reach M β ( M ), for β in the range where the curve appears linear, and estimate the reach as the model intercept.

Although the manifold M in Example 5 is derived from a simple paraboloid, this example is representative of other two-dimensional manifolds whose reach is determined by a region of high curvature. The difference might be that the linear term in the first order approximation of the β-reach profile at β = 0 does not have a coefficent of 1/2 (see Example 4). The following two examples emphasize the applicability of this method in higher dimensions.

Example 6 (d-dimensional point cloud on a 3-dimensional manifold). Let d ≥ 4, and let M ⊂ R d be a section of the three-dimensional paraboloid defined by x 2 1 + x 2 2 + x 2 3 -12x 4 = 0, such that its reach is decided by a point of maximal curvature at the origin. It can be shown that reach β (M ) = 6 + β 2 , for β between 0 and some positive threshold. Let M ⊂ M be a realization of 3000 points, uniformly distributed on M . The Python package pyvista does not currently have methods for computing meshes in dimension higher than 3, so in this example, we do not compute reach M β ( M ) in [START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF]. Mesh generation in higher dimension is itself an active field of research [START_REF] Boissonnat | Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension[END_REF][START_REF] Boissonnat | Locally uniform anisotropic meshing[END_REF][START_REF] Edelsbrunner | Geometry and Topology for Mesh Generation[END_REF]. Nonetheless, we plot the exact β-reach profile of M in Figure 15. Remark 10. The dimension of the ambient space d ≥ 4 in Example 6 does not affect the shape of the β-reach profile of the point cloud M , computed purely in terms of distances between the points, and distances to midpoints. These distances are preserved under isometries to higher dimensional spaces. However, the number of points in M plays a role in the shape of the β-reach profile through the Hausdorff distance between M and the underlying manifold M . The exact relationship between the number of points in M and the Hausdorff distance d H ( M , M ) cannot be made precise with no prior knowledge of how the points are distributed on M -which also plays a role in the shape of the β-reach profile of M . Nonetheless, the dimension of M determines to a large extent the number of points needed to ensure that d H ( M , M ) is less than a given tolerance.

Example 7 (Two 3-dimensional hyperspheres). Let d ≥ 4, and let M ⊂ R d be the union of two three-dimensional hyperspheres of radius 2 whose centers are 12 units apart. Let M ⊂ M be a realization of 3000 points uniformly distributed on M . The β-reach profiles of M and a realization of M are shown in Figure 16.

Example 7 highlights a few nice features of the β-reach profile. That is, it adapts very well to situations where the reach is determined by a bottleneck structure, as is the case for a hypersphere. For β ∈ (2, 4], the β-reach is no longer determined by the radius of the hypersphere, but by half the distance between the surfaces of the spheres (in this case, (12-2-2)/2 = 4 units). Thus, the β-reach profile also provides information about the large scale features of the data. Notably, it gives the scales at which it becomes possible to distinguish these features from one another. Finally, recall from Remark 2 that one can read from the plot information about the critical points of the generalized gradient function. In the case of Example 7, the distances from the three critical points to M are 2, 2, and 4.

Numerical studies

In this section, we test the methods for bounding the reach and r-convexity introduced in Section 3 against numerical data. First, in Section 4.1, we study the performance of our methods on real data. Then, in Section 4.2, we test the convergence results in Theorems 3 and 4.

Aircraft data

The real data in Example 8, below, is studied using the tools developed in this document. After a short description of the data, we perform several analyses using the tools developed in Section 3.

Example 8 (Aircraft data). [START_REF] Baorui | Surface reconstruction from point clouds by learning predictive context priors[END_REF] provides a point cloud dataset that is sampled over the surface of a commercial aircraft (the white points in Figure 17 (a)).

The diameter of the raw point cloud data (which corresponds to the length of the plane) is 0.749 units. Denote the surface of the aircraft by P and the approximating point cloud by P . We are also interested in the nose of the aircraft, N ⊂ P , the surface of the first 0.056 length units of the aircraft. A two-dimensional mesh approximating N := N ∩ P is shown in Figure 17 It is possible that in an engineering practice, one may want to identify which regions of a point cloud are not r-convex for a predefined value of r. Panel (a) of Figure 17 highlights in red the regions of the plane that are certainly not r-convex for the choice of r = 0.03. The surface of the plane P is known to be two-dimensional, and so a cubic lattice of points φ with lattice spacing a = 0.004 superimposed over P will almost surely not intersect P . The discrete dilation and erosion operations in Definition 7 are well defined using the larger point cloud Φ := φ ∪ P . The red points in Figure 17 (a) are the elements of the discrete set ( P r-ϵ ) -(r+ϵ) ∩ φ, with ϵ := √ 3a/2 = sup{δ Φ (q) : q ∈ R 3 }. Since this set is not empty, one has that P is a proper subset of P •r . In addition, by [START_REF] Aamari | Estimating the reach of a manifold[END_REF], one has conclusive evidence that reach(P ) ≤ r. This example illustrates that, with this method, one can identify the regions responsible for limiting the r-convexity (and thus the reach), with a test specificity of 100%. One can improve the sensitivity of the test by decreasing the lattice spacing a. Then, other regions that are not r-convex (such as the interiors of the horizontal and vertical stabilizers) would be identified as such.

Remark that the nose of the plane is marked in red, due of course to a region of high curvature. By considering only the smooth manifold N in Example 8, corresponding to the nose of the plane, we can approximate the β-reach profile of N by reach β ( N ) in Definition 6, or by reach M β ( N ) in Equation ( 23). The resulting β-reach profiles are shown in Figure 18. From the figure, the reach is clearly seen to be much smaller than 0.03 as indicated by the r-convexity experiment. Assuming that the β-reach profile of N maintains a constant slope near 0 as seen before in Figure 14, the approximation reach(N ) ≈ 0.012 can be read from Figure 18. There are two main issues with using the reach bound in [START_REF] Boissonnat | Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension[END_REF] on the aircraft data in Example 8. First, it is expected to produce a large overestimate of reach(N ) since N is a smooth manifold (see the discussion in Section 3.3). In addition, it is impossible to know the Hausdorff distance beween N and its approximating point cloud N . Nevertheless, one can obtain a good approximation by considering the persistence diagram of growing balls centered at the points in N . The largest of the death-times of the topological features corresponds to the smallest radius for which the union of balls is homotopic to a point. This is likely to corespond closely to the Hausdorff distance d H (N, N ), and is thus a good choice for ϵ in [START_REF] Boissonnat | Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension[END_REF]. The persistence diagram, generated from the Python module ripser [START_REF] Bauer | Ripser: efficient computation of Vietoris-Rips persistence barcodes[END_REF], gives that the largest death-time is ϵ = 0.0065. From this, one calculates rch

(ϵ) ( N ) = 0.022.
Although the reach bound in [START_REF] Boissonnat | Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension[END_REF] is less appropriate to use in this setting, we will see in the following section that it (and the r-convexity bound in [START_REF] Berrendero | A multivariate uniformity test for the case of unknown support[END_REF]) is highly applicable when studying binary images.

Numerical convergence of reach and r-convexity bounds

In stochastic geometry literature, the excursion set of a random field is the subset of its domain on which the random field surpasses a predefined threshold (see [START_REF] Adler | Random fields and geometry[END_REF] for a comprehensive reference). The set in Figure 9, for example, is one realization of the excursion set of a stationary, isotropic Gaussian random field sampled on a square lattice.

The following two examples are meant to imitate the discretized excursion set of C 2 continuous random fields on square lattices (see, e.g., [START_REF] Biermé | The effect of discretization on the mean geometry of a 2D random field[END_REF][START_REF] Cotsakis | Surface area and volume of excursion sets observed on point cloud based polytopic tessellations[END_REF][START_REF] Cotsakis | On the perimeter estimation of pixelated excursion sets of 2D anisotropic random fields[END_REF]). A key feature of both examples, is that the reach and r-convexity of the sets are known, and so we can study the convergence of the bounds in Theorems 3 and 4 as the grid of sampling points becomes dense in R 2 . Each example illustrates one of the two cases mentioned in Remark 8 concerning the relationship between the reach, regions of high curvature, and bottleneck structures.

Example 9 (Reach determined by curvature). Let U := {(x, y) ∈ R 2 : y ≤ x 2 /2} ∩ B(0, 10). It is easy to check that reach(U ) = rconv(U ) = 1. Moreover, the reach is determined by a point of maximal curvature at (0, 0) ∈ U . Let (Φ (n) ) n≥1 be a sequence of square lattices over R 2 with lattice spacing a n = 0.7/n, and independent, uniformly random position and orientation. For n ∈ N + , let U (n) := U ∩ Φ (n) be the set U sampled on Φ (n) . Figure 19 depicts square subsets of realizations of U (2) and U (10) shown as binary images. Example 10 (Reach determined by a bottleneck structure). Let W := {(x, y) ∈ R 2 : |y| ≥ x 2 /2 + 1} ∩ B(0, 10). One has reach(W ) = rconv(W ) = 1, which is half the distance between its two connected components. For the sequence of square lattices (Φ (n) ) n≥1 in Example 9, let W (n) := W ∩ Φ (n) . Figure 20 depicts square subsets of realizations of W (2) and W (10) shown as binary images.

Remark 11. The choice to use sets with a reach of 1 in Examples 9 and 10 does not limit their generality. The importance lies in the scale of the sampling lattice Φ (n) relative to the reach, and the ratio of the two tends to 0 as n → ∞ in both examples. The following observation makes the gernerality of these examples even clearer: to consider the lattice of sampling points at various scales and orientations is equivalent to considering a fixed lattice and various scales and orientations of the underlying sets U and W .

For each n ∈ {2, . . . , 12}, we compute 50 independent realizations of U (n) and 50 independent realizations of W (n) . For each of the resulting discrete sets, we Fig. 22: The grey points and the white points can be seperated by a curve with arbitrarily small curvature (arbitrarily large reach). The midpoint of two grey points may be up to a distance of √ 1.25a n from another grey point, while remaining arbitrarily close to the separating curve. compute the bounds of r-convexity and reach in [START_REF] Berrendero | A multivariate uniformity test for the case of unknown support[END_REF] and ( 15) respectively. The means of the bounds are plotted in Figure 21 with empirical 95% confidence intervals. Panels (a) and (b) correspond to the results for the replications of U (n) and W (n) respectively. For the r-convexity bound,

ϵ n = a n / √ 2 is chosen since d H (Φ (n) , R 2 ) = a n / √ 2, for n ∈ N + .
For the reach bound, we set ϵ n = √ 1.25a n for reasons that are more complicated. Even though this choice of ϵ n leads to d H ( U (n) , U ) > ϵ n , or d H ( W (n) , W ) > ϵ n with positive probability, it is sufficient for the result of Theorem 4 in this case. We provide Figure 22 for some intuition, but a formal proof is omitted. δ (Ar) c (x) = r -δ A (x) < r, and so x ∈ (Ar) c ⊕ B(0, r) = (A•r) c , which proves [START_REF] Aamari | Estimating the reach of a manifold[END_REF]. What remains to be shown is that if ∂A is C 1 -smooth and (d -1)-dimensional, then rconv(A) ≤ reach(A). This inequality is shown via proof by contradiction. Suppose that (i) r > reach(A) and (ii) A •r = A.

By (i), there exists p ∈ A r+reach(A) 2 with no unique point in A closest to p. In particular, since A is closed, there exists two non-identical points a 1 , a 2 ∈ ∂A ⊆ A such that ∥p -a 1 ∥ 2 = ∥p -a 2 ∥ 2 = δ A (p) < r. Let n 1 be the unit normal vector to ∂A at a 1 , pointing towards p. Since a 1 is a limit point of A, one has A c ∩ B(a 1 , ϵ) ̸ = ∅ for all ϵ > 0. By (ii), A c = x∈(Ar) c B(x, r), and so for all ϵ > 0, there exists x ∈ (Ar) c such that

(iii) B(x, r) ∩ B(a 1 , ϵ) ̸ = ∅ and (iv) B(x, r) ∩ A = ∅.
The boundary ∂A is C 1 -smooth at a 1 , so it is easily checked that for ϵ close to 0, the locations x that satisfy both (iii) and (iv) are necessarily contained in a small neighbourhood around a 1 + rn 1 (see Figure 23). That is, there exists a mapping θ : ϵ → θ(ϵ) ∈ R + that tends to 0 as ϵ → 0, such that if x ∈ (Ar) c and ϵ ∈ R + satisfy (iii) and (iv), then x ∈ B(a

1 + rn 1 , θ(ϵ)). Note that ∥(a 1 + rn 1 ) -a 2 ∥ 2 < r since a 2 ∈ B(p, δ A (p)) ⊂ B(a 1 + rn 1 , r). Choose ϵ such that θ(ϵ) < r -∥(a 1 + rn 1 ) -a 2 ∥ 2 . Then for any x ∈ (Ar) c ∩ B(a 1 + rn 1 , θ(ϵ)), ∥x -a 2 ∥ 2 ≤ ∥x -(a 1 + rn 1 )∥ 2 + ∥(a 1 + rn 1 ) -a 2 ∥ 2 ≤ θ(ϵ) + ∥(a 1 + rn 1 ) -a 2 ∥ 2 < r.
This contradicts (iv). □ Lemma 2. Let U be an open set in R d , and let r ≥ 0. Then, Here, we present an auxiliary lemma, and use it in our proof of Proposition 1 in Section 3.1.

cl(U ) •r = cl(U ) =⇒ U •r = U. Proof of Lemma 2 By Lemma 1, item (b), U ⊆ U•r ⊆ cl(U )•r. Note also that U•r is open. Suppose that cl(U )•r = cl(U ). Then U•
which reads: the elements of A•r are the p ∈ R d such that p is not contained in any closed ball of radius r that does not intersect A. This statement is equivalent to: p / ∈ A•r if and only if there exists a closed ball of radius r that contains p but does not intersect A. Thus, we have shown that (A•r) c is equal to the complement of the RHS of [START_REF] Cholaquidis | A counter example on a borsuk conjecture[END_REF], which proves the desired result. □

Proof of Proposition 1 Let r ∈ (rconv(A), r) and fix p ∈ A • r \ A. Since A is closed, there is an open neighbourhood containing p that does not intersect A. Choose ϵ ∈ R + such that B(p, ϵ)∩A = ∅. There exists a sufficiently small δ ∈ (0, ϵ) such that for every y ∈ B(p, δ +r), there exists an x ∈ B(0, r) that satisfies B(p+x, r)\B(p, ϵ) ⊂ B(y, r).

Since p ∈ A • r , one has that B(p+x, r)\B(p, ϵ) contains an element of A by Lemma 4. By inclusion, B(y, r) contains a point in A as well. Let z ∈ B(p, δ). We have shown that z is in the right-hand side of (24), since, for all x ∈ B(0, r), one has y := z + x ∈ B(z, δ + r) by the triangle inequality, and so by previous arguments, B(z + x, r) contains an element of A. Therefore, by Lemma 4, z ∈ A•r. But z is not in A since B(p, δ) ⊆ B(p, ϵ) ⊆ A c . Therefore, z ∈ A•r \ A and so B(p, δ) ⊆ A•r \ A. □

Proof of Theorem 3 We begin by showing [START_REF] Biermé | The effect of discretization on the mean geometry of a 2D random field[END_REF]. Let n ∈ N + and fix p ∈ Φ (n) \ A (n) . If ϵn ≥ rconv(A), then (12) holds trivially. Now, let r ∈ R + be such that ϵn < r < rconv(A) so that A•r = A. We aim to show that p / ∈ ( A (n) r-ϵn ) -(r+ϵn) . Indeed, by the r-convexity of A, there exists x ∈ (Ar) c such that ∥x -p∥ 2 < r.

In addition, B(x, ϵn) ∩ A r-ϵn = ∅, so there exists q ∈ Φ (n) \ A n) is sufficiently dense such that there exists q ∈ O -(δn+2ϵn) ∩ Φ (n) . Importantly, this implies that q ∈ (Ar) -(r+δn+2ϵn) ∩ Φ (n) . By Lemma 1, for all s > r, we have (Ar) -(r+δn+2ϵn) ⊆ ((Ar) •(s-r) ) -(r+δn+2ϵn) = (As) -(s+δn+2ϵn) , and therefore q ∈ (As) -(s+δn+2ϵn) ∩ Φ (n) . Notice that As ∩ Φ (n) ⊆ A δn+s ) -(s+δn+2ϵn) . Summarizing, we have shown that there is a point q in ( A (n) δn+s ) -(s+δn+2ϵn) that is not in A (n) . By the change of variables s := s + δn + ϵn, it follows that ( A (n) s-ϵn ) -( s+ϵn) \ A (n) ̸ = ∅ for all s > r + δn + ϵn, which implies r (ϵn) ( A (n) ) ≤ r + δn + ϵn. Sending n → ∞ yields limn→∞ r (ϵn) ( A (n) ) ≤ r, and since r ∈ (rconv(A), ∞) was chosen freely, limn→∞ r (ϵn) ( A (n) ) ≤ rconv(A). This result, along with [START_REF] Biermé | The effect of discretization on the mean geometry of a 2D random field[END_REF], gives the convergence in [START_REF] Biermé | Lipschitz-Killing curvatures of excursion sets for two-dimensional random fields[END_REF]. □ Justification for Equations (8) and (9).

The reach of A is equal to the inverse of the curvature of f at x = 0 [2, Theorem 3.4]. Equation ( 8) holds since the curvature of f at x = 0 is f ′′ (0) = 2h ′ (0). Now we show [START_REF] Bauer | Ripser: efficient computation of Vietoris-Rips persistence barcodes[END_REF]. Without loss of generality, suppose h(0) = f (0) = 0. For x in a neighbourhood of 0, consider the symmetric points a 1 = (x, f (x)) and a 2 = (-x, f (x)) in A, and remark that

g ∥a2-a1∥ 2 • δ A a 1 + a 2 2 = x 2 2f (x) + f (x) 2 , (26)
since δ A a1+a2 2

= f (x). We claim without proof that for all a 1 , a

Remark 1 .

 1 Any closed subset of R d contained in a (d -1)-dimensional affine linear subspace is r-convex for all r > 0. This is easy to see since the complement of the set in the (d -1)-dimensional affine linear subspace is open, and is the union of open (d -1)-balls of radius less than r. Each (d -1)-ball can be expressed as the intersection of the affine linear subspace with an open ball of radius r in R d ; therefore, the closed subset in question can be expressed as the complement of a union of open balls of radius r and is hence r-convex.

Fig. 1 :

 1 Fig. 1: The closed set A (in grey) has rconv(A) > reach(A). The set A can be expressed as the complement of a union of open balls of radius rconv(A) whose centers lie outside the dotted black curve. The dotted red line is the medial axis M(A c ).

Fig. 2 :Fig. 3 :

 23 Fig. 2: g α (x) in Definition 5 plotted for several values of α.

2 Fig. 4 :

 24 Fig. 4: For β ∈ [0, ∞), the β-reach of A (see Definition 6) is the largest lower bound of g ∥a2-a1∥ 2 (x) (see Definition 5), for the pairs a 1 , a 2 ∈ A satisfying x ≥ β.

Fig. 6 :

 6 Fig. 6: (a): The construction of reach β (A) for β > 0 with A, the union of two rays in R d that originate from the same point. (b): The β-reach profile of A shown as a solid line. The lower bound with slope 1 is shown as a dashed line.

Fig. 7 :

 7 Fig. 7: (a): The construction of reach β (A) for β > 0 with A, a paraboloid embedded in R d . (b): The β-reach profile of A shown as a solid line. The lower bound with slope 1 is shown as a dashed line.

Fig. 9 :

 9 (a): A set A is shown as a pixelated image in grey. The set of grey pixel centers is A (n) . (b): The set ( A (n)

Fig. 11 :

 11 Fig. 11: Hypothetical β-reach profiles of sets that would not satisfy Assumption 1. (a): The β-reach profile is neither constant nor strictly increasing on any neighbourhood of 0. (b): The limit in (14) is infinite.

2 ϵnFig. 12 :

 212 Fig. 12: Visual aid for Equation (21). The real numbers δ A (n) p1+p2 2 and δ A p1+p2 2 are contained in their respective intervals, positioned relative to δ A a1+a2 2

Fig. 13 :Fig. 14 :

 1314 Fig.14:The exact β-reach profile (see Definition 6) of M in Example 5 and Figure13(a) is shown as the blue solid curve. Using the formulation in[START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF], and the mesh in Figure13(b), one may compute an improved approximation (green dashed curve) to the β-reach of the underlying manifold M (red dotted curve).

Fig. 15 :

 15 Fig. 15: The exact β-reach profile of M in Example 6 is shown as the blue solid curve. The β-reach of the underlying manifold M (a 3-dimensional paraboloid embedded in R d ) is shown as a red dotted curve.

Fig. 16 :

 16 Fig. 16: The exact β-reach profile of M in Example 7. The β-reach of the underlying manifold M is shown as a red dotted curve. Here, M is the union of two 3-dimensional hyperspheres of radius 2 embedded in R d .

Fig. 17 :

 17 Fig. 17: (a): The point cloud data P in Example 8 is used to guarantee that the r-convexity of the underlying surface of the plane P does not exceed th chosen test radius r = 0.03. The areas of the plane responsible for this restriction on the r-convexity are highlighted in red. (b): The pyvista mesh M( N ) constructed from N ⊂ P , the points at the nose of the plane.

  (b).

Fig. 18 :

 18 Fig.18: The exact β-reach profile of N in Example 8 is shown as the blue solid curve. Using the formulation in[START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF], and the mesh in Figure17(b), one may compute an improved approximation (green dashed curve) to the β-reach of the underlying (unknown) manifold N .

Fig. 19 :Fig. 20 :

 1920 Realizations of the random set U (n) in Example 9. (a): n = 2. (b): n = 10. Realizations of the random set W (n) in Example 10. (a): n = 2. (b): n = 10.

Fig. 21 :

 21 (a): The mean and 95% confidence interval for the values of r (an/ √ 2) ( U (n) ) (squares) and rch ( √ 1.25an) ( U (n) ) (circles) for 50 independent realizations of U (n) in Example 9 (b): The mean and 95% confidence interval for the values of r (an/ √ 2) ( W (n) ) (squares) and rch ( √ 1.25an) ( W (n) ) (circles) for 50 independent realizations of W (n) in Example 10.

  then clearly, x ∈ (Ar) c ⊕ B(0, r) = (A•r) c . If x ∈ Ar \ A, then by Federer [39, Corollary 4.9],

Lemma 3 .Remark 12 .

 312 r is an open subset of cl(U ) that contains all of the interior points of cl(U ). Therefore, U•r = U .□ Let A ⊆ R d be closed. It holds thatrconv(cl(A c )) = sup{r ∈ R : A •-r = A} Proof of Lemma 3 By Lemma 2 and item (a) in Lemma 1, {r ∈ R : cl(A c )•r = cl(A c )} ⊆ {r ∈ R : (A c )•r = A c } = {r ∈ R : A •-r = A}. Therefore, rconv(cl(A c )) ≤ sup{r ∈ R : A •-r = A}. Now we show the reverse inequality. Let r, r ∈ R + satisfy r > r > rconv(cl(A c )). By Proposition 1, cl(A c ) • r \ cl(A c) contains a ball of radius ϵ for some ϵ ∈ (0, r). Now, let δ = min(ϵ, 2(r -r)). Note that (A c ) δ/2 ⊇ cl(A c ), and so by Lemma 1, ((A c ) δ/2 ) •r-δ/2 = ((A c )r) -(r-δ/2) ⊇ cl(A c ) •r-δ/2 ⊇ cl(A c ) • r ,which contains the ball of radius ϵ. Now, eroding by δ/2 preserves a ball of radiusϵ -δ/2 ≥ ϵ/2. That is, (((A c ) δ/2 ) •r-δ/2 ) -δ/2 = (A c )•r contains a ball of radius ϵ/2 that does not intersect cl(A c ), and so (A c )•r ̸ = A c which implies the desired A •-r ̸ = A by Lemma 1, item (a). □ Proof of Corollary 1 If rconv(A) = 0, then by Theorem 1, reach(A) = 0 and we are done. Now assume rconv(A) > 0 and rconv(cl(A c )) > 0, then by Lemma 3, there exists δ > 0 such that A•r = A for all r ∈ (-δ, δ). Theorem 1 in [53] states that ∂A is (d -1)-dimensional and C 1 -smooth, which implies Equation 3 in our Theorem 1. □ Proof of Corollary 2 By Theorem 1, the statement holds if ∂(Aϵ) is C 1 -smooth and (d -1)-dimensional. Otherwise, if there is indeed a point c on the boundary of Aϵ = a∈A B(a, ϵ) that does not have a continuous derivative, then c is an intersection point of two distinct d-spheres centered in A of radius ϵ. In other words, c is at cusp that points inwards towards the interior of Aϵ, making reach(Aϵ) = rconv(Aϵ) = 0.□ Remark that (A ϵ ) •-ϵ = A ϵ . Therefore, if the hypotheses of Corollary 2 are strengthened to those of Corollary 1, then the proof of Corollary 2 holds by applying Theorem 1 in[START_REF] Walther | On a Generalization of Blaschke's Rolling Theorem and the Smoothing of Surfaces[END_REF] followed by our Theorem 1.

Lemma 4 . 24 )

 424 For closed A ⊆ R d and r ∈ R + , it holds thatA •r = p ∈ R d : ∀x ∈ B(0, r), B(p + x, r) ∩ A ̸ = ∅ . (Proof of Lemma 4 By manipulating the expressions in Definition 1, one obtains

  such that ∥q -x∥ 2 ≤ ϵn. Therefore, by the triangle inequality, ∥q -p∥ 2 ≤ r +ϵn, which impliesδ Φ (n) \ A (n) r-ϵn (p) ≤ r + ϵn. Thus, p / ∈ ( A (n) r-ϵn ) -(r+ϵn) as desired. Now, to prove (13), first fix r > rconv(A). To simplify notation, let δn := d H ( A (n) , A). By Proposition 1, there exists an open subset O ⊆ A•r \A that contains a closed ball of radius δn 0 +3ϵn 0 for sufficiently large n 0 ∈ N + . Let n ≥ n 0 . The point cloud Φ (

  implies (As) c ⊇ Φ (n) \ A (n)s+δn and thus (As) -(s+δn+2ϵn) ∩Φ (n) ⊆ ( A (n)

  Definition 3 (The medial axis). Let O ⊆ R d be open. Its medial axis M(O) is the set of points in O with at least two closest points in ∂O.

Acknowledgements

I extend my gratitude to Elena Di Bernardino and Thomas Opitz for their attentive and indispensable guidance. Thank you to the anonymous reviewers, who significantly helped to improve the communication of ideas in this manuscript. This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.

Computable bounds for the reach and r-convexity of subsets of R d A linear regression on the log-log plot of the sample means of the data in Figure 21 (a) shows that

59 and E[ rch

These empirical convergence rates -O(ϵ 0.59 n ) for the bound on rconv(U ) and O(ϵ 0.62 n ) for the bound on reach(U ) -are both slightly faster than the predicted rate of O( √ ϵ n ) established in [START_REF] Boissonnat | Locally uniform anisotropic meshing[END_REF] for the bound on the reach. Since the reach of U is determined by a region of maximal curvature, the convergence rate is governed by the analysis in Case 2 in the proof of Theorem 4.

For the data in panel (b) of Figure 21, 20 and E[ rch

Again, these empirical convergence rates are faster than the anticipated rate of O(ϵ n ) established for the bound on the reach in Case 1 (i.e., when the reach is determined by a bottleneck structure) in the proof of Theorem 4.

Proofs and technical results

Here, we provide proofs and auxiliary lemmas that support the results in Sections 2 and 3.

Proof of Theorem 1 We begin by showing [START_REF] Aamari | Estimating the reach of a manifold[END_REF]. Suppose that r ∈ (0, reach(A)). By Lemma 1, A ⊆ A•r, so it suffices to show that

. In the language of the β-reach, this is equivalent to

There is a δ > 0 such that h has an inverse on [0, δ], and so for β ∈ [0, δ], choose x such that f (x) = β. Remark that

by Taylor's theorem. Plugging into [START_REF] Clarke | Proximal Smoothness and the Lower-C 2 Property[END_REF] and applying [START_REF] Colesanti | Geometric and isoperimetric properties of sets of positive reach in E d[END_REF], one obtains (9).