Jisu Kim
email: jisu.kim@inria.fr

Jaehyeok Shin
email: shinjaehyeok@cmu.edu

Frédéric Chazal
email: frederic.chazal@inria.fr

Alessandro Rinaldo
email: arinaldo@cmu.edu

Larry Wasserman

Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex

Keywords: 2012 ACM Subject Classification Mathematics of computing → Algebraic topology; Theory of computation → Computational geometry Computational topology, Homotopy reconstruction, Homotopy Equivalence, Vietoris-Rips complex, Čech complex, Reach, µ-reach, Nerve Theorem, Offset, Double offset, Consistency

We derive conditions under which the reconstruction of a target space is topologically correct via the Čech complex or the Vietoris-Rips complex obtained from possibly noisy point cloud data. We provide two novel theoretical results. First, we describe sufficient conditions under which any non-empty intersection of finitely many Euclidean balls intersected with a positive reach set is contractible, so that the Nerve theorem applies for the restricted Čech complex. Second, we demonstrate the homotopy equivalence of a positive µ-reach set and its offsets. Applying these results to the restricted Čech complex and using the interleaving relations with the Čech complex (or the Vietoris-Rips complex), we formulate conditions guaranteeing that the target space is homotopy equivalent to the Čech complex (or the Vietoris-Rips complex), in terms of the µ-reach. Our results sharpen existing results.

Introduction

A fundamental task in topological data analysis, geometric inference, and computational geometry is that of estimating the topology of a set X ⊂ R d based on a finite collection of data points X that lie in it or in its proximity. This problem naturally occurs in many applications area, such as cosmology [30], time series data [28], machine learning [START_REF] Tamal | Curve and Surface Reconstruction: Algorithms with Mathematical Analysis[END_REF], and so on.

A natural way to approximate the target space is to consider an r-offset of the data points, that is, to take the union of the open balls of radius r > 0 centered at the data points. Under appropriate conditions, by the Nerve theorem [START_REF] Alexandroff | Über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung[END_REF] this offset is topologically equivalent to the target space X via the Čech complex [START_REF] Björner | Topological Methods[END_REF]23]. For computational reasons, the Alpha shape complex may be used instead, which is homotopy equivalent to the Čech complex [20]. To further speed up calculations, and in particular if the data are high dimensional, the Vietoris-Rips complex may be preferable as only the pairwise distances between the data points are used.

To guarantee that the topological approximation based on the data points recovers correctly the homotopy type of X, it is necessary that the data points are dense and close to the target space, and that the radius parameter used for constructing the Čech complex or the Vietoris-Rips complex be of appropriate size.

The conditions require the offset r to be lower bounded by a constant times the Hausdorff distance between the target space and the data points, and upper bounded by another constant times a measure of the size of the topological features of the target space. Originally, the topological feature size was described as a sufficiently small number, for the Vietoris-Rips complex in [24,25]. Then, the topological feature size was expressed in terms of the reach of X: see, for the Čech complex, in [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF]27]. Subsequently, the notion of µ-reach was put forward to allow for more general target spaces: the condition for the Čech complex is studied in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF][START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF], and the condition for the Vietoris-Rips complex is studied in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. Also, the radii parameters are allowed to vary across the data points in [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF]. For the case when the target space equals the data points, the conditions for the Čech complex or the Vietoris-Rips complex is studied in [START_REF] Adamaszek | Metric reconstruction via optimal transport[END_REF][START_REF] Adams | Metric thickenings of euclidean submanifolds[END_REF]. When the offset r is beyond the topological feature size so that the homotopy equivalence does not hold, the homotopy type of the Vietoris-Rips complex was studied for the circle in [START_REF] Adamaszek | The Vietoris-Rips complexes of a circle[END_REF].

In this paper, we derive conditions under which the homotopy type of the target space is correctly recovered via the Čech complex or the Vietoris-Rips complex, in terms of the Hausdorff distance and the µ-reach of the target space. To tackle this problem, we provide two novel theoretical results. First, we describe sufficient conditions under which any nonempty intersection of finitely many Euclidean balls intersected with a set of positive reach is contractible, so that the Nerve theorem applies for the restricted Čech complex. Second, we demonstrate the homotopy equivalence of a positive µ-reach set and its offsets. These results are new and of independent interest.

Overall, our new bounds offer significant improvements over the previous results in [27, 6] and are sharp: in particular, they achieve the optimal upper bound for the parameter of the Čech complex and the Vietoris-Rips complex under a positive reach condition. We will provide a detailed comparison of our results with existing ones in Section 6. and details. Throughout the paper, we let X and X be subsets of R d . For x, y ∈ R d , we let d(x, y) := x -y be the Euclidean distance with • being the Euclidean norm. Let d(x, X) = inf y∈X d(x, y) denotes the distance from a point x to a set X, and let d X : R d → R be the distance function x → d(x, X). For r > 0, we let B X (x, r) := {y ∈ X : d(x, y) < r} be the open restricted ball centered at x ∈ R d of radius r > 0. For r > 0, we let X r be an r-offset of a set X defined by the collection of all points that are within r distance to X, that is, X r := x∈X B R d (x, r). Finally, for two sets X, Y ⊂ R d , we let d H (X, Y ) := inf{r > 0 : X ⊂ Y r and Y ⊂ X r } be the Hausdorff distance between X and Y .

Simplicial complex and Nerve theorem

A natural way to approximate the target space X with the data points X is to take the union of open balls centered at the data points. In detail, let r = {r x , x ∈ X } ∈ R X + be pre-specified radii and consider the union of restricted balls x∈X B X (x, r x ).

(

) 1
Though we allow for the points in X to lie outside X, we will assume throughout that B X (x, r x ) = ∅ for all x ∈ X .

To infer the topological properties of the union of balls in [START_REF] Aamari | Estimating the reach of a manifold[END_REF], we rely on a simplicial complex, which can be seen as a high dimensional generalization of a graph. Given a set V , an (abstract) simplicial complex is a collection K of finite subsets of V such that α ∈ K and β ⊂ α implies β ∈ K. Each set α ∈ K is called its simplex, and each element of α is called a vertex of α.

A simplicial complex encoding the topological properties of the union of balls in (1) is the Čech complex.

Definition 1 (Čech complex). Let X , X be two subsets and r ∈ R X + . The (weighted) Čech complex Čech X (X , r) is the simplicial complex Čech X (X , r) :=

   σ = {x 1 , . . . , x k } ⊂ X : k j=1 B X (x j , r xj ) = ∅    .
(2)

Computing the Čech complex requires computing all possible intersections of the balls. To further speed up the calculation, we only check the pairwise distances between the data points and instead build the Vietoris-Rips complex.

Definition 2 (Vietoris-Rips complex). Let X , X be two subsets and r ∈ R X + . The weighted Vietoris-Rips complex Rips(X , r) is the simplicial complex defined as Rips(X , r) := σ ⊂ X : d(x i , x j ) < r xi + r xj , for all x i , x j ∈ σ .

(

) 3
The ambient Čech complex in (2) (that is, X = R d ) and the Vietoris-Rips complex in (3) have the following interleaving relationship when all radii are equal (e.g., see Theorem 2.5 in [START_REF] De | Coverage in sensor networks via persistent homology[END_REF]). That is, when r x = r > 0 for all x ∈ X , then

Čech R d (X , r) ⊂ Rips(X , r) ⊂ Čech R d X , 2d d + 1 r . ( 4
)
This interleaving relation is extended to the case of different radii in Lemma 16.

The union of balls in (1) and the Čech complex in (2) are homotopy equivalent under appropriate conditions. This remarkable result is precisely the renowned nerve theorem [START_REF] Alexandroff | Über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung[END_REF][START_REF] Björner | Topological Methods[END_REF]23], which we recall next. We first introduce the nerve, which is a more abstract notion of the Čech complex. Definition 3 (Nerve). Let U = {U α } be an open cover of a given topological space X. The nerve of U, denoted by N (U), is the abstract simplicial complex defined as

N (U) =    {U 1 , . . . , U k } ⊂ U : k j=1 U j = ∅    .
The nerve theorem prescribes conditions under which the nerve of an open cover of X is homotopy equivalent to X itself.

Theorem 4 (Nerve theorem). Let X be a paracompact space and U be an open cover of X. If every nonempty intersection of finitely many sets in U is contractible, then X is homotopy equivalent to the nerve N (U).

Thus, in order to conclude that the Čech X (X , r) complex in [START_REF] Adamaszek | The Vietoris-Rips complexes of a circle[END_REF] has the same homotopy type as X, it is enough to show, by the nerve theorem, that the union of restricted balls x∈X B X (x, r x ) covers the target space X and that any arbitrary non-empty intersection of restricted balls is contractible. The difficulty in establishing the latter, more technical, condition lies in the fact that it is not clear a priori what properties of X will imply it. If

The reach

First introduced by [21], the reach is a quantity expressing the degree of geometric regularity of a set. In detail, given a closed subset X ⊂ R d , the medial axis of X, denoted by Med(X), is the subset of R d consisting of all the points that have at least two nearest neighbors in X. Formally, Med(X) = x ∈ R d \ X : there exist q 1 = q 2 ∈ X,

||q 1 -x|| = ||q 2 -x|| = d(x, X) , (5)
The reach of X is then defined as the minimal distance from X to Med(X).

Definition 5. The reach of a closed subset X ⊂ R d is defined as

τ X = inf q∈X d (q, Med(X)) = inf q∈X,x∈Med(X) ||q -x||. ( 6
)
Some authors [see, e.g. 27, 29] refer to τ -1 X as the condition number. From the definition of the medial axis in [START_REF] Alexandroff | Über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung[END_REF], the projection π X (x) = arg min p∈X p -x onto X is well defined (i.e. unique) outside M ed(X). In fact, the reach is the largest distance ρ ≥ 0 such that π X is well defined on the ρ-offset x ∈ R d : d(x, X) < ρ . Hence, assuming the set X has positive reach can be seen as a generalization or weakening of convexity, since a set X ⊂ R d is convex if and only if τ X = ∞. In the next section, we describe how to use the reach condition to ensure that the union of restricted balls is contractible, which in turn allows us to apply the Nerve theorem to recover the homotopy type of the target space X.

Γ X (x) X Θ X (x) x ∇ X (x) = x-Θ X (x) d X (x) d X (x)
1

Figure 1 The graphical illustration for the generalized gradient ∇ X (x), from [START_REF] Chazal | Shape smoothing using double offsets[END_REF][START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF].

For a non-smooth target space, the reach of the space can be zero. In this case, we can deploy a more general notion of feature size, called µ-reach, introduced by [START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF]. For any point x ∈ R d \ X, let Γ X (x) be the set of points in X closest to x. Let Θ X (x) be the center of the unique smallest closed ball enclosing Γ X (x). Then, for x ∈ R d \ X, the generalized gradient of the distance function d X is defined as

∇ X (x) = x -Θ X (x) d X (x) , (7)
and set ∇ X (x) = 0 for x ∈ X. See Figure 1 for a graphical illustration. Then, for µ ∈ (0, 1], the µ-medial axis of X is defined as

Med µ (X) = x ∈ R d \ X : ∇ X (x) < µ , (8)
Finally, the µ-reach of X is defined as the minimal distance from X to Med µ (X).

Definition 6. The µ-reach of a closed subset X ⊂ R d is defined as

τ µ X = inf q∈X d (q, Med µ (X)) = inf q∈X,x∈Medµ(X) ||q -x||. ( 9
)
Note that if µ = 1, the corresponding µ-reach equals to the reach of X. Two offsets X r and X s of the target space X are topologically equivalent if they are free of critical points of the distance function d X in the sense specified below (see e.g., [22] or Proposition 3.4 in [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in R n from noisy data samples[END_REF]).

Lemma 7 (Isotopy Lemma). Let X ⊂ R d be a set, and for r, s > 0 with s ≤ r, let X r and X s be two offsets of X. Suppose the distance function d X does not have a critical point on X r \X s , that is, ∇ X (x) = 0 for all x ∈ X r \X s where ∇ X is from [START_REF] Björner | Topological Methods[END_REF]. Then X r and X s are homeomorphic.

Note that requiring ∇ X (x) = 0 for all x ∈ X r \X s is weaker than the µ-reach condition τ µ X > r for any µ ∈ (0, 1]. One of the main results of the paper, given in Theorem 12, generalizes this topological relation to the relation between the target space and its offset under a stronger positive µ-reach condition.

x 1 x 2

Figure 2

An example in which the union of balls is different from the underlying space in terms of the homotopy. In the figure, the union of balls deformation retracts to a circle, hence its homotopy is different from the underlying semicircle.

Restricted versus Ambient balls

It is important to point out that the nerve theorem needs not to be applied to the Čech complex built using ambient, as opposed, to restricted balls. In particular, the homotopy type of X, may not be correctly recovered using unions of ambient balls even if the point cloud is dense in X and the radii of the balls all vanish. We elucidate this point in the next example. Below, B R d (x, r) denotes the open ambient ball in R d centered at x and of radius r > 0.

Example 8. Let X = (∂B R 2 (0, 1)) ∩ {x ∈ R 2 : x 2 ≥ 0} be a semicircle in R 2 .
Let ∈ (0, 1) be fixed, and x 1 , x 2 be points on X satisfying

x 1 -x 2 ∈ √ 4 -2 , 2 . Then, B R 2 (x 1 , ) ∩ B R 2 (x 2 ,
) is nonempty but has an empty intersection with X. Now, choose

ρ < d(X, B R 2 (x 1 , ) ∩ B R 2 (x 2 ,
)) and choose X 0 ⊂ X be dense enough so that x∈X0 B R 2 (x, ρ) covers X. Now, consider the union of ambient balls

B R 2 (x 1 , ) B R 2 (x 2 , ) x∈X0 B R 2 (x, ρ) . ( 10
) Then from the fact ρ < d (X, B R 2 (x 1 , ) ∩ B R 2 (x 2 , )) and x∈X0 B R 2 (x, ρ) is a covering of X,
we have that the union of balls in [START_REF] Chazal | Robust topological inference: Distance to a measure and kernel distance[END_REF] is homotopy equivalent to a circle, hence its homotopy is different from the semicircle X. Note that the above construction holds for all choices of ∈ (0, 1). Since ρ → 0 as → 0, X 0 can be arbitrary dense in X. See Figure 2.

The nerve theorem for Euclidean sets of positive reach

In order to apply the nerve theorem to the Čech complex built on restricted balls, it is enough to check whether any finite intersection of the restricted balls k j=1 B X (x j , r xj ) is contractible (since X is a subset of R d and is endowed with the subspace topology, it is paracompact.).

Theorem 9 is one of the main statements of this paper and shows that, if a subset X ⊂ R d has a positive reach τ > 0, any non-empty intersection of restricted balls is contractible if the radii are small enough compared to τ . Theorem 9. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then, if

r x ≤ τ 2 + (τ -d X (x)) 2 1 + (1 -) 2 X x 1 x 2 B X (x 1 , r) B X (x 2 , r) 0 1 r r 1 - Figure 3 An example in which B X (x1, r) B X (x2, r) is not homotopy equivalent to Čech X (X , r) where X = x ∈ R 2 : x 2 = 1 , x1 = (-1 + , 0), x2 = (1 -, 0), X = {x1, x2}, and r > 1 + (1 -) 2 , for any > 0.
for all x ∈ X , any nonempty intersection of restricted balls x∈I B X (x, r x ) for I ⊂ X is contractible.

Therefore, by combining Theorem 9 and the Nerve Theorem (Theorem 4), we can establish that the topology of the subspace X can be recovered by the corresponding restricted Čech complex Čech X (X , r), provided the radii of the balls are not too large with respect to the reach. This result is summarized in the following corollary.

Corollary 10 (Nerve Theorem on the restricted balls). Under the same condition of Theorem 9, suppose r x ≤ τ 2 + (τ -d X (x)) 2 for all x ∈ X , then the union of restricted balls x∈X B X (x, r x ) is homotopy equivalent to the restricted Čech complex Čech X (X , r). If, in addition, the union of restricted balls covers the target space X, that is,

X ⊂ x∈X B X (x, r x ), ( 11
)
then X is homotopy equivalent to the restricted Čech complex Čech X (X , r).

The reach condition r x ≤ τ 2 + (τ -d X (x)) 2 is tight as the following example shows.

Example 11. Let X be the unit Euclidean sphere in R d , and fix > 0. Let x 1 := (1 -, 0, . . . , 0), x 2 := (-1 + , 0, . . . , 0) ∈ R d , and set X := {x 1 , x 2 }. For a unit Euclidean sphere, the reach is equal to its radius 1. Therefore

, if r = (r 1 , r 2 ) ∈ 0, 1 + (1 -) 2 2 then B X (x 1 , r 1 ) B X (x 2 , r 2 ) is homotopy equivalent to Čech X (X , r) by Corollary 10. However, if r 1 , r 2 > 1 + (1 -) 2 , B X (x 1 , r 1 ) B X (x 2 , r 2 ) X but Čech X (X , r) 0. Figure 3 illustrates the 2-dimensional case.

Deformation retraction on positive µ-reach

The positive reach condition is critical for the nerve theorem on the restricted Čech complex. However, it is not easily generalized to the positive µ-reach condition. Instead, we find a positive reach set that approximates the positive µ-reach set. And to show their homotopy Figure 4 An example where X r does not deformation retracts to X. X is a topologist's sine circle, that is,

X = X0 ∪ X1 ∪ X2, with X0 = x, sin π x ∈ R 2 : x ∈ (0, 1] , X1 = {0} × [-1, 1]
, and X2 is a sufficiently smooth curve joining (0, 1) and (1, 0) and meeting X0 ∪ X1 only at its endpoints.

equivalence, we discover the topological relation between the positive µ-reach set and its offset.

The homeomorphic relation between two offsets X r and X s of the target space X in Lemma 7 does not hold in general between the target space and its offset, but a weakened topological relation holds under a stronger condition on the target space. Theorem 12, which is one of the main results in our paper, asserts that if the target space X has a positive µ-reach, then the offset X r deformation retracts to X when the offset size is not large, and in particular, they are homotopy equivalent.

Theorem 12. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0. For r ≤ τ µ , the r-offset X r deformation retracts to X. In particular, X and X r are homotopy equivalent.

The positive µ-reach condition r ≤ τ µ in Theorem 12 is critical and cannot be weakened to ∇ X (x) = 0 for all x ∈ X r \X as in Lemma 7. Indeed, Example 13 shows that the offset does not deformation retract to the target space although ∇ X (x) = 0 for all x ∈ R d .

Example 13. Let X ⊂ R 2 be a topologist's sine circle, that is, X = X 0 ∪ X 1 ∪ X 2 , with X 0 = x, sin π x ∈ R 2 : x ∈ (0, 1] , X 1 = {0} × [-1, 1]
, and X 2 is a sufficiently smooth curve joining (0, 1) and (1, 0) and meets X 0 ∪ X 1 only at its endpoints. See Figure 4. Then, τ µ X = 0 for any µ ∈ (0, 1] but ∇ X is nonzero for all x ∈ R 2 \X. Now, H 1 (X) = 0, but for any sufficiently small r > 0, X r is homeomorphic to an annulus B R 2 (0, 2)\B R 2 (0, 1) and hence H 1 (X r ) = Z. Hence X r cannot deformation retract to X.

Using Theorem 12, we find a positive reach set that approximates the positive µ-reach set. The set we will use is the double offset [START_REF] Chazal | Shape smoothing using double offsets[END_REF]. Recall that, for r > 0, an r-offset X r of a set X is the collection of all points that are within r distance to X, that is,

X r := x∈X B R d (x, r).
The double offset is to take offset, take complement, take offset, and take complement, that is, for s ≥ t > 0, X s,t := (((X s ) ) t ) . Roughly speaking, it is to inflate your set first, and then deflate your set, so that sharp corners become smooth. See [START_REF] Chazal | Shape smoothing using double offsets[END_REF] for more details. To set up the homotopy equivalence of the positive µ-reach set and its double offset, we need another tool for finding the homotopy equivalence of the complement set. This is done in the next lemma. Lemma 14. Let X ⊂ R d be a subset with positive reach τ > 0. For r ≤ τ , X deformation retracts to (X r ) . In particular, X and (X r ) are homotopy equivalent. Now, combining Theorem 12 and Lemma 14 gives the desired homotopy equivalence between the target set of positive µ-reach and its double offset, where the double offset has a positive reach.

Corollary 15. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0. For s, t > 0 with t ≤ s, let X s,t := (((X s ) ) t ) be the double offset of X. If s < τ µ and t < µs, then X s,t and X are homotopy equivalent, and the reach of X s,t is greater than or equal to t, that is, τ X s,t ≥ t.

Homotopy Reconstruction via Cech complex and Vietoris-Rips complex

Next, we derive conditions under which the homotopy type of the target space is correctly recovered via the Čech complex and the Vietoris-Rips complex. We first extend the interleaving relationship of the ambient Čech complex and the Vietoris-Rips complex in (4) to the different radii case in Lemma 16.

Lemma 16. Let X ⊂ R d be a set of points and r = {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then,

Čech R d (X , r) ⊂ Rips(X , r) ⊂ Čech R d X , 2d d + 1 r .
To recover the homotopy of the target set via the ambient Čech complex and the Vietoris-Rips complex, we utilize the restricted Čech complex. Hence, we set up the interleaving relationship between the restricted Čech complex and the ambient Čech complex in Lemma 17 and between the restricted Čech complex and the Vietoris-Rips complex in Corollary 18.

Lemma 17. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let r = {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then,

Čech X (X , r) ⊂ Čech R d (X , r) ⊂ Čech X (X , r ), where r = {r x > 0 : x ∈ X } with r x = 2τ (r 2 x + d X (x) (2τ -d X (x))) τ + τ 2 -(r 2 x + d X (x) (2τ -d X (x))) -d X (x) (2τ -d X (x)). Equivalently, Čech R d (X , r ) ⊂ Čech X (X , r) ⊂ Čech R d (X , r),
where r = {r x > 0 : x ∈ X } with

r x = τ 2 -d X (x)(2τ -d X (x)) - (2τ 2 -r 2 x -d X (x)(2τ -d X (x))) 2 4τ 2 .
Corollary 18. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let r = {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then, Čech X (X , r) ⊂ Rips(X , r) ⊂ Čech X (X , r ), where r = {r x > 0 : x ∈ X } with

r x = 2τ 2d d+1 r 2 x + d X (x) (2τ -d X (x)) τ + τ 2 -2d d+1 r 2 x + d X (x) (2τ -d X (x)) -d X (x) (2τ -d X (x)).
Combining Nerve Theorem on the restricted balls (Corollary 10) with the covering condition [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in R n from noisy data samples[END_REF] and Lemma 17 or Corollary 18 gives the following commutative diagram:

X y y Čech X (X , r) % % / / Čech X (X , r ) e e S 9 9
, ( 12
)
where S is either the ambient Čech complex Čech R d (X , r) or the Vietoris-Rips complex Rips(X , r). Using this diagram, we develop the homotopy equivalence between the target space and either the ambient Čech complex or the Vietoris-Rips complex. First, Theorem 19 asserts that when the target space of positive reach is densely covered by the data points and if they are not too far apart, the ambient Čech complex can be used to recover the homotopy type.

Theorem 19. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a closed discrete set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := min x∈X {r x } and r max := max x∈X {r x }, and let := max{d X (x) : x ∈ X }. Suppose X is covered by the union of balls centered at x ∈ X and radius δ as

X ⊂ x∈X B R (x, δ). ( 13
)
Suppose that the maximum radius r max is bounded as

r max ≤ τ -. ( 14
)
Also, suppose δ satisfies the following condition:

δ + r 2 max -l2 + (2τ -) -((τ -) 2 -r 2 max + l2 + (τ -l) 2 ) τ τ 2 -rδ,c -1 ≤ r min , d 2(d + 1)
r max r min    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    ≤ r min , ( 15
) l := 1 2 r min -τ + (τ -) 2 -r 2 max -δ , l := τ -(τ -) 2 -r 2 max + l, r2 δ,c := min δ 2 + (2τ -), 1 2 (r 2 max -l2 + (2τ -) + l(2τ -l)) , r min := τ 2 -(2τ -) - (2τ 2 -r 2 min -(2τ -)) 2 4τ 2 , r2 b := 2τ (r min ) 2 + (2τ -) τ + τ 2 -((r min ) 2 + (2τ -)) , r2 δ,b := min δ 2 + (2β -), 1 2 r2 b .
Then X is homotopy equivalent to the ambient Čech complex Čech R d (X , r).

A similar approach also gives the homotopy equivalence between the target space and the Vietoris-Rips complex when the target space has positive reach.

Theorem 20. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a closed discrete set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := min x∈X {r x } and r max := max x∈X {r x }, and let := max{d X (x) : x ∈ X }. Suppose X is covered by the union of balls centered at x ∈ X and radius δ as

X ⊂ x∈X B R (x, δ). ( 16
)
Suppose that the maximum radius r max is bounded as

r max ≤ d + 1 2d (τ -) . ( 17
)
Also, suppose δ satisfies the following condition:

r2 b (r max ) -(2τ 2 -r2 b (r max ))   τ τ 2 -r2 δ,b (r max ) -1   + 2δ ≤ 2r min , d 2(d + 1)    r2 b (r min ) -(2τ 2 -r2 b (r min ))   τ τ 2 -r2 δ,b (r min ) -1   + 2δ    ≤ r min , ( 18
)
where

r min := τ 2 -(2τ -) - (2τ 2 -r 2 min -(2τ -)) 2 4τ 2 , r2 b (t) := 2τ t 2 + (2τ -) τ + τ 2 -(t 2 + (2τ -)) , r2 δ,b (t) := min δ 2 + (2τ -), 1 2 r2 b (t) .
Then X is homotopy equivalent to the Vietoris-Rips complex Rips(X , r).

Remark 21. Compared to the restricted Čech complex (Corollary 10), the covering condition in [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF] or ( 16) is more critical for the ambient Čech complex (Theorem 19) or the Vietoris-Rips complex (Theorem 20). Although the restricted Čech complex Čech X (X , r) is still homotopy equivalent to the union of restricted balls x∈X B X (x, r x ) without the covering condition in [START_REF] Chazal | Weak feature size and persistent homology: Computing homology of solids in R n from noisy data samples[END_REF], such homotopy equivalence does not hold for the ambient Čech complex or the Vietoris-Rips complex. This is since the upper triangle of the diagram in [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF] only holds under the covering condition in [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF] or [START_REF] De | Coverage in sensor networks via persistent homology[END_REF]. Furthermore, the covering condition in [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF] or [START_REF] De | Coverage in sensor networks via persistent homology[END_REF] is denser in that δ < r x for all x ∈ X , to construct an additional homotopy equivalence on the lower triangle of the diagram in [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF].

The homotopy equivalences in Theorem 19 and 20 for the positive reach case is extended to the positive µ-reach case by applying Corollary 15 with the double offset of the target space. Corollary 22 shows that when the double offset of the target space of positive µ-reach is densely covered by the data points and if they are not too far apart, either the ambient Čech complex or the Vietoris-Rips complex can be used to recover the homotopy type of X.

Corollary 22. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0 and let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := min x∈X {r x } and r max := max x∈X {r x }. Let s, t, ≥ 0 with t µ < s < τ µ , and let Y := (((X s ) ) t ) be the double offset, with d Y (x) ≤ for all x ∈ X . Suppose Y is covered by the union of balls centered at x ∈ X and radius δ as

Y ⊂ x∈X B R (x, δ).
(i) Suppose r max ≤ t -, and δ satisfies the following condition:

δ + r 2 max -l2 + (2t -) -((t -) 2 -r 2 max + l2 + (t -l) 2 ) t t 2 -rδ,c -1 ≤ r min , d 2(d + 1)
r max r min    r2 b -(2t 2 -r2 b )   t t 2 -r2 δ,b -1   + 2δ    ≤ r min ,
where

l := 1 2 r min -t + (t -) 2 -r 2 max -δ , l := t -(t -) 2 -r 2 max + l, r2 δ,c := min δ 2 + (2t -), 1 2 (r 2 max -l2 + (2t -) + l(2t -l)) , r min := t 2 -(2t -) - (2t 2 -r 2 min -(2t -)) 2 4t 2 , r2 b := 2t (r min ) 2 + (2t -) t + t 2 -((r min ) 2 + (2t -)) , r2 δ,b := min δ 2 + (2t -), 1 2 r2 b .
Then X is homotopy equivalent to the ambient Čech complex Čech R d (X , r).

(ii) Suppose r max ≤ d+1 2d (t -), and δ satisfies the following condition:

r2 b (r max ) -(2t 2 -r2 b (r max ))   t t 2 -r2 δ,b (r max ) -1   + 2δ ≤ 2r min , d 2(d + 1)    r2 b (r min ) -(2t 2 -r2 b (r min ))   t t 2 -r2 δ,b (r min ) -1   + 2δ    ≤ r min ,
where

r min := t 2 -(2t -) - (2t 2 -r 2 min -(2t -)) 2 4t 2 , r2 b (t) := 2t t 2 + (2t -) t + t 2 -(t 2 + (2t -)) , r2 δ,b (t) := min δ 2 + (2t -), 1 2 r2 b (t) .
Then X is homotopy equivalent to the Vietoris-Rips complex Rips(X , r).

We end this section by introducing a sampling condition in which we can guarantee the covering conditions in Corollary 10 and Theorem 19, 20 are satisfied. Let P be the sampling distribution on X. We assume that there exist positive constants a, b and 0 such that, for all x ∈ X, the following inequality holds:

P (B R d (x, )) ≥ a b , for all ∈ (0, 0 ). ( 19
)
This condition on P is also known as the (a, b)-condition or the standard condition [START_REF] Cuevas | On boundary estimation[END_REF][START_REF] Cuevas | Set estimation: another bridge between statistics and geometry[END_REF][START_REF] Chazal | Robust topological inference: Distance to a measure and kernel distance[END_REF].

It is satisfied, for example, if X is a smooth manifold of dimension b and P has a density with respect to the Hausdorff measure on it bounded from below by a.

Under this condition, we have the following covering lemma.

Lemma 23. Let {X 1 , . . . , X n } be an i.i.d. sample from the distribution P and let {r n = (r n,1 , . . . , r n,n )} n∈N be a triangular array of positive numbers such that, for each n,

2
log n an

1/b ≤ min i r n,i ≤ 2 0 . ( 20
)
Then, the probability that the sample is a r n -covering of X is bounded as

P X ⊂ n i=1 B R d (X i , r n,i ) ≥ 1 - 1 2 b log n . ( 21
)

Conditions for homotopy reconstruction

In this subsection, we discuss the tightness of the conditions we have identified for guaranteeing the homotopy equivalence of the target space and the Čech complex and the Vietoris-Rips complex. We first argue that the maximum radius conditions in [START_REF] Cuevas | Set estimation: another bridge between statistics and geometry[END_REF] and [START_REF] Tamal | Curve and Surface Reconstruction: Algorithms with Mathematical Analysis[END_REF] are tight, as Example 24 shows that the Čech complex fails to be homotopy equivalent to X when r max > τ -d X (x) and the Vietoris-Rips complex fails to be homotopy equivalent to X when

r max > d+1 2d (τ -d X (x)) and d ≤ 2.
Example 24. Let ∈ [0, 1) be fixed. Let X ⊂ R d be the unit sphere in R d , and let X = {x 1 , . . . , x n } ⊂ (1 -)X be a finite set of points on the sphere centered at 0 and of radius 1 -. Suppose that for some δ > , X is covered by δ-balls centered at X , that is,

X ⊂ x∈X B R (x, δ).
The reach of X equals to its radius 1.

For the ambient Čech complex, if r ∈ (0, 1 -] n and condition (15) is satisfied, then X is homotopy equivalent to Čech X (X , r) by Theorem 19. Now, suppose that

r min > 1 -. Then 0 ∈ B R d (x i , r xi ) for all i, hence for any y ∈ n i=1 B R d (x i , r xi ), a line segment connecting 0 and y is contained in n i=1 B R d (x i , r xi ) as well. Hence n i=1 B R d (x i , r xi ) is contractible, and then from the usual Nerve Theorem, Čech R d (X , r) n i=1 B R d (x i , r xi ) 0. On the other hand, the d -1-th homology group of X is H d-1 (X) = Z, so X and Čech R d (X , r) are not homotopy equivalent. For the Vietoris-Rips complex, if r ∈ 0, d+1 2d (1 -) d+1
and condition ( 18) is satisfied, then X is homotopy equivalent to Rips X (X , r) by Theorem 20. Now, suppose each r xi is equal to some r > d+1 2d (1 -), and further suppose that d ≤ 2 and δ <

1 2(1-) r 0 - √ 3
4 . When d = 1, then the Vietoris-Rips complex equals the ambient Čech complex, hence from the above argument, Rips (X , r

) = Čech R d (X , r) 0. When d = 2, then Rips (X , r) ∼ = Rips 1 1-X , 1 1-r 0 and 1 1-X ⊂ X ⊂ n i=1 B R d ( 1 1-x i , δ) holds. Then 1 1-r 0 -2δ > √ 3
2 , and hence from Proposition 3.8, Corollary 4.5, Proposition 5.2 of [START_REF] Adamaszek | The Vietoris-Rips complexes of a circle[END_REF], either Rips (X , r) S 2l+1 for some l ≥ 1 or Rips (X , r)

∨ c S 2l for some l ≥ 1 and c ≥ 0. In either case, H 1 (Rips (X , r)) = 0. However, the d -1-th homology group of X is H d-1 (X) = Z, so X and Rips (X , r) are not homotopy equivalent.

We then rephrase the conditions on := max{d X (x) : x ∈ X } and the covering radius δ in ( 15) and ( 18) in terms of the Hausdorff distance d H (X, X ). For simplicity, we consider the case when all the radii r x 's are equal, and we denote that common value as r. In general, the Hausdorff distance d H (X, X ) gives a bound for both and δ, that is,

, δ ≤ d H (X, X ). Let ρ := d H (X,X ) τ .
For the Čech complex, a sufficient condition for [START_REF] Cuevas | On boundary estimation[END_REF] is that for some r τ ∈ (0, 1],

ρ + ( r τ ) 2 -l2 + ρ(2 -ρ) -((1 -ρ) 2 -( r τ ) 2 + l2 + (1 -ρ l) 2 )   1 1 -r2 δ,c -1   ≤ r τ , d 2(d + 1)    r2 b -(2 -r2 b )   1 1 -r2 δ,b -1   + 2ρ    ≤ r min , ( 22
)
where

l := 1 2 r τ -1 + (1 -ρ) 2 -( r τ ) 2 -ρ , ρ l := 1 -(1 -ρ) 2 -( r τ ) 2 + l, r2 δ,c := min 2ρ, 1 2 (( r τ ) 2 -l2 + ρ(2 -ρ) + ρ l(2 -ρ l)) , r min := 1 -ρ(2 -ρ) - (2 -( r τ ) 2 -ρ(2 -ρ)) 2 4 , r2 b := 2 (r min ) 2 + ρ(2 -ρ) 1 + 1 -((r min ) 2 + ρ(2 -ρ)) , r2 δ,b := min 2ρ, 1 2 r2 b .
And for the Vietoris-Rips complex, the sufficient condition for ( 18) is

r2 b (r 0 ) -(2 -r2 b (r 0 ))   1 1 -r2 δ,b (r 0 ) -1   + 2ρ ≤ 2r 0 , d 2(d + 1)    r2 b (r min ) -(2 -r2 b (r min ))   1 1 -r2 δ,b (r min ) -1   + 2ρ    ≤ r min , ( 23
)
where

r 0 := d + 1 2d (1 -ρ), r min := 1 -ρ(2 -ρ) - (2 -d+1 2d (1 -ρ) 2 -ρ(2 -ρ)) 2 4 , r2 b (t) := 2 t 2 + ρ(2 -ρ) 1 + 1 -(t 2 + ρ(2 -ρ)) , r2 δ,b (t) := min 2ρ, 1 2 r2 b (t) .
With the aid of a computer program, we can check that ( 22) is equivalent to ρ ≤ 0.01591 • • • , and ( 23) is equivalent to ρ ≤ 0.07856 • • • . Now, we consider two specific cases. First, we consider the noiseless case X ⊂ X, that is, the data points lie in the target space. For that case, = 0 and δ ≤ d H (X, X ). For the Čech complex, the sufficient condition for [START_REF] Cuevas | On boundary estimation[END_REF] is that for some r τ ∈ (0, 1],

ρ + ( r τ ) 2 -l2 -(1 -( r τ ) 2 + l2 + (1 -ρ l) 2 )   1 1 -r2 δ,c -1   ≤ r τ , d 2(d + 1)    r2 b -(2 -r2 b )   1 1 -r2 δ,b -1   + 2ρ    ≤ r min , ( 24
)
where

l := 1 2 r τ -1 + 1 -( r τ ) 2 -ρ , ρ l := 1 -1 -( r τ ) 2 + l, r2 δ,c := min ρ 2 , 1 2 (( r τ ) 2 -l2 + ρ l(2 -ρ l)) , r min := 1 - (2 -( r τ ) 2 ) 2 4 , r2 b := 2(r min ) 2 1 + 1 -(r min ) 2 , r2 δ,b := min ρ 2 , 1 2 r2 b .
For the Vietoris-Rips complex, a sufficient condition for ( 18) is

r2 b (r 0 ) -(2 -r2 b (r 0 ))   1 1 -r2 δ,b (r 0 ) -1   + 2ρ ≤ 2r 0 , d 2(d + 1)    r2 b (r min ) -(2 -r2 b (r min ))   1 1 -r2 δ,b (r min ) -1   + 2ρ    ≤ r min , ( 25
)
where

r 0 := d + 1 2d (1 -ρ), r min := 1 - (2 -d+1 2d (1 -ρ) 2 ) 2 4 , r2 b (t) := 2t 2 1 + √ 1 -t 2 , r2 δ,b (t) := min ρ 2 , 1 2 r2 b (t) .
With the aid of a computer program, we can check that (24) is equivalent to ρ ≤ 0.02994

• • • , and (25) is equivalent to ρ ≤ 0.1117 • • • .
Second, we consider the asymptotic case, where we sample more and more points and X forms a dense cover of X, that is, sup y∈X inf x∈X x -y → 0. Still, we have a noisy sample distribution, that is, sup x∈X inf y∈X x -y 0, so the Hausdorff distance d H (X, X ) need not go to 0. In this case, δ → 0 and ≤ d H (X, X ). For the Čech complex, a sufficient condition for [START_REF] Cuevas | On boundary estimation[END_REF] is that for some r τ ∈ (0, 1],

( r τ ) 2 -l2 + ρ(2 -ρ) -((1 -ρ) 2 -( r τ ) 2 + l2 + (1 -ρ l) 2 )   1 1 -r2 δ,c -1   ≤ r τ , d 2(d + 1) r2 b -(2 -r2 b )   1 1 -r2 δ,b -1   ≤ r min , ( 26
)
where

l := 1 2 r τ -1 + (1 -ρ) 2 -( r τ ) 2 , ρ l := 1 -(1 -ρ) 2 -( r τ ) 2 + l, r2 δ,c := min ρ(2 -ρ), 1 2 (( r τ ) 2 -l2 + ρ(2 -ρ) + ρ l(2 -ρ l)) , r min := 1 -ρ(2 -ρ) - (2 -( r τ ) 2 -ρ(2 -ρ)) 2 4 , r2 b := 2 (r min ) 2 + ρ(2 -ρ) 1 + 1 -((r min ) 2 + ρ(2 -ρ)) , r2 δ,b := min ρ(2 -ρ), 1 2 r2 b .
And for the Vietoris-Rips complex, a sufficient condition for ( 18) is

r2 b (r 0 ) -(2 -r2 b (r 0 ))   1 1 -r2 δ,b (r 0 ) -1   ≤ 2r 0 , d 2(d + 1) r2 b (r min ) -(2 -r2 b (r min ))   1 1 -r2 δ,b (r min ) -1   ≤ r min , ( 27
)
where

r 0 := d + 1 2d (1 -ρ), r min := 1 -ρ(2 -ρ) - (2 -d+1 2d (1 -ρ) 2 -ρ(2 -ρ)) 2 4 , r2 b (t) := 2 t 2 + ρ(2 -ρ) 1 + 1 -(t 2 + ρ(2 -ρ)) , r2 δ,b (t) := min ρ(2 -ρ), 1 2 r2 b (t) .
With the aid of a computer program, we can check that (26) is equivalent to ρ ≤ 0.03440

Discussion and Conclusion

Above we have provided conditions under which the ambient Čech complex Čech R d (X , r) and the Rips complex Rips(X , r) are homotopy equivalent to the target space X when the target space X has positive µ-reach τ µ and the data points X being contained in the -offset X of X. In this section, we further discuss our results and compare them with existing ones.

For the comparison purpose, we consider the case when all the radii r x 's are equal, and we denote the common value as r. In these settings, an analogous homotopy equivalence between the ambient Čech complex Čech R d (X , r) and the target space X is presented in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] and [27]. First, we compare the upper bound for the maximum parameter value r in Čech R d (X , r) or Rips(X , r). When µ = 1 so that τ µ = τ , our result suggests that the homotopy equivalences hold when r ≤ τ -for Čech R d (X , r) and r ≤ d+1 2d (τ -) for Rips(X , r). As we have seen in Example 24, these bounds are optimal bounds. In [27], such a bound for Čech R d (X , r) is

(τ + )+ √ τ 2 + 2 -6τ 2
(see Proposition 7.1). Then our bound is strictly sharper than this when > 0 since

(τ + ) + √ τ 2 + 2 -6τ 2 < (τ + ) + √ τ 2 + 9 2 -6τ 2 = τ -.
In [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF], a necessary condition for Čech R d (X , r) in Section 5.3 is r ≤ τ -3 , so our upper bound is strictly better when > 0. Second, we compare the condition for the maximum possible ratio of the Hausdorff distance d H (X, X ) and the µ-reach τ µ . For this case, as we have seen in Section 5.1, we can check that Čech R d (X , r) is homotopy equivalent to X when d H (X,X ) [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. Again from Section 5.1, we can check that Rips(X , r) is homotopy equivalent to X

τ ≤ 0.01591 • • • . This result is worse than 3 - √ 8 ≈ 0.1716 • • • in Proposition 7.1 in [27] or -3+ √ 22 13 ≈ 0.1300 • • • in Section 5.3 in
when d H (X,X ) τ ≤ 0.07856 • • • . This result is better than 2 √ 2- √ 2- √ 2 2+ √ 2 ≈ 0.03412 • • • in Section 5.3 in [6].
Then we consider two specific cases. In the noiseless case X ⊂ X, the data points lie in the target space. In this case, as we have seen in Section 5.1, we can verify that

Čech R d (X , r) is homotopy equivalent to X when d H (X,X ) τ ≤ 0.02994 • • • , and Rips(X , r) is homotopy equivalent to X when d H (X,X ) τ ≤ 0.1117 • • • .
In the asymptotics case, as we sample more and more points from the target space, X forms a dense cover on X, that is, sup y∈X inf x∈X x -y → 0. For this case, as we have seen in Section 5.1, we can check that Čech R d (X , r) is homotopy equivalent to X when d H (X,X )

τ ≤ 0.03440 • • • , and Rips(X , r) is homotopy equivalent to X when d H (X,X ) τ ≤ 0.07712 • • • .
Finally, we emphasize that our result also allows the radii {r x } x∈X to vary across the points x ∈ X . Considering different radii is of practical interest if each data point has different importance. For example, one might want to use large radii on the flat and sparse region, while to use small radii on the spiky and dense region. However, there remain significant technical difficulties to allow for a different radius per each data point. As it can be seen in Figure 2, an uneven distribution of radii might lead to nonhomotopic between the Čech complex (or the Vietoris-Rips complex) and the target space. This situation has been studied in [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF] for the union of balls under the reach condition, but not the Vietoris-Rips complex or under the µ-reach case. Theorem 20 or Corollary 22 first tackles this homotopy reconstruction problem with different radii for the Vietoris-Rips complex or under the µ-reach condition.

A More background

Throughout the paper, for x ∈ R, we use the notation (x) + := max{x, 0}. Also, for a subset

X ⊂ R d and a point x ∈ R d \M ed(X), let π X : R d → X be the projection function to X, that is, π X (x) = arg min y∈X x -y .
We first review some topological equivalent relations. Two spaces X, Y are homeomorphic and write X ∼ = Y if there exists a bijective function f : X → Y that is continuous and its inverse f -1 : Y → X is also continuous. Sometimes the homeomorphic equivalence is too fine and we need a coarser equivalent relation. A homotopy between two continuous functions f, g :

X → Y is a continuous function H : X × [0, 1] → Y such that H(x, 0) = f (x)
and H(x, 1) = g(x) for all x ∈ X. We say that f and g are homotopic if there exists a homotopy between them, and write f g. Two spaces X, Y are homotopy equivalent if there exists f :

X → Y and g : Y → X such that g • f id X and f • g id Y . Then homotopy equivalence is coarser than the homeomorphic equivalence, in that if X ∼ = Y then X Y .
A space X deformation retracts to a subset A ⊂ X if there exists a homotopy H : X × [0, 1] → X such that for all x ∈ X, H(x, 0) = x and H(x, 1) ∈ A, and for all x ∈ A and t

∈ [0, 1] H(x, t) = x. A space X is contractible if X is homotopy equivalent to a point x.
We can see that if a space X deformation retracts to a point x ∈ X then X is contractible, but the converse is not always true.

The following theorem is from [26]. This theorem is used for constructing the homotopy map giving a deformation retract from X r to X in Theorem 12.

Theorem 25 (Fundamental theorem on flows). Let W be a smooth vector field on a smooth manifold M . Then there is a unique maximal flow ψ :

D ⊂ M × R → M with d dt ψ(x, t) = W (ψ(x, t)). In particular, the maximal domain D is open in M × R.
The following Lemma 3.3 in [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF] shows that the homotopy equivalence in the Nerve Theorem commutes well with the inclusion maps. This lemma plays a critical role in showing the homotopy equivalence of the target space X and a simplicial complex S in Lemma 40. For a space X, its open cover U = {U i } i∈I is a good cover if its intersection is either empty or contractible, that is, for each σ ⊂ I, the set i∈σ U i is either empty or contractible.

Lemma 26 (Lemma 3.3 in [START_REF] Chazal | Towards persistence-based reconstruction in euclidean spaces[END_REF]). Let X ⊂ X be two paracompact spaces, and let U = {U i } i∈I , U = {U i } i∈I , be good covers of X and X , respectively, with I ⊂ I and U i ⊂ U i for all i ∈ I. Then, there exist homotopy equivalences N U → X and N U → X that commutes with inclusions X → X and N U → N U at homotopy level, that is, the following diagram commutes:

X ı X→X / / X N U ı N U →N U / / O O N U O O .

A.1 The reach and the distance function

Sometimes we are interested in the local behavior of the target space. For that, the reach can be defined locally at a point. The reach of a closed set X ⊂ R d at q ∈ X, denoted by τ X (q), is defined as

τ X (q) := d (q, Med(X)) = inf x∈Med(X) ||q -x||.
Then it is direct that the reach is the infimum of the reach at each point, that is,

τ X = inf q∈X τ X (q).
The positive condition for the reach imposes smoothness on the target space. In particular, the reach condition enforces a lower bound on the inner product between a difference vector between two points and a normal vector at one of these points, and provides a Lipschitz continuity on the projection function to the target space.

Theorem 27 (Theorem 4.8 ( 7) and ( 8)

in [21]). Let X ⊂ R d be a subset. (i) If x ∈ X and u ∈ R d \M ed(X), then u -π X (u), π X (u) -x ≥ - x -π X (u) 2 d X (u) 2τ X (u) . (ii) If , τ ∈ R with 0 < < τ and x, y ∈ R d \M ed(X) with d X (x), d X (u) ≤ and τ X (x), τ X (u) ≥ τ , then π X (x) -π X (u) ≤ τ τ - x -u .
In the case of submanifolds, one can reformulate the definition of the reach in the following manner.

X

q 1 + T q 1 X d (q 2 -q 1 , T q 1 X) q 2 -q 1 q 2 -q 1 2 2d ( q 2 -q 1 ,T q 1 X ) C q 2 q 1 Figure 5
Geometric interpretation of the quantities involved in (28).

Proposition 28

(Theorem 4.18 in [21]). If X ⊂ R d is a submanifold of R d , then τ X = inf q1 =q2∈X q 1 -q 2 2 2 2d(q 2 -q 1 , T q1 X) . (28)
Above, T q X denotes the tangent space of X at q ∈ X. This formulation has the advantage of involving only points on X and its tangent spaces, while (6) uses the distance to the medial axis M ed(X), which is a global quantity. The ratio appearing in (28) has a clear geometric meaning, as it corresponds to the radius of the ambient ball tangent to X at q 1 and passing through q 2 . See Figure 5. Hence, the reach gives a lower bound on the radii of curvature of X. Equivalently, τ -1 X is an upper bound on the directional curvature of X. Proposition 29 (Proposition 6.1 in [27]). Let X ⊂ R d be a submanifold, and γ p,v an arc-length parametrized geodesic of X. Then for all t > 0,

γ p,v (t) ≤ 1/τ X .
The reach further provides an upper bound on the injectivity radius and the sectional curvature of X; see Proposition A.1. part (ii) and (iii) respectively, in [START_REF] Aamari | Estimating the reach of a manifold[END_REF]. Hence the reach is a quantity that characterizes the overall structure of X and, as argued in [START_REF] Aamari | Estimating the reach of a manifold[END_REF], captures structural properties of X of both global and local nature. In particular, assuming a lower bound on the reach prevents the manifold from being nearly self-intersecting or from having portions with very high curvature [START_REF] Aamari | Estimating the reach of a manifold[END_REF]Theorem 3.4].

We end this section with the bound on the distance function, which is Lemma 3.2 in [START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF]. We enhance this bound in Lemma 39.

Lemma 30. Let X ⊂ R d be a closed set and x ∈ M ed µ (X). Then for any y ∈ R d , the distance d X (y) is bounded as

d X (y) 2 ≤ d X (x) 2 + x -y 2 + 2d X (x) ∇ X (x) x -y .
Theorem 31

(Theorem 4.1 in [9]). Let X ⊂ R d be a closed set with µ-reach τ µ X > 0. Then for r ∈ (0, τ µ X ), τ (X r ) ≥ µr.

B Projection on a Positive Reach set

The positive reach condition imposes smoothness in geometry and topology. In particular, given two points x, u ∈ R d where u has the unique projection π X (u) ∈ X to the target space X, the positive reach condition gives a bound on the distance x -π X (u) from the projection π X (u) to x in terms of the distance x -u . When x also has the unique projection π X (x) and τ ≥ τ X (π X (x)), τ X (π X (u)), a direct consequence of Theorem 27 (ii) gives a bound as

x -π X (u) ≤ d X (x) -π X (u) + x -π X (x) ≤ τ τ -d X (u) x -u + d X (x). ( 29
)
This section is devoted to improve (29) and give a tighter bound on x -π X (u) . An improved bound is given in Lemma 33. Then, for the case where the distance d X (u) from u to X is not directly known, a bound for a general case is given in Lemma 34 in terms of x -u , and a bound for a case when u is in a convex hull of a set of points x 1 , . . . , x k is given in Lemma 37 in terms of x -x i 's for i = 1, . . . , k. Lemma 34 and 37 play key roles in showing the homotopy equivalence of the target space X to the restricted Čech complex (Corollary 10), the ambient Čech complex (Theorem 19), and the Vietoris-Rips complex (Theorem 20).

The proof of Theorem 27 (ii) in [21] is based on Theorem 27 (i). To improve (29), we generalize Theorem 27 (i) to the case where the point x need not be on the target space X, in Claim 32. The proof is similar to the proof of Theorem 27 (i) in [21].

Claim 32. Let τ > 0 and X ⊂ R d be a set. Let x ∈ R d and u ∈ R d \M ed(X) with reach(X, π X (u)) ≥ τ and d X (x) ≤ τ . Then u -π X (u), π X (u) -x ≥ - x -π X (u) 2 d X (u) 2τ -d X (x)d X (u) 1 - d X (x) 2τ .
Proof of Claim 32. If π X (u) = u, then d X (u) = 0 and the inequality trivially holds. Assume π X (u) = u, and we will find a lower bound for u -π

X (u), π X (u) -x . Let v = u -π X (u) d X (u) , S = {t > 0 : π X (π X (u) + tv) = π X (u)}.
Then u -π X (u) ∈ S implies sup S > 0, and then Theorem 4.8 [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] in [21] implies that sup S ≥ τ.

(30)

Now, if t < sup S, then π X (u) + tv -x is lower bounded using π X (π X (u) + tv) = π X (u) as (see Figure 6 for a graphical illustration)

π X (u) + tv -x ≥ π X (u) + tv -π X (x) -x -π X (x) ≥ π X (u) + tv -π X (π X (u) + tv) -d X (x) = π X (u) + tv -π X (u) -d X (x) = t -d X (x). (31)
And since both π X (u) + tv -x and t -d X (x) are continuous on t, so for all t ≤ sup S, π X (u) + tv -x is lower bounded as

π X (u) + tv -x ≥ t -d X (x).
Then additionally under t ≥ d X (x), squaring and expanding gives

π X (u) -x 2 + 2t v, π X (u) -x + t 2 ≥ (t -d X (x)) 2 . π X (u) + tv π X (u) u π X (x) x π X (u) + tv -x t X d X (x) π X (u) + tv -π X (x)
Figure 6 The graphical illustration involved in (31).

Rearranging this gives that if

d X (x) ≤ t ≤ sup S, then v, π X (u) -x is lower bounded as v, π X (u) -x ≥ - π X (u) -x 2 2t -d X (x) 1 - d X (x) 2t . ( 32
)
Hence( 30) and (32) implies that, under the condition

d X (x) ≤ τ , applying v = u-π X (u) u-π X (u) and t = τ gives a lower bound for u -π X (u), π X (u) -x as u -π X (u), π X (u) -x ≥ - π X (u) -x 2 d X (u) 2τ -d X (x)d X (u) 1 - d X (x) 2τ .
Now we are ready to pose a bound for x -π X (u) in Lemma 33 that is improved from (29). The proof is similar to the proof of Theorem 27 (ii) in [21], while we use Claim 32 instead of Theorem 27 (i).

Lemma 33. Let τ > 0 and X ⊂ R d be a set. Let ≥ 0, x ∈ R d , and u ∈ R d \M ed(X) with reach(X, π X (u)) ≥ τ and d X (x) ≤ ≤ τ . Then

x -π X (u) ≤ τ τ -d X (u) x -u 2 -d X (u) d X (u) -2 + 2 τ . ( 33
)
Proof of Lemma 33. From Claim 32, u -π X (u), π X (u) -x is lower bounded as

u -π X (u), π X (u) -x ≥ - π X (u) -x 2 d X (u) 2τ -d X (x)d X (u) 1 - d X (x) 2τ .
Hence x -u 2 can be expanded and lower bounded as

x -u 2 = u -π X (u) 2 + π X (u) -x 2 + 2 u -π X (u), π X (u) -x ≥ d X (u) 2 + π X (u) -x 2 1 - d X (u) τ -2d X (x)d X (u) 1 - d X (x) 2τ .
By rearranging, we obtain an upper bound for x -π X (u) as

x -π X (u) ≤ τ τ -d X (u) x -u 2 -d X (u) d X (u) -2d X (x) + d X (x) 2 τ .
And

d X (x) ≤ ≤ τ implies 2d X (x) -d X (x) 2 τ ≤ 2 - 2 τ
, and hence x -π X (u) is further upper bounded as

x -π X (u) ≤ τ τ -d X (u) x -u 2 -d X (u) d X (u) -2 + 2 τ .
Note that by setting = d X (x), the bound of (33) is upper bounded by the bound of (29) as

τ τ -d X (u) x -u 2 -d X (u) d X (u) -2 + 2 τ = τ τ -d X (u) x -u 2 - τ τ -d X (u) (d X (u) -) 2 + 2 ≤ τ τ -d X (u) x -u 2 + 2 ≤ τ τ -d X (u) x -u + ≤ τ τ -d X (u) x -u + , so (33)
is indeed tighter than (29). For many cases, we don't have direct access to the distance d X (u) from u to X but only through a bound d X (u) ≤ u for some u ≥ 0. For this case, we need to maximize the bound of (33) with respect to d X (u). As a result, the bound for x -π X (u) is expressed in terms of x -u and u in Lemma 34. Lemma 34 plays a key role in showing the interleaving relationship between the restricted Čech complex and the ambient Čech complex in Lemma 17.

Lemma 34. Let τ > 0 and X ⊂ R d be a set. Let ≥ 0, x ∈ R d , and

u ∈ R d \M ed(X) with reach(X, π X (u)) ≥ τ and d X (x) ≤ ≤ τ . (i) Let u ∈ R and suppose that d X (u) ≤ u < τ . Then x -π X (u) ≤ x -u 2 + r2 -(τ 2 + (τ -) 2 -x -u 2 -r2 ) τ √ τ 2 -r2 -1 , where r2 := min x -u 2 + (2τ -), τ 2 -(τ -u ) 2 . (ii) Suppose that x -u ≤ τ -, then x -π X (u) ≤ 2τ u -x 2 + (2τ -) τ + τ 2 -u -x 2 + (2τ -) -(2τ -).
Proof of Lemma 34. (i) First, considering Lemma 33 gives an upper bound for x -π X (u) as

x -π X (u) ≤ τ τ -d X (u) u -x 2 -d X (u) d X (u) -2 + 2 τ . ( 34
)
We further bound (34) by regarding (34) as a function of d X (u) and maximize with respect to d X (u). Let ru := u -x , rX := 2 -2 τ , and ryz := τ 2 -(τu ) 2 for convenience, so that u = τ -τ 2 -r2 yz . Now, consider the function

t ∈ 0, τ -τ 2 -r2 yz → f (t) := τ (r 2 u -t 2 + rX t) τ -t .
Then its derivative is 2 .

f (t) = τ (t 2 -2τ t + r2 u + rX τ ) (τ -t)
Hence if r2 u + rX τ ≥ τ 2 then f (t) ≥ 0 holds for all t ∈ 0, τ -τ 2 -r2 yz , and if r2 u + rX τ ≤ τ 2 then f (t) ≥ 0 if and only if t ≤ τ -τ 2 -(r 2 u + rX τ ). Hence if r2 yz ≤ r2 u + rX τ then f attains its maximum at t = τ -τ 2 -r2
yz , and if r2 u + rX τ ≤ r2 yz then f attains its maximum at t = τ -τ 2 -(r 2 u + rX τ ). Hence by letting r := min{ r2 u + rX τ , ryz }, for all

t ∈ 0, τ -τ 2 -r2 yz , f (t) ≤ f τ -τ 2 -r2 = τ r2 u + r2 -2τ 2 + rX τ + (2τ -rX ) √ τ 2 -r2 √ τ 2 -r2 .
Hence (34) is correspondingly further upper bounded as

x -π X (u) ≤ τ τ -d X (u) u -x 2 -d X (u) d X (u) -2 + 2 τ ≤ τ r2 u + r2 -2τ 2 + rX τ + (2τ -rX ) √ τ 2 -r2 √ τ 2 -r2 (35) = r2 u + r2 -(2τ 2 -r2 u -r2 -rX τ ) τ √ τ 2 -r2 -1 = x -u 2 + r2 -(τ 2 + (τ -) 2 -x -u 2 -r2 ) τ √ τ 2 -r2 -1 , where r2 := min x -u 2 + (2τ -), τ 2 -(τ -u ) 2 . (ii) Since d X (u) < τ , we can set u → τ , which implies r2 yz → τ 2 . And under x -u ≤ τ -, r2 u + rX τ ≤ (τ -) 2 + (2τ -) = τ 2 ,

and hence r2 → r2

u + rX τ . Then (35) converges to

τ r2 u + r2 -2τ 2 + rX τ + (2τ -rX ) √ τ 2 -r2 √ τ 2 -r2 → τ 2τ -rX -2 τ 2 -(r 2 u + rX τ ) ,
and hence x -π X (u) is correspondingly bounded as

x -π X (u) ≤ τ 2τ -rX -2 τ 2 -(r 2 u + rX τ ) = 2τ (r 2 u + rX τ ) τ + τ 2 -(r 2 u + rX τ ) -rX τ = 2τ u -x 2 + (2τ -) τ + τ 2 -u -x 2 + (2τ -) -(2τ -).
Now, we consider the case when the point u is in a convex hull of a set of points x 1 , . . . , x k . We first start with a simple calculation of the distance from one vertex of a simplex to another point lying on the opposite side.

Claim 35. Let x, x 1 , . . . , x k ∈ R d and λ 1 , . . . , λ k ∈ [0, 1] with k i=1 λ i = 1. Then x - k i=1 λ i x i = k i=1 λ i x -x i 2 - 1≤i<j≤k λ i λ j x i -x j 2 (36) = k i=1 λ i x -x i 2 - k i=1 λ i x i - k j=1 λ j x j 2 . ( 37
)
Proof of Claim 35. The distance from k i=1 λ i x i to x can be expanded as

x - k i=1 λ i x i 2 = k i=1 λ i (x -x i ) 2 = k i=1 λ 2 i x -x i 2 + 2 1≤i<j≤k λ i λ j x -x i , x -x j . ( 38
)
Then applying the identity 2 x -x i , x -

x j = x -x i 2 + x -x j 2 -x i -x j 2 to (38) gives x - k i=1 λ i x i 2 = k i=1 λ i x -x i 2 - 1≤i<j≤k λ i λ j x i -x j 2 , ( 39
)
which gives (36). Then, applying x =

k i=1 λ i x i to (39) gives k i=1 λ i x i - k j=1 λ j x j 2 = 1≤i<j≤k λ i λ j x i -x j 2 , ( 40
)
and combining (39) and (40) gives (37).

If the points x 1 , . . . , x k are not far from the target space X, then so is the convex combination u. Lemma 36 gives a bound on the distance from any point u on the convex hull to its projection π X (u) on X. See Figure 7.

x i x j w π X (u) u τ d X (x i ) X Figure 7
Bound on the distance from any point on the segment to its projection on X, as in Lemma 36.

Lemma 36. Let τ > 0 and X ⊂ R d be a subset with reach τ X ≥ τ . Let 1 , . . . , k ≥ 0 and x 1 , . . . ,

x k ∈ R d with d X (x i ) ≤ i ≤ τ for i = 1, . . . , k. Let λ 1 , . . . , λ k ∈ [0, 1] with k i=1 λ i = 1, and let u := k i=1 λ i x i be such that d X (u) < τ . Then u -π X (u) ≤ τ -   k i=1 λ i (τ -i ) 2 - 1≤i<j≤k λ i λ j x i -x j 2   + = τ -    k i=1 λ i (τ -i ) 2 - k i=1 λ i x i - k j=1 λ j x j 2    + .
Proof of Lemma 36. If π X (u) = u, then there is nothing to prove. Now, suppose π X (u) = u, and let w := π X (u) + τ u-π X (u) u-π X (u) . Then, we have that w -π X (u) = τ and w -u

= τ -π X (u)-u π X (u)-u (u -π X (u)). Since u -π X (u) < τ , it follows that w -u, u -π X (u) = w -u u -π X (u) and u -π X (u) + w -u = w -π X (u) , as in Figure 7. Since π X π X (u) + u -π X (u) u-π X (u) u-π X (u) = π X (u) and π X (u) + r u-π X (u) u-π X (u)
/ ∈ M ed(X) for all r < τ , Theorem 4.8 ( 2) and ( 6) in [21] imply that

π X π X (u) + r u -π X (u) u -π X (u) = π X (u)
for all r < τ . Thus, B(w, τ ) ∩ X = ∅ and we can conclude that w -

x i ≥ τ -d X (x i ) ≥ τ -i for i = 1, . . . , k.
Applying Claim 35 to w -u gives a lower bound for w -u as

w -u = k i=1 λ i x i -w 2 - 1≤i<j≤k λ i λ j x i -x j 2 ≥   k i=1 λ i (τ -i ) 2 - 1≤i<j≤k λ i λ j x i -x j 2   + .
Then, applying u -π X (u) = w -π X (u) -w -u and Claim 35 gives upper bounds for u -π X (u) as

u -π X (u) ≤ τ -   k i=1 λ i (τ -i ) 2 - 1≤i<j≤k λ i λ j x i -x j 2   + = τ -    k i=1 λ i (τ -i ) 2 - k i=1 λ i x i - k j=1 λ j x j 2    + .
Now, combining Lemma 34 and 36 and gives the bound on x -u in terms of x -x i 's for i = 1, . . . , k, in Lemma 37. Lemma 37 plays a key role in showing the contractibility of the intersection of restricted balls in Theorem 9.

Lemma 37. Let τ > 0 and X ⊂ R d be a subset with reach τ X ≥ τ . Let , 1 , . . . , k ≥ 0 and x, x 1 , . . . ,

x k ∈ R d with d X (x) ≤ ≤ τ , d X (x i ) ≤ i ≤ τ , and x -x i < (τ -) 2 + (τ -i ) 2 , for each i = 1, . . . , k. Let λ 1 , . . . , λ k ∈ [0, 1] with k i=1 λ i = 1, and let u := k i=1 λ i x i . Then d X (u) < τ and x -π X (u) ≤ r2 x -(τ 2 -r2 x + (τ -) 2 )   τ τ 2 -r2 u,x -1   ,
where

r2 x := k i=1 λ i x i -x 2 + i (2τ -i ) , r2 u,x := min k i=1 λ i x i -u 2 + i (2τ -i ) , 1 2 (r 2 x + (2τ -)) .
Proof of Lemma 37. Let r :=

k i=1 λ i x i -x 2 , then r < (τ -) 2 + k i=1 λ i (τ -i ) 2 .
Then from Claim 35,

x -u = k i=1 λ i x i -x 2 - k i=1 λ i x i -u 2 = r 2 - k i=1 λ i x i -u 2 , ( 41
)
whose rearrangement gives

x -u 2 + k i=1 λ i x i -u 2 = r 2 . Then r < (τ -) 2 + k i=1 λ i (τ -i )
2 implies that either x -u < τ -or x i -u < τi for some i,and hence d X (u) < τ holds for either case. Hence applying Lemma 36 implies that

u -π X (u) ≤ τ - τ 2 - k i=1 λ i i (2τ -i ) - k i=1 λ i x i -u 2 + . ( 42
)
Hence, combining (42) and Lemma 33 gives

x -π X (u) ≤ x -u 2 + r2 -(τ 2 + (τ -) 2 -x -u 2 -r2 ) τ √ τ 2 -r2 -1 , ( 43
)
where

r2 := min x -u 2 + (2τ -), min k i=1 λ i i (2τ -i ) + k i=1 λ i x i -u 2 , τ 2 .
For further bounding (43), use the following notations for convenience:

ru := u -x , rX := 2 - 2 τ , ryz := k i=1 λ i i (2τ -i ) + k i=1 λ i x i -u 2 .
First, note that r2 u + r2 yz can be expanded as

r2 u + r2 yz = x -u 2 + k i=1 λ i i (2τ -i ) + k i=1 λ i x i -u 2 = r 2 - k i=1 λ i x i -u 2 + k i=1 λ i i (2τ -i ) + k i=1 λ i x i -u 2 = r 2 + k i=1 λ i i (2τ -i ) = k i=1 λ i x i -x 2 + i (2τ -i ) =: r2 x . (44) Then, x -x i < (τ -) 2 + (τ -i ) 2 implies that r2 u + rX τ + r2 yz is bounded as r2 u + rX τ + r2 yz = k i=1 λ i x i -x 2 + i (2τ -i ) + (2τ -) < k i=1 λ i (τ -) 2 + (τ -i ) 2 + i (2τ -i ) + (2τ -) = 2τ 2 ,
and hence r2 = min r2 u + rX τ, r2 yz .

Now, we split into cases whether ryz ≤ r2 u + rX τ or r2 u + rX τ ≤ ryz . For ryz ≤ r2 u + rX τ case, applying r = ryz to (43) gives

x -π X (u) ≤ r2 u + r2 yz -(2τ 2 -r2 u -r2 yz -rX τ )   τ τ 2 -r2 yz -1   . ( 45
)
For r2 u + rX τ ≤ ryz case, applying r = r2 u + rX τ to (43) gives

x -π X (u) ≤ 2r 2 u + rX τ -(2τ 2 -2r 2 u -2r X τ ) τ τ 2 -(r 2 u + rX τ ) -1 = 2τ 2 -rX τ -2τ τ 2 -(r 2 u + rX τ )
Then RHS is an increasing function of ru . Hence applying r2 u ≤ 1 2 (r 2 u + r2 yz -rX τ ) gives

x -π X (u) ≤ r2 u + r2 yz -(2τ 2 -r2 u -r2 yz -rX τ )   τ τ 2 -1 2 (r 2 u + r2 yz + rX τ ) -1   . (46)
Hence, combining (45) and ( 46) gives that

x -π X (u)

≤ r2 u + r2 yz -(2τ 2 -r2 u -r2 yz -rX τ )   τ τ 2 -max r2 yz , 1 2 (r 2 u + r2 yz + rX τ ) -1   .
Then, (44) gives that x -π X (u) is upper bounded as

x -π X (u) ≤ r2 x -(τ 2 -r2 x + (τ -) 2 )   τ τ 2 -r2 u,x -1   , where r2 x := k i=1 λ i x i -x 2 + i (2τ -i ) , r2 u,x := min k i=1 λ i x i -u 2 + i (2τ -i ) , 1 2 (r 2 x + (2τ -) .

C Proofs for Section 3

This section provides the proofs for Section 3, in particular focuses on proving Theorem 9.

To show the contractibility of the intersection of restricted balls x∈I B X (x, r x ), we fix a point y 0 ∈ x∈I B X (x, r x ) and show that x∈I B X (x, r x ) deformation retracts to {y 0 }. This deformation retract is constructed by sending each y ∈ x∈I B X (x, r x ) to y 0 via a curve π X (l y0,y ), where l y0,y is the line segment joining y 0 and y in R d . The key part is to show that π X (l y0,y ) ⊂ x∈I B X (x, r x ), or equivalently, to show that for all x ∈ I and t ∈ [0, 1],

x -π X (ty 0 + (1 -t)y) < r x . This is implied from Lemma 37, as x -y 0 , x -y < r x implies that

x -π X (ty 0 + (1 -t)y) ≤ t x -y 0 2 + (1 -t) x -y 2 < r x .
We restate Theorem 9 and formally write its proof below. Theorem 9. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then, if r x ≤ τ 2 + (τ -d X (x)) 2 for all x ∈ X , any nonempty intersection of restricted balls x∈I B X (x, r x ) for I ⊂ X is contractible.

Proof of Theorem 9. Fix x ∈ I and let y 1 , y 2 ∈ B X (x, r x ). Let l y1,y2 : [0, 1] → B R d (x, r x ) with l y1,y2 (t) = ty 1 + (1 -t)y 2 be the line segment joining y 1 and y 2 . Then d X (y i ) = 0 and x -y i < r x ≤ (τ -d X (x)) 2 + τ 2 for i = 1, 2, hence Lemma 37 implies that d X (l y1,y2 (t)) < τ for all t ∈ [0, 1]. Hence π X (l y1,y2 (t)) ∈ X is uniquely defined for each t ∈ [0, 1]. And hence the curve γ y1,y2 : [0, 1] → X defined as γ(t) := π X (l(t)) is well-defined. Now we argue that γ y1,y2 (t) ∈ B X (x, r x ) for all t ∈ [0, 1], in other words, we show x -γ y1,y2 (t) < r x . Again, applying Lemma 37 gives the bound for x -γ y1,y2 (t) as

x -γ y1,y2 (t) ≤ t x -y 1 2 + (1 -t) x -y 2 2 < r x . Hence γ y1,y2 (t) ∈ B X (x, r x ) for all t ∈ [0, 1]. Now, fix y 0 ∈ x∈I B X (x, r x )
, and define the map F :

x∈I B X (x, r x ) ×[0, 1] → x∈I B X (x, r x )
as F (y, t) = γ y0,y (t). As we have shown above, γ y0,y (t) ∈ x∈I B X (x, r x ) for all t, so F is a well-defined. Also, for any y, ỹ

∈ x∈I B X (x, r x ) and t, t ∈ [0, 1], Theorem (27) (ii) implies F (y, t) -F (ỹ, t) = γ y0,y (t) -γ y0,ỹ ( t) = π X (l y0,y (t)) -π X (l y0,ỹ ( t)) ≤ τ l y0,y (t) -l y0,ỹ ( t) τ -max d X (l y0,y (t)), d X (l y0,ỹ ( t))
.

Then (ỹ, t) → (y, t) implies l y0,ỹ ( t) = ty 0 + (1 -t)ỹ → ty 0 + (1 -t)y = l y0,y (t) and d X (l y0,ỹ ( t)) → d X (l y0,y (t)) < τ , and hence F (y, t) -F (ỹ, t) → 0, and hence F is continuous. Now, for all y ∈ Then Corollary 10 is a direct application of Theorem 9 to Nerve Theorem (Theorem 4).

Corollary 10 (Nerve Theorem on the restricted balls). Under the same condition of Theorem 9, suppose r x ≤ τ 2 + (τ -d X (x)) 2 for all x ∈ X , then the union of restricted balls x∈X B X (x, r x ) is homotopy equivalent to the restricted Čech complex Čech X (X , r). If, in addition, the union of restricted balls covers the target space X, that is,

X ⊂ x∈X B X (x, r x ), ( 47
)
then X is homotopy equivalent to the restricted Čech complex Čech X (X , r).

Proof of Corollary 10. Let U := {B X (x, r x )} x∈X be the collection of balls. Then since R d is paracompact, x∈X B X (x, r x ) ⊂ R d is paracompact as well. And from Theorem 9, any nonempty finite intersection of U is contractible. Hence from Nerve Theorem (Theorem 4), x∈X B X (x, r x ) is homotopy equivalent to the nerve N (U), which is the restricted Čech complex Čech X (X , r). Further, under the covering condition (47), X = x∈X B X (x, r x ), so X is homotopy equivalent to Čech X (X , r) as well.

D Proofs for Section 4

This section provides the proofs for Section 4, in particular focuses on proving Theorem 12.

As in Section 2.2, we use the following notation: For a closed set X and x ∈ R d \X, let Γ X (x) be the set of points in X closest to x, and Θ X (x) be the center of the smallest ball enclosing Γ X (x).

To prove the deformation retract, we proceed similar to [22]. We find a continuous vector field W : X r \X → R d that satisfies

sup x∈X r \X W (x), ∇ X (x) < 0. ( 48
)
And use the flow ψ generated from W , that is, d dt ψ(x, t) = W (ψ(x, t)) to find a homotopy map giving a deformation retract from X r to X. To use ψ as a homotopy map, we show that the distance function d X decreases to 0 in a finite time on the integral curve ψ x (•) := ψ(x, •): sufficiently, we show that sup

(x,s):ψ(x,s)∈X r \X lim sup h→0 d X (ψ(x, s + h)) -d X (ψ(x, s)) h < 0. ( 49
)
To construct a vector field W satisfying (48), the generalized gradient of the distance function ∇ X is necessarily required not to change too much. Lemma 38 asserts that the generalized gradient of the distance function is not necessarily continuous but it also does not change too much in terms of the inner product geometry.

Lemma 38. Let X be a closed set and x

∈ R d \X. Then lim inf y→x ∇ X (y), ∇ X (x) ≥ ∇ X (x) 2 .
Proof. Fix a small > 0. Let F X (x) be the radius of the ball enclosing Γ X (x), and consider a compact set

K := ∂B R d (x, d X (x))\B R d (Θ X (x), F X (x) + ). Since ∂B R d (x, d X (x)) ∩ X ⊂ B R d (Θ X (x), F X (x) + ), K does not intersect with X, i.e. K ⊂ R d \X. Then since R d \X
is an open set, for each q ∈ K, there exists r q > 0 such that B R d (q, 2r q ) ⊂ R d \X. And {B R d (q, r q )} q∈K covers K, hence there exists a finite subcover {B R d (q i , r qi )} m i=1 that covers K. Now, let ∆r := min{r qi : 1

≤ i ≤ m}, then K ∆r ⊂ m i=1 B R d (q i , 2r qi ) ⊂ R d \X holds. Now, from the expansion q -Θ X (x) 2 = x -q 2 + x -Θ X (x) 2 -2 x -q, x -Θ X (x) , it is implied that if x ∈ ∂B R d (x, d X (x)), then x ∈ K is equivalent to x -q, x -Θ X (x) ≤ 1 2 d X (x) 2 + d X (x) 2 ∇ X (x) 2 -(F X (x) + ) 2 = d X (x) 2 ∇ X (x) 2 -F X (x) - 1 2 2 , using F X (x) 2 = d X (x) 2 1 -∇ X (x) 2 . Hence q ∈ B R d (x, d X (x) + ∆r)\B R d (x, d X (x)) with x -q, x -Θ X (x) ≤ d X (x) 2 ∇ X (x) 2 -F X (x) -1 2 2 implies that q ∈ K ∆r . Then from B R d (x, d X (x)) ∩ X = ∅ and K ∆r ∩ X = ∅, for any q ∈ B R d (x, d X (x) + ∆r) ∩ X, x -q, x -Θ X (x) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) - 1 2 2 . ( 50
) Now, for δ ∈ (0, 1 2 ∆r), suppose y ∈ R d with y -x < δ. Then d X (y) < d X (x) + δ, so Γ X (y) ⊂ B R d (y, d X (y)) ⊂ B R d (y, d X (x) + δ) ⊂ B R d (x, d X (x) + 2δ) ⊂ B R d (x, d X (x) + ∆r).
Hence for any q ∈ Γ X (y), (50) implies that

y -q, x -Θ X (x) = x -q, x -Θ X (x) + y -x, x -Θ X (x) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) - 1 2 2 -y -x x -Θ X (x) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) - 1 2 2 -δd X (x) ∇ X (x) . ( 51
)
Since Θ X (y) is in the convex hull of Γ X (y), there exists q 1 , . . . , q k ∈ Γ X (y) and λ 1 , . . . , λ k ∈ [0, 1] with

k i=1 λ i q i = Θ X (y). Then (51) implies that y -Θ X (y), x -Θ X (x) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) - 1 2 2 -δd X (x) ∇ X (x) , which implies that ∇ X (y), ∇ X (x) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) -1 2 2 -δd X (x) ∇ X (x) d X (x)d X (y) ≥ d X (x) 2 ∇ X (x) 2 -F X (x) -1 2 2 -δd X (x) ∇ X (x) d X (x)(d X (x) + δ) .
Hence by sending δ → 0,

lim inf y→x ∇ X (y), ∇ X (x) ≥ ∇ X (x) 2 - F X (x) + 1 2 2 d X (x) 2 .
And since the choice of was arbitrary small,

lim inf y→x ∇ X (y), ∇ X (x) ≥ ∇ X (x) 2 .
To show (49), we generally show that for x, y ∈ R d , the distance function is bounded as

d X (y) 2 ≤ d X (x) 2 + x -y 2 + 2d X (x) y -x, ∇ X (x) .
This implies that for x ∈ R d \X and any differentiable curve γ with γ(s) = x,

lim sup h→0 d X (γ(s + h)) -d X (γ(s)) h ≤ γ (s), ∇ X (x) ,
and hence together with Lemma 38 implies (49). Lemma 39 bounds the distance function values that are close to each other and improves Lemma 30.

Lemma 39. Let X be a closed set and x, y ∈ R d . Then the distance d X (y) is bounded as

d X (y) 2 ≤ d X (x) 2 + x -y 2 + 2d X (x) y -x, ∇ X (x) . ( 52
)
In particular, suppose x ∈ R d \X and let γ be a differentiable curve with γ(s) = x, then

lim sup h→0 d X (γ(s + h)) -d X (γ(s)) h ≤ γ (s), ∇ X (x) . ( 53
)
Proof. We first show (52). For any q ∈ Γ X (x),

y -q 2 = x -q 2 + y -x 2 + 2 y -x, x -q = x -q 2 + y -x 2 + 2 y -x, x -Θ X (x) + 2 y -x, Θ X (x) -q . ( 54
)
Then since Θ X (x) is in the convex hull of Γ X (x), there exists q 1 , . . . , q k ∈ Γ X (x) and λ 1 , . . . , λ k ∈ [0, 1] with k i=1 λ i q i = Θ X (x). Then 2 k i=1 λ i y -x, Θ X (x) -q i = 0, so there exists q j ∈ Γ X (x) with y -x, Θ X (x) -q j ≤ 0, and applying this to (54) gives

y -q j 2 ≤ x -q j 2 + y -x 2 + 2 y -x, x -Θ X (x) = x -q j 2 + y -x 2 + 2d X (x) y -x, ∇ X (x) .
Then applying d X (y) ≤ y -q j and d X (x) = x -q j gives (52). For (53), from d X (γ(s)) = d X (x) > 0, applying γ(s + h) and γ(s) to (52) and rearranging gives

d X (γ(s + h)) -d X (γ(s)) h ≤ 1 h γ(s + h) -γ(s) 2 + 2d X (γ(s)) 1 h (γ(s + h) -γ(s)), ∇ X (x) d X (γ(s + h)) + d X (γ(s))
.

Then from γ being differentiable, as h → 0, γ(s

+ h) → γ(s), 1 h γ(s + h) -γ(s) 2 → 0, and 1
h (γ(s + h) -γ(s)) → γ (s) hold, and (53) follows.
Now, from Lemma 38 and Lemma 39, we can construct a vector field W with the desired properties, and build a homotopy map from W . We restate Theorem 12 and formally write its proof below.

Theorem 12. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0. For r ≤ τ µ , the r-offset X r deformation retracts to X. In particular, X and X r are homotopy equivalent.

Proof of Theorem 12. For each x ∈ X r \X, let W x : U x → R d be a vector field on a small neighborhood U x of x defined as a constant W x (y) = -∇ X (x). Then from Lemma 38 and the µ-reach condition, U x can be chosen arbitrary small so that

W x (y), ∇ X (y) ≤ - µ 2 ∇ X (y) . ( 55
)
From the open cover {U x } ⊃ X r \X, take a locally finite covering {U xi } i∈N , and take a smooth partition of unity {ρ i } i∈N subordinate to {U xi } i∈N . Then we define a vector field

W : X r \X → R d as W = i∈N ρ i W i .
Then note that for any x ∈ X r \X, (55) implies

W (x), ∇ X (x) = i∈N ρ i W i (x), ∇ X (x) ≤ - µ 2 ∇ X (x) . ( 56
)
Then, since X r \X is an open set in R d and W is smooth on X r \X, Fundamental Theorem of flows (Theorem 25 implies that there exists a domain D ⊂ (X r \X) × [0, ∞) and the unique smooth flow ψ : D × [0, ∞) → X r \X, i.e. d ds ψ(x, s) = W (ψ(x, s)). Such D is a maximal in that D is the set of points (x, s) such that the integral curve ψ x (•) := ψ(x, •) exists on an interval containing [0, s]. Now, Lemma 39 and (56) implies lim sup

h→0 d X (ψ(x, s + h)) -d X (ψ(x, s)) h ≤ ∇ X (ψ(x, s)), d ds ψ(x, s) = ∇ X (ψ(x, s)), W (ψ(x, s)) ≤ - µ 2 ∇ X (x) ≤ - µ 2 2 . ( 57
)
Hence d X is strictly decreasing along the integral curve ), and (57) implies that s

ψ x . Let D x := {s ∈ [0, ∞) : (x, s) ∈ D}, then D x is a connected open set in [0, ∞
x := sup D x ≤ d X (x) µ 2 /2 ≤ 2τ µ µ 2 < ∞, so D x = [0, s x ). And since (ψ x ) (s) = W (ψ x (s)) < ∞ for all s ∈ [0, s x ), ψ x ([0, s x )
) is a curve of finite length. Hence there exists a limit ψ x (s x ) := lim s→sx ψ x (s), and we can extend ψ x continuously on [0, ∞) by

ψ x (s) = ψ x (s x ) if s ≥ s x . Using this, we extend ψ on X r × [0, ∞) as ψ(x, s) = ψ x (s x ), if x ∈ X r \X, x, if x ∈ X. Now we show that ψ is continuous on X r × [0, ∞). If (x 0 , s 0 ) ∈ D, then ψ is smooth on an open set D, so ψ is continuous at (x 0 , s 0 ). When x 0 ∈ X r \X and s 0 / ∈ D x , let ρ x > 0 be small enough so that B(x 0 , ρ x ) × 0, s x0 -µ 2 8 ⊂ D and |ψ(x, s) -ψ(x 0 , s)| ≤ µ 2 8 for all (x, s) ∈ B(x 0 , ρ x ) × 0, s x0 -µ 2 8
. Then s 0 ≥ s x0 holds. And for any x ∈ B(x 0 , ρ x ),

d X ψ x, s x0 - µ 2 8 ≤ d X ψ x, s x0 - µ 2 8 -d X ψ x 0 , s x0 - µ 2 8 + d X ψ x 0 , s x0 - µ 2 8 -d X (ψ(x 0 , s x0 )) + d X (ψ(x 0 , s x0 )) ≤ µ 2 4 , then (57) implies that s x -s x0 -µ 2 8 ≤ 2 . Hence for (x, s) with x -x 0 < ρ x and s -s 0 < µ 2 8 , s 0 ≥ s x0 and s ≥ s 0 -µ 2 8 ≥ s x0 -µ 2 8 imply ψ(x, s) -ψ(x 0 , s 0 ) = ψ(x, min{s, s x }) -ψ(x 0 , s x0 ) ≤ ψ(x, min{s, s x }) -ψ x, s x0 - µ 2 8 + ψ x, s x0 - µ 2 8 -ψ x 0 , s x0 - µ 2 8 + ψ x 0 , s x0 - µ 2 8 -ψ (x 0 , s x0 ) ≤ 2 + µ 2 8 + µ 2 8 < .
Hence ψ is continuous at (x 0 , s 0 ). When x 0 ∈ X, let x ∈ B(x 0 , µ 2 4 ). Then d X (x) < µ 2 4 , so s x < 2 . Then for any x ∈ B(x 0 , µ 2 4 ) and for any s ≥ 0,

ψ(x, s) -ψ(x 0 , s) = ψ(x, s) -x 0 = ψ(x, s) -x + x -x 0 < 2 + µ 2 4 ≤ .
Hence ψ is continuous at (x 0 , s 0 ). Now, we define the deformation retract H : X r × [0, 1] → X r as H(x, t) = ψ x, 2 µ 2 t . Then, H(x, 0) = x for all x ∈ X r and H(x, t) = x for all x ∈ X. Also, since s x ≤ 2 µ 2 for all x, H(x, 1) = ψ x, 2 µ 2 ∈ X for all x ∈ X r . Also, H is continuous since ψ is continuous. Hence H gives the deformation retract from X r to X.

For showing Lemma 14, we directly construct a map ψ : X → (X r ) as

ψ(x) = x + (r-d X (x)) d X (x) (x -π X (x)), if x ∈ X r \X, x, if x / ∈ X r ,
and show that X deformation retracts to (X r ) using the map ψ. We restate Lemma 14 and formally write its proof below. Lemma 14. Let X ⊂ R d be a subset with positive reach τ > 0. For r ≤ τ , X deformation retracts to (X r ) . In particular, X and (X r ) are homotopy equivalent.

Proof of Lemma 14. For x ∈ X , let the function ψ : X → (X r ) be

ψ(x) = x + (r-d X (x)) d X (x) (x -π X (x)), if x ∈ X r \X, x, if x / ∈ X r .
From r ≤ τ , this function is well defined, and ψ is continuous on X . Also, if x / ∈ X r then ψ(x) = x / ∈ X r and if x ∈ X r \X,

ψ(x) -π X (x) = 1 + r -d X (x) d X (x)
x -π X (x) = r, so ψ(x) / ∈ X r . Hence in any case, ψ(x) ∈ (X r ) . And if x ∈ (X r ) , then ψ(x) = x on (X r ) . Now, we define the deformation retract H :

X × [0, 1] → X as H(x, t) = (1 -t)x + tψ(x).
Then, H(x, 0) = x for all x ∈ X , H(x, t) = x for all x ∈ (X r ) , and H(x, 1) ∈ (X r ) for all x ∈ X r . Also, H is continuous since ψ is continuous. Hence H gives the deformation retract from X to (X r ) .

Corollary 15. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0. For r, s > 0 with s ≤ r, let X r,s := (((X r ) ) s ) be the double offset of X. If r < τ µ and s < µr, then X r,s and X are homotopy equivalent, and the reach of X r,s is greater than or equal to s, that is, τ X r,s ≥ s.

Proof of Corollary 15. Since X has a positive µ-reach τ µ and r < τ µ , Theorem 12 implies that X and X r are homotopy equivalent. Then, by r < τ µ and Theorem 31,

τ (X r ) ≥ µr.
Then, from Lemma 14 and s < µr, X r = ((X r ) ) and X r,s = (((X r ) ) s ) are homotopy equivalent. And hence, X and X r,s are homotopy equivalent as well. Also, again by s < µr and Theorem 31,

τ X r,s = τ (((X r ) ) s ) ≥ s.

E Proofs for Section 5

This section provides the proofs for Section 5, and in particular, focuses on proving Theorem 19 and 20. For this section, we define some notions for (weighted) barycenter and radius. For a given set of radii r = {r x : x ∈ X }, Let (weighted) barycenter bc r : 2 X → R and (weighted) radius Rad r : 2 X → R be functions defined on a simplex defined as bc r (σ) = arg min

y∈R d max x∈σ x -y r x , Rad r (σ) = max x∈σ x -bc r (σ) . ( 58
)
And we drop the notation r when r x 's are all equal, i.e.

bc(σ) = arg min

y∈R d max x∈σ x -y , Rad(σ) = max x∈σ x -bc(σ) . ( 59
)
bc(σ) is the usual center of the smallest enclosing ball, and Rad(σ) is its radius. Also, note that bc r (σ)

∈ x∈σ B R d (x, r x )

if and only if min y∈R d max x∈σ

x-y rx < 1. We first extend the interleaving relationship of the ambient Čech complex and the Vietoris-Rips complex in (4) to the different radii case in Lemma 16. The proof is similar to the proof of Theorem 2.5 in [START_REF] De | Coverage in sensor networks via persistent homology[END_REF] but modified to adapt to different radii case.

Lemma 16. Let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then,

Čech R d (X , r) ⊂ Rips(X , r) ⊂ Čech R d X , 2d d + 1 r .
Proof of Lemma 16. The first inclusion Čech R d (X , r) ⊂ Rips(X , r) is trivial.

For the second inclusion, the equivalent statement is as follows

: if σ = {x 0 , . . . , x k } ⊂ R d satisfies that x i -x j < r i + r j for all 0 ≤ i, j ≤ k, then the intersection of the balls k i=0 B R d x i , 2d d+1 r xi is nonempty.
We first prove this for the case k ≤ d. Consider a function f : R d → R defined as

f (y) = max 0≤i≤k x i -y r xi .
This is continuous, and f (y) → ∞ as y → ∞, so f has a global minimum f (y 0 ) at y 0 := bc r (σ). Then y 0 ∈ co(σ) where co(σ) is the convex hull of σ, since otherwise x i -π co(σ) (y 0 ) < x i -y 0 for each x i ∈ X , contradicting the minimality of y 0 .

Let xi := x i -y 0 be the translated x i 's. We can find a convex combination (a 0 /r x0 )x 0 + • • • + (a k /r x k )x k = 0 for some j ≤ k, after relabeling so that a 0 > 0 is the largest among a 0 , . . . , a k and all a i 's are nonnegative. Then -x 0 = k i=1 ai/rx i a0/rx 0 xi , and so

-r 2 x0 f (y 0 ) 2 = -x0 2 = k i=1 a i /r xi a 0 /r x0 x0 , xi .
Then at least one i should satisfy (a i /a 0 ) x0 , xi ≤ -

rx 0 rx i f (y0) 2 k
,which can be weakened to x0 , xi ≤ -

rx 0 rx i f (y0) 2 d
. Putting these together gives

f (y 0 ) 2 (r 2 x0 + 2 d r x0 r xi + r 2 xi ) ≤ x0 2 -2 x0 , xi + xi 2 = x0 -xi 2 = (r x0 + r xi ) 2 .
Then from AM-GM inequality,

r 2 x0 + 2 d r x0 r xi + r 2 xi = d -1 2d (r 2 x0 + r 2 xi ) + d + 1 2d (r 2 x0 + r 2 xi ) + 2 d r x0 r xi ≥ d -1 d r x0 r xi + d + 1 2d (r 2 x0 + r 2 xi ) + 2 d r x0 r xi = d + 1 2d (r x0 + r xi ) 2 .
Hence combining these gives

f (y 0 ) 2 d + 1 2d (r x0 + r xi ) 2 ≤ f (y 0 ) 2 (r 2 x0 + 2 d r x0 r xi + r 2 xi ) ≤ (r x0 + r xi ) 2 ,
and hence

f (y 0 ) ≤ 2d d + 1 . Therefore y 0 ∈ k i=0 B R d x i , 2d d+1 r xi , i.e. k i=0 B R d x i , 2d
d+1 r xi is nonempty. For the case k > d, the result follows by the Helly's theorem [START_REF] Eckhoff | Chapter 2.1 -Helly, Radon, and Carathéodory type theorems[END_REF]. This asserts that a collection of k ≥ d + 2 convex sets in R d has a nonempty intersection if and only if it is true for each subcollection of size d + 1. Now, for any k + 1 points σ = {x 0 , . . . , x k } with

k ≥ d + 1, any subset ς ⊂ σ with |ς| = d + 1 satisfy that x∈ς B R d x, 2d d+1 r x is nonempty. Hence by Helly's theorem, k i=0 B R d x i , 2d d+1 r xi is nonempty as well.
We also set up the interleaving relationship between the restricted Čech complex Čech X (X , r) and the ambient Čech complex Čech R d (X , r) in Lemma 17. The proof is a direct application of Lemma 34. We restate Lemma 17 and formally write its proof.

Lemma 17. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then,

Čech X (X , r) ⊂ Čech R d (X , r) ⊂ Čech X (X , r ), where r = {r x > 0 : x ∈ X } with r x = 2τ (r 2 x + d X (x) (2τ -d X (x))) τ + τ 2 -(r 2 x + d X (x) (2τ -d X (x))) -d X (x) (2τ -d X (x)). Equivalently, Čech R d (X , r ) ⊂ Čech X (X , r) ⊂ Čech R d (X , r),
where r = {r x > 0 : x ∈ X } with

r x = τ 2 -d X (x)(2τ -d X (x)) - (2τ 2 -r 2 x -d X (x)(2τ -d X (x))) 2 4τ 2 . Proof of Lemma 17. For Čech X (X , r) ⊂ Čech R d (X , r), this is implied from B X (x, r x ) ⊂ B R d (x, r x ). For Čech R d (X , r) ⊂ Čech X (X , r ), let [x 1 , . . . , x k ] ∈ Čech R d (X , r), then there exists λ 1 , . . . , λ k ∈ [0, 1] with λ i = 1 such that u := λ i x i ∈ k i=1 B R d (x i , r xi ).
Then from Lemma 34,

x i -π X (u) ≤ 2τ u -x i 2 + d X (x i ) (2τ -d X (x i )) τ + τ 2 -u -x i 2 + d X (x i ) (2τ -d X (x i )) -d X (x i ) (2τ -d X (x i )) < 2τ r 2 xi + d X (x i ) (2τ -d X (x i )) τ + τ 2 -r 2 xi + d X (x i ) (2τ -d X (x i )) -d X (x i ) (2τ -d X (x i )) := r xi .
And hence

π X (u) ∈ k j=1 B X x j , r xj .
Therefore, [x 1 , . . . , x k ] ∈ Čech X (X , r ) as well, and hence Čech R d (X , r) ⊂ Čech X (X , r ) holds.

Then, Corollary 18 is a combination of Lemma 16 and 17. We restate Corollary 18 and formally write its proof.

Corollary 18. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a set of points. Let r = {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Then,

Čech X (X , r) ⊂ Rips(X , r) ⊂ Čech X (X , r ), where r = {r x > 0 : x ∈ X } with r x = 2τ 2d d+1 r 2 x + d X (x) (2τ -d X (x)) τ + τ 2 -2d d+1 r 2 x + d X (x) (2τ -d X (x)) -d X (x) (2τ -d X (x)).
Proof of Corollary 18. For Čech X (X , r) ⊂ Rips(X , r), this is implied by Lemma 16 and 17 as

Čech X (X , r) ⊂ Čech R d (X , r) ⊂ Rips(X , r).
For Rips(X , r) ⊂ Čech X (X , r ), this is again implied by Lemma 16 and 17 as

Rips(X , r) ⊂ Čech R d X , 2d d + 1 r ⊂ Čech X (X , r ).
To show Theorem 19 and 20, we consider a generalized commutative diagram of [START_REF] Chazal | Smooth manifold reconstruction from noisy and nonuniform approximation with guarantees[END_REF]. Let X be a paracompact space, let U = {U i } i∈I , U = {U i } i∈I , be good covers of X, and let S be a simplicial complex satisfying N U ⊂ S ⊂ N U , so that the following diagram commutes:

X φ } } N U ı N U →S ! ! ı N U →N U / / N U ψ a a S ı S→N U = = . ( 60
)
In Theorem 19, N U = Čech X (X , r), N U = Čech X (X , r ), and S = Čech R d (X , r), and in Theorem 20, N U = Čech X (X , r), N U = Čech X (X , r ), and S = Rips(X , r). Then our goal is to construct a homotopy equivalence between X and S. The maps between X and S are naturally defined as Φ : X → S and Ψ : S → X by Φ = ı N U →S • φ and Ψ = ψ • ı S→N U . Then, Ψ • Φ id X naturally follows by the commutative diagram in (60). However, Φ • Ψ id S needs an additional condition. We suppose the existence of ρ : S → N U such that ı N U →S • ρ : S → S is homotopy equivalent to id S : S → S, so that the following diagram commutes:

X φ } } N U ı N U →S ( ( ı N U →N U / / N U ψ a a S ρ g g ı S→N U = = . ( 61
)
Then Φ • Ψ id S can be deduced from this commutative diagram. We summarize this result in Lemma 40.

Lemma 40. Let X be a paracompact space, and let U = {U i } i∈I , U = {U i } i∈I , be good covers of X, with I ⊂ I and U i ⊂ U i for all i ∈ I. Let S be a simplicial complex satisfying N U ⊂ S ⊂ N U . Suppose there exists ρ : S → N U such that ı N U →S • ρ : S → S is homotopy equivalent to id S : S → S. Then X and S are homotopy equivalent.

Proof of Lemma 40. Let φ : X → N U and ψ : N U → X be the maps giving homotopy equivalence of the Nerve Theorem. Then from Lemma 26, the following diagram commutes at homotopy level:

X φ } } N U ı N U →N U / / N U ψ a a . ( 62
)
To show homotopy equivalence, we define maps Φ : X → S and Ψ : S → X by Φ = ı N U →S • φ and Ψ = ψ • ı S→N U . Then, we need to show that Ψ • Φ id X and Φ • Ψ id S on homotopy level.

For Ψ • Φ id X , consider the diagram below, which is (60):

X φ } } N U ı N U →S ! ! ı N U →N U / / N U ψ a a S ı S→N U = = .
Then from (62), ψ • ı N U →N U • φ id X holds, and hence

Ψ • Φ = ψ • ı S→N U • ı N U →S • φ = ψ • ı N U →N U • φ id X .
And hence Ψ • Φ id X on homotopy level.

For Φ • Ψ S , consider the diagram below, which is (61):

X φ } } N U ı N U →S ( ( ı N U →N U / / N U ψ a a S ρ g g ı S→N U = = .
Then ı N U →S • ρ id S holds from the condition, and from (62

), φ • ψ • ı N U →N U id N U holds, and hence Φ • Ψ = ı N U →S • φ • ψ • ı S→N U ı N U →S • φ • ψ • ı S→N U • ı N U →S • ρ = ı N U →S • φ • ψ • ı N U →N U • ρ ı N U →S • ρ id S .
And hence Φ • Ψ id S on homotopy level.

Hence for showing Theorem 19 and 20, the problem reduces to finding a subcomplex in Čech X (X , r) that is homotopy equivalent to S = Čech R d (X , r) or S = Rips(X , r). To do this, for each σ = [x 1 . . . x k ] ∈ S, we choose b σ to be a point in a convex hull of {x 1 , . . . , x k }, and we find y σ ∈ X to be a point close to π X (b σ ) such that

[x 1 , . . . , x k ] k i=1 [x 1 • • • xi • • • x k y σ ] in S. (63)
We use the notation [x 1 , . . . , x k ] to emphasize that each simplex is considered with its topology structure, and

[x 1 • • • xi • • • x k y σ ]
means that the vertex x i is removed. To show (63), we need several bounds for x i -y σ and y ς -y σ , which we collect in Claim 41.

Claim 41. Let τ > 0, X ⊂ R d be a subset with reach τ X ≥ τ > 0, and X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . For each σ ⊂ X , let σ ≥ 0 be satisfying d X (x) ≤ σ for all x ∈ σ. Let δ > 0, and suppose X ⊂ x∈X B X (x, δ). For each σ ⊂ X , let b σ be a point in the convex hull of σ, and let r σ := max x∈σ x -b σ . Then for each σ ⊂ X , there exists y σ ∈ X that satisfy the followings:

(i) If r σ < τ , then d X (b σ ) ≤ τ -(τ -σ ) 2 -r 2 σ . (ii) If r σ ≤ τ -σ , then x i -π X (b σ ) ≤ r2 bσ -σ (2τ -σ ),
and

x i -y σ < r2 bσ -σ (2τ -σ ) + δ,
where

r2 bσ := 2τ r 2 σ + σ (2τ -σ ) τ + τ 2 -(r 2 σ + σ (2τ -σ )) . (iii) If r σ < τ -σ and suppose ς ⊂ σ , then r2 bσ -σ (2τ -σ ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + δ 2 ,
and

y ς -y σ < r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ,
where r2 bσ is from (ii) and

r2 δ,b := min δ 2 + σ (2τ -σ ), 1 2 r 2 bσ .
(iv) Suppose that for all ς with {x 1 , . . . ,

x j } ⊂ ς ⊂ σ, b ς ∈ x∈ς B R d (x, r x ). If r σ < τ -σ and suppose δ + r 2 σ -l2 + σ (2τ -σ ) -((τ -σ ) 2 -r 2 σ + l2 + (τ -l) 2 )   τ τ 2 -r2 δ,c -1   ≤ r min , where l := 1 2 r min -τ + (τ -σ ) 2 -r 2 σ -δ , l := τ -(τ -σ ) 2 -r 2 σ + l, r2 δ,c := min δ 2 + σ (2τ -σ ), 1 2 (r 2 σ -l2 + σ (2τ -σ ) + l(2τ -l)) . Then σ ∈ Čech R d (X , r) implies that [x 1 • • • x j y [x1•••xj ] y [x1•••xj+1] • • • y [x1•••x k ] ] ∈ Čech R d (X , r). (v) If r σ < τ -σ and suppose r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ ≤ 2r min ,
where rbσ is from (ii) and rδ,b is from (iii), then σ ∈ Rips(X , r) implies that

[x 1 • • • x j y [x1•••xj ] y [x1•••xj+1] • • • y [x1•••x k ] ] ∈ Rips(X , r).
Proof of Claim 41. For choosing y σ ∈ X , we divide the problem into two cases. If d(π X (b σ ), σ) < δ, then choose y σ = arg min x∈σ x -π X (b σ ) . Otherwise, by using covering condition, choose y σ ∈ X be satisfying

y σ -π X (b σ ) < δ. (i) From d X (x i ) ≤ σ < τ for i = 1, . . . , k, d X (b σ ) ≤ r σ ≤ τ -σ , and d X (b σ ) < τ , applying Lemma 36 gives b σ -π X (b σ ) ≤ τ - (τ -) 2 - k i=1 λ i x i -b σ 2 + ≤ τ -(τ -σ ) 2 -r 2 σ .
(ii) Note that x i -b σ ≤ r σ ≤ τσ , so applying Lemma 34 gives

x i -π X (b σ ) ≤ 2τ x i -b σ 2 + σ (2τ -σ ) τ + τ 2 -x i -b σ 2 + σ (2τ -σ ) -σ (2τ -σ ). ≤ 2τ (r 2 σ + σ (2τ -σ )) τ + τ 2 -(r 2 σ + σ (2τ -σ )) -σ (2τ -σ ) ≤ r2 bσ -σ (2τ -σ ),
where

r2 bσ := 2τ r 2 σ + σ (2τ -σ ) τ + τ 2 -(r 2 σ + σ (2τ -σ ))
.

And hence

x i -y σ ≤ x i -π X (b σ ) + π X (b σ ) -y σ < r2 bσ -σ (2τ -σ ) + δ. (iii) Without loss of generality assume that ς = [x 1 • • • x j ] and σ = [x 1 • • • x k ] with j ≤ k.
Then (ii) implies that for each i = 1, . . . , j ,

x i -π X (b σ ) ≤ 2τ (r 2 σ + σ (2τ -σ )) τ + τ 2 -(r 2 σ + σ (2τ -σ )) -σ (2τ -σ ).
We divide the problem into two cases. First, consider the case d(b ς , ς) < δ. Then y ς = x l for some x l ∈ ς and

y ς -π X (b σ ) = x l -π X (b σ ) ≤ 2τ (r 2 σ + σ (2τ -σ )) τ + τ 2 -(r 2 σ + σ (2τ -σ )) -σ (2τ -σ ) = r2 bσ -σ (2τ -σ ), where r2 bσ = 2τ (r 2 σ + σ (2τ -σ )) τ + √ τ 2 -(r 2 σ + σ (2τ -σ ))
is from (ii). And hence for d(b ς , ς) < δ case,

y ς -y σ ≤ y ς -π X (b σ ) + π X (b σ ) -y σ < r2 bσ -σ (2τ -σ ) + δ. (64) Otherwise, d(b ς , ς) ≥ δ, i.e. x i -b ς ≥ δ for all 1 ≤ i ≤ j. Then π X (b σ ) -x i < 2τ ((τ -σ ) 2 + σ (2τ -σ )) τ + τ 2 -((τ -σ ) 2 + σ (2τ -σ )) -σ (2τ -σ ) = τ 2 + (τ -σ ) 2 .
So Lemma 37 is applicable and gives

π X (b σ ) -π X (b ς ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 bς ,bσ -1   , where r 2 bσ := k i=1 λ i x i -π X (b σ ) 2 + σ (2τ -σ ) , r 2 bς ,bσ := min k i=1 λ i x i -b ς 2 + σ (2τ -σ ) , 1 2 r 2 bσ .
Then, RHS is an increasing function of x i -π X (b σ ) 2 and a decreasing function of x i -b ς 2 , and from x i -b ς ≥ δ for all 1 ≤ i ≤ j , we have

π X (b ς ) -π X (b σ ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   , where r2 bσ = 2τ r 2 σ + σ (2τ -σ ) τ + τ 2 -(r 2 σ + σ (2τ -σ )) , r2 δ,b := min δ 2 + σ (2τ -σ ), 1 2 r2 bσ .
And hence for d(b ς , ς) ≥ δ case,

y ς -y σ ≤ y ς -π X (b ς ) + π X (b ς ) -π X (b σ ) + π X (b σ ) -y σ < r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ. ( 65
)
Hence ( 64) and (65) gives that for any case,

y ς -y σ < δ + max      r2 bσ -σ (2τ -σ ), r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + δ      . ( 66
) Now, we show r2 bσ -σ (2τ -σ ) ≤ r2 bσ -(2τ 2 -r2 bσ ) τ √ τ 2 -r 2 δ -1 + δ 2 .
We again divide it into two cases. First, when 1 2

r2 bσ ≤ δ 2 + σ (2τ -σ ), then r2 δ,b = 1 2 r2 bσ and therefore, r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   = r2 bσ -(2τ 2 -r2 bσ )   τ -τ 2 -1 2 r2 bσ τ 2 -1 2 r2 bσ   = 2τ 2 -2τ τ 2 - 1 2 r2 bσ = 2τ 2 -4τ 4 -2τ 2 r2 bσ ≥ 2τ 2 -4τ 4 -2τ 2 r2 bσ + 1 4 r4 bσ = 1 2 r2 bσ ≥ r2 bσ -(δ 2 + σ (2τ -σ )) = r2 bσ -σ (2τ -σ ) -δ 2 . And hence for 1 2 r2 bσ ≤ δ 2 + σ (2τ -σ ) case, r2 bσ -σ (2τ -σ ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r 2 δ -1   + δ 2 . ( 67
)
Second, when

δ 2 + σ (2τ -σ ) ≤ 1 2 r2 bσ , then r2 δ,b = δ 2 + σ (2τ -σ ), and therefore, r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   = r2 bσ -(2τ 2 -r2 bσ )   τ -τ 2 -r2 δ,b τ 2 -r2 δ,b   = r2 bσ - (2τ 2 -r2 bσ )r 2 δ,b τ 2 -r2 δ,b (τ + τ 2 -r2 δ,b )
.

Then from r2 δ,b = δ 2 + σ (2τ -σ ) ≤ 1 2 r2 bσ , 2τ 2 -r 2 bσ τ 2 -r 2 δ,b (τ + τ 2 -r 2 δ,b )
is lower bounded as

2τ 2 -r2 bσ τ 2 -r2 δ,b (τ + τ 2 -r2 δ,b ) = 2τ 2 -r2 bσ τ 2 -r2 δ,b + τ τ 2 -r2 δ,b ≤ 2τ 2 -r2 bσ τ 2 -r2 δ,b + (τ 2 -r2 δ,b ) ≤ 2τ 2 -r2 bσ 2τ 2 -r2 bσ = 1,
and hence

r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   = r2 bσ - (2τ 2 -r2 bσ )r 2 δ,b τ 2 -r2 δ,b (τ + τ 2 -r2 δ,b ) ≥ r2 bσ -r2 δ,b = r2 bσ -σ (2τ -σ ) -δ 2 . And hence for δ 2 + σ (2τ -σ ) ≤ 1 2 r2 bσ case, r2 bσ -σ (2τ -σ ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r 2 δ -1   + δ 2 . ( 68
)
Hence from and (68), for any case,

r2 bσ -σ (2τ -σ ) ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r 2 δ -1   + δ 2 .
and applying this to (66) gives that

y ς -y σ < r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ.
(iv) We need to find b ∈ R d and check that x i -b < r xi for i = 1, . . . , k and y ς -b < r yς for all ς with {x 1 , . . . , x j } ⊂ ς ⊂ σ = {x 1 , . . . , x k }. We let

l := 1 2 r min -τ + (τ -σ ) 2 -r 2 σ -δ ,
and divide the problem into two cases.

First, if all ς with {x 1 , . . . , x j } ⊂ ς ⊂ σ satisfy that b ς -b σ ≤ l, then we can set b := b σ . For this case, for i = 1, . . . , j,

x i -b = x i -b σ < r xi ,
and for any ς with {x 1 , . . . , x j } ⊂ ς ⊂ σ, (i) and the covering condition imply

y ς -b ≤ y ς -π X (b ς ) + π X (b ς ) -b ς + b ς -b σ < δ + τ -(τ -σ ) 2 -r 2 σ + l = r min -l ≤ r min ≤ r yς .
x i -b ≤ l b σ -b σ x i -b σ 2 + 1 - l b σ -b σ x i -b σ 2 < r xi . ( 69
)
Next, we show that for all ς with σ

ς ⊂ σ, y ς -b < r yς . Note that b -b ς ≤ b -b σ + b σ -b ς ≤ 2 l,
and then (i) and the covering condition imply

y ς -b ≤ y ς -π X (b ς ) + π X (b ς ) -b ς + b ς -b σ < δ + τ -(τ -σ ) 2 -r 2 σ + 2 l = r min ≤ r yς .
Finally, we show that for all ς ⊂ σ, y ς -b < r yς . Note that r σ ≤ r 2 σ -b σ -b σ 2 , so

x i ∈ B R d (b σ , r σ ) ∩ B R d (b σ , r σ ) ⊂ B R d ( b, r 2 σ -l2 ) holds. Hence for all i = 1, . . . , k, b -x i < r 2 σ -l2 ≤ r σ . ( 70
)
We again divide it into two cases. First, consider the case d(b ς , ς) < δ. Then y ς = x l for some x l ∈ ς, hence from (69),

y ς -b = x l -b < r x l = r yς .
Otherwise, x i -b ς ≥ δ for all x i ∈ ς. Then (i) implies

d X ( b) ≤ d X (b σ ) + b -b σ ≤ τ -(τ -σ ) 2 -r 2 σ + l.
And from (70), Lemma 37 is applicable and gives an upper bound for π X (b ς ) -b as

π X (b ς ) -b ≤ r2 b -(τ 2 -r2 b + (τ -l) 2 )   τ τ 2 -r2 bς , b -1   ,
where

l := τ -(τ -σ ) 2 -r 2 σ + l, r2 b := k i=1 λ i x i -b 2 + σ (2τ -σ ) , r2 bς , b := min k i=1 λ i x i -b ς 2 + σ (2τ -σ ) , 1 2 (r 2 b + l(2τ -l)) .
Then, RHS is an increasing function of x i -b 2 and decreasing function of x i -b ς 2 , so applying (70) and from x i -b ς 2 ≥ δ for all x i ∈ ς, we have

π X (b ς ) -b ≤ r 2 σ -l2 + σ (2τ -σ ) -((τ -σ ) 2 -r 2 σ + l2 + (τ -l) 2 )   τ τ 2 -r2 δ,c -1   , where r2 δ,c := min δ 2 + σ (2τ -σ ), 1 2 (r 2 σ -l2 + σ (2τ -σ ) + l(2τ -l)) .
Then,

y ς -b ≤ y ς -π X (b ς ) + π X (b ς ) -b < δ + r 2 σ -l2 + σ (2τ -σ ) -((τ -σ ) 2 -r 2 σ + l2 + (τ -l) 2 )   τ τ 2 -r2 δ,c -1   ≤ r min < r yς . (v)
We need to check that x i -y σ < r xi + r yσ and y ς -y σ < r yς + r yσ . For x i -y σ < r xi + r yσ , note that (ii) (iii) and the condition on δ gives

x 1 -y σ < r2 bσ -σ (2τ -σ ) + δ ≤ r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ ≤ 2r min ≤ r xi + r y0 ,
where rbσ is from (ii) and rδ,b is from (iii).

For y ς -y σ < r yς + r yσ , note that (iii) and the condition on δ gives

y ς -y σ < r2 bσ -(2τ 2 -r2 bσ )   τ τ 2 -r2 δ,b -1   + 2δ ≤ 2r min ≤ r yς + r y0 .
After repeating (63) several times, we get the homotopy equivalence as

[x 1 • • • x k ] ω∈S k [x 1 y [x ω(1) x ω(2) ] • • • y [x1•••x k ] ] in S, (71)
where S k is the permutation group of size k. Since we are trying to map S = Čech R d (X , r) or Rips(X , r) to into Čech X (X , r) which is consisting of smaller simplices, we want to each simplex [x 1 y [x ω [START_REF] Aamari | Estimating the reach of a manifold[END_REF] x ω( 2

) ] • • • y [x1•••x k ]
] be of smaller size. We measure the size by Rad r (σ) or Rad(σ) as introduced in (58) and (59). We collect several bounds for Rad r (σ) or Rad(σ) in Claim 42.

Claim 42. Let τ > 0, X ⊂ R d be a subset with reach τ X ≥ τ > 0, and X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X . Let ≥ 0 be satisfying d X (x) ≤ for all x ∈ X . Let δ > 0, and suppose X ⊂ x∈X B X (x, δ).

(i) Rad r (σ) ≤ r max r min Rad(σ),
where r min = min{r x : x ∈ X } and r max = max{r x : x ∈ X }. (ii) bc r and Rad r satisfy the following: for each σ = {x 1 , . . . , x k } ⊂ X , y σ ∈ X can be chosen so that if

r σ := Rad r (σ) < τ -σ , then Rad r ({x 1 y {x1x2} . . . y {x1•••x k } }) ≤ d 2(d + 1) r max r min    r2 b -(2τ 2 - b )   τ τ 2 -r2 δ,b -1   + 2δ    , where r2 b := 2τ r 2 σ + (2τ -) τ + τ 2 -(r 2 σ + (2τ -)) , r2 δ,b := min δ 2 + (2τ -), 1 2 r2 b . Further, if δ + r 2 σ -l2 + (2τ -) -((τ -) 2 -r 2 σ + l2 + (τ -l) 2 )   τ τ 2 -r2 δ,c -1   ≤ r min , where l := 1 2 r min -τ + (τ -) 2 -r 2 σ -δ , l := τ -(τ -) 2 -r 2 σ + l, r2 δ,c := min δ 2 + (2τ -), 1 2 (r 2 σ -l2 + (2τ -) + l(2τ -l)) . then σ ∈ Čech R d (X , r) implies that {x 1 • • • x j y {x1•••xj } y {x1•••xj+1} • • • y {x1•••x k } } ∈ Čech R d (X , r).
(iii) bc and Rad satisfy the following: for each σ = {x 1 , . . . , x k } ⊂ X , y σ ∈ X can be chosen so that if

r σ := Rad(σ) < τ -σ , then Rad({x 1 y {x1x2} . . . y {x1•••x k } }) ≤ d 2(d + 1)    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    , where r2 b := 2τ r 2 σ + (2τ -) τ + τ 2 -(r 2 σ + (2τ -)) , r2 δ,b := min δ 2 + (2τ -), 1 2 r 2 b . Further, if r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ ≤ 2r min , then σ ∈ Rips(X , r) implies that [x 1 • • • x j y {x1•••xj } y {x1•••xj+1} • • • y {x1•••x k } ] ∈ Rips(X , r). Proof of Claim 42. (i) From bc r (σ) = arg min y∈R d max x∈σ x-y rx , Rad r (σ) = max x∈σ x -bc r (σ) ≤ r max max x∈σ x -bc r (σ) r x ≤ r max max x∈σ x -bc(σ) r x ≤ r max r min max x∈σ x -bc(σ) = r max r min Rad(σ). Conversely, from bc(σ) = arg min y∈R d max x∈σ x -y , Rad(σ) = max x∈σ x -bc(σ) ≤ max x∈σ x -bc r (σ) = Rad r (σ).
(ii) For each σ ⊂ X , we set b σ := bc r (σ) and choose the corresponding y σ ∈ X according to Claim 41. Note that Rad r (σ) = max x∈σ x -b σ . Then Claim 41 (ii) implies that

x i -y σ < r2 b -σ (2τ -σ ) + δ,
and Claim 41 (iii) implies that for any ς ⊂ σ,

y ς -y σ < r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ. Then from Claim 41 (iii), r2 b -σ (2τ -σ ) + δ ≤ r2 b -(2τ 2 -r2 b ) τ τ 2 -r 2 δ,b -1 + 2δ, and hence {x 1 , y {x1x2} , . . . , y {x1•••x k } } ∈ Rips   X , 1 2    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ       .
And Lemma 16 implies that

{x 1 , y {x1x2} , . . . , y {x1•••x k } } ∈ Čech R d   X , d 2(d + 1)    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ       .

And hence

Rad({x 1 , y {x1x2} , . . . , y {x1

•••x k } }) ≤ d 2(d + 1)    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    . Then from (i), Rad r ({x 1 , y {x1x2} , . . . , y {x1•••x k } }) ≤ d 2(d + 1) r max r min    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    .
Further, Claim 41 (iv) implies that if

δ + r 2 σ -l2 + (2τ -) -((τ -) 2 -r 2 σ + l2 + (τ -l) 2 )   τ τ 2 -r2 δ,c -1   ≤ r min , then σ ∈ Čech R d (X , r) implies that b ς = bc r (ς) ∈ x∈ς B R d (x, r x ). And hence {x 1 , . . . , x j , y {x1•••xj } , y {x1•••xj+1} , . . . , y {x1•••x k } } ∈ Čech R d (X , r).
(iii) For each σ ⊂ X , we set b σ := bc(σ) and choose the corresponding y σ ∈ X according to Claim 41. Note that Rad(σ) = max x∈σ x -b σ . Then Claim 41 (ii) implies that

x i -y σ < r2 b -σ (2τ -σ ) + δ,
and Claim 41 (iii) implies that for any ς ⊂ σ,

y ς -y σ < r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ. Then from Claim 41 (iii), r2 b -σ (2τ -σ ) + δ ≤ r2 b -(2τ 2 -r2 b ) τ τ 2 -r 2 δ,b -1 + 2δ, and hence {x 1 , y {x1x2} , . . . , y {x1•••x k } } ∈ Rips   X , 1 2    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ       .
And Lemma 16 implies that

{x 1 , y {x1x2} , . . . , y {x1•••x k } } ∈ Čech R d   X , d 2(d + 1)    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ       .

And hence

Rad({x 1 , y {x1x2} , . . . , y {x1

•••x k } }) ≤ d 2(d + 1)    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    . Further, Claim 41 (v) implies that if r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ ≤ 2r min , then σ ∈ Rips(X , r) implies that {x 1 , . . . , x j , y {x1•••xj } , y {x1•••xj+1} , . . . , y {x1•••x k } } ∈ Rips(X , r).
For Theorem 19, Claim 41 and 42 imply that there exists a map ρ : r) . Then from Lemma 17, the following diagram commutes:

Čech R d (X , r) → Čech X (X , r) that ı Čech X (X ,r)→Čech R d (X ,r) • ρ : Čech R d (X , r) → Čech R d (X , r) is homotopic to the identity id Čech R d (X ,
X φ y y Čech X (X , r) ı Čech X (X ,r)→Čech R d (X ,r) * * ı Čech X (X ,r)→Čech X (X ,r ) / / Čech X (X , r ) ψ e e S ρ g g ı Čech R d (X ,r)→Čech X (X ,r ) 9 9
. Then Lemma 40 implies that X is homotopy equivalent to the ambient Čech complex Čech R d (X , r). We restate Theorem 19 and formally write its proof below.

Theorem 19. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a closed discrete set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := inf x∈X {r x } > 0 and r max := sup x∈X {r x } < ∞, and let := sup{d X (x) : x ∈ X }. Suppose X is covered by the union of balls centered at x ∈ X and radius δ as

X ⊂ x∈X B R (x, δ).
Suppose that the maximum radius r max is bounded as

r max ≤ τ -.
Also, suppose δ satisfies the following condition:

δ + r 2 max -l2 + (2τ -) -((τ -) 2 -r 2 max + l2 + (τ -l) 2 ) τ τ 2 -rδ,c -1 ≤ r min , d 2(d + 1) r max r min    r2 b -(2τ 2 -r2 b )   τ τ 2 -r2 δ,b -1   + 2δ    ≤ r min , l := 1 2 r min -τ + (τ -) 2 -r 2 max -δ , l := τ -(τ -) 2 -r 2 max + l, r2 δ,c := min δ 2 + (2τ -), 1 2 (r 2 max -l2 + (2τ -) + l(2τ -l)) , r min := τ 2 -(2τ -) - (2τ 2 -r 2 min -(2τ -)) 2 4τ 2 , r2 b := 2τ (r min ) 2 + (2τ -) τ + τ 2 -((r min ) 2 + (2τ -)) , r2 δ,b := min δ 2 + (2β -), 1 2 r2 b .
Then X is homotopy equivalent to the ambient Čech complex Čech R d (X , r).

Proof of Theorem 19. For a simplex σ

= [x 1 • • • x k ] ∈ Čech R d (X , r), let r σ := Rad r (σ),
and choose y σ ∈ X according to Claim 42. Then as long as

r σ < τ -σ , Claim 42 (ii) asserts that [x 1 • • • x k y [x1•••x k ] ] ∈ Čech R d (X , r) holds. Now, define the homotopy map F 1 : [x 1 • • • x k ] × [0, 1] → [x 1 • • • x k y [x1•••x k ] ] as F 1 k i=1 λ i x i , t = k i=1 (λ i -min λ i )x i + k min λ i ty σ + (1 -t) 1 k k i=1 x i .
Then F 1 gives homotopy between ı σ→σ * yσ and f 1 : σ → σ * y σ defined as

f 1 k i=1 λ i x i = k i=1 (λ i -min λ i )x i + (k min λ i )y σ ,
giving homotopy equivalence as

[x 1 • • • x k ] k i=1 [x 1 • • • xi • • • x k y [x1•••x k ] ] in Čech R d (X , r).
And again, Claim 42 (ii) asserts that [

x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ] ∈ Čech R d (X , r) holds. Now, the homotopy map F 2 : [x 1 • • • x k-1 y [x1•••x k ] ] × [0, 1] → [x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ]
is defined as

F 2 k-1 i=1 λ i x i + λ k y [x1•••x k ] , t = λ k y [x1•••x k ] + k-1 i=1 (λ i -min λ i )x i + (k -1) min λ i ty [x1•••x k-1 ] + (1 -t) 1 k -1 k-1 i=1 x i . Then F 2 gives homotopy between ı [x1•••x k-1 y [x 1 •••x k ] ]→[x1•••x k-1 y [x 1 •••x k-1 ] y [x 1 •••x k ] ] and f 2 : [x 1 • • • x k-1 y [x1•••x k ] ] → [x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ] defined as f 2 k-1 i=1 λ i x i + λ k y [x1•••x k ] = λ k y [x1•••x k ] + k-1 i=1 (λ i -min λ i )x i + (k -1) min λ i y [x1•••x k-1 ] ,
giving the homotopy equivalence as

[x 1 • • • x k-1 y [x1•••x k ] ] k-1 i=1 [x 1 • • • xi • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ] in Čech R d (X , r).
By repeating this and concatenating the homotopy maps, we have the homotopy map

F σ : σ ×[0, 1] → Čech R d (X , r) giving homotopy between ı σ→Čech R d (X ,r) and f σ : σ → Čech R d (X , r) with f σ (σ) = ω∈S k [x ω(1) y [x ω(1) x ω(2) ] . . . y [x1•••x k ] ], i.e. F σ is giving homotopy equivalence between [x 1 , . . . , x k ] and ω∈S k [x ω(1) y [x ω(1) x ω(2) ] . . . y [x1•••x k ] ] in Čech R d (X , r).
Now, we extend f σ and F σ to the entire ambient Čech complex Čech R d (X , r). Define

f : Čech R d (X , r) → Čech R d (X , r) and F : Čech R d (X , r) × [0, 1] → Čech R d (X , r) as f | σ = f σ and F | σ×[0,1] = F σ for each σ ∈ Čech R d (X , r). Then for σ, τ ∈ Čech R d (X , r), F σ and F τ coincides on σ ∩ τ × [0, 1]
, so f and F are well defined. Also, from X being closed and discrete, Čech R d (X , r) is locally finite. Hence for any compact set C ⊂ Čech R d (X , r), C intersects with only finite number of simplices σ

1 , . . . , σ k ∈ Čech R d (X , r), so F -1 (C) = k i=1 F -1
σi (C) is compact, and hence F is continuous. So F gives the homotopy between id Čech R d (X ,r) and f . Now, applying Claim 42 (ii) gives that Hence by repeating this sufficiently many times (say N ), we can guarantee f (N ) (Čech R d (X , r)) to be consisting of simplices with their radii (i.e. Rad(σ)) at most rσ , where rσ is the solution of then f (r min ) ≤ 0 implies that rσ ≤ r min . Hence satisfying f (r min ) ≤ 0 implies that f (N ) (Čech R d (X , r)) ⊂ Čech R d (X , r min ). And Lemma 17 implies that

Rad r ([x ω(1) y [x ω(1) x ω(2) ] • • • y [x1•••x k ] ]) ≤ d 2(d + 1)
f (t) = d 2(d + 1)
f (N ) (Čech R d (X , r)) ⊂ Čech R d (X , r min ) ⊂ Čech X (X , r min ) ⊂ Čech X (X , r),
i.e. f (N ) : Čech R d (X , r) → Čech X (X , r). Then by construction, ı Čech X (X ,r)→Čech R d (X ,r) • f (N ) is homotopy equivalent to id Čech R d (X ,r) . Hence by applying Lemma 40, X and Čech R d (X , r) are homotopy equivalent.

For Theorem 20, Claim 41 and 42 imply that there exists a map ρ : Rips(X , r) → Čech X (X , r) that ı Čech X (X ,r)→Rips(X ,r) • ρ : Rips(X , r) → Rips(X , r) is homotopic to the identity id Rips(X ,r) . Then from Corollary 18, the following diagram commutes: X φ w w Čech X (X , r) ı Čech X (X ,r)→Rips(X ,r)) )

ı Čech X (X ,r)→Čech X (X ,r ) / / Čech X (X , r ) ψ g g Rips(X , r) ρ i i ı Rips(X ,r)→Čech X (X ,r ) 7 7

.

Then Lemma 40 implies that X is homotopy equivalent to the Vietoris-Rips complex Rips(X , r). We restate Theorem 20 and formally write its proof below.

Theorem 20. Let X ⊂ R d be a subset with reach τ > 0 and let X ⊂ R d be a closed discrete set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := inf x∈X {r x } > 0 and r max := sup x∈X {r x } < ∞, and let := sup{d X (x) : x ∈ X }. Suppose X is covered by the union of balls centered at x ∈ X and radius δ as

X ⊂ x∈X B R (x, δ).
Suppose that the maximum radius r max is bounded as

r max ≤ d + 1 2d (τ -) .
Also, suppose δ satisfies the following condition: Then X is homotopy equivalent to the Vietoris-Rips complex Rips(X , r).

Proof of Theorem 20. For a simplex σ = [x 1 • • • x k ] ∈ Rips(X , r), let r σ := Rad(σ), and choose y σ ∈ X according to Claim 42. Then as long as r σ < τσ , Claim 42 (iii) asserts that

[x 1 • • • x k y [x1•••x k ]
] ∈ Rips(X , r) holds. Now, define the homotopy map

F 1 : [x 1 • • • x k ]×[0, 1] → [x 1 • • • x k y [x1•••x k ] ] as F 1 k i=1 λ i x i , t = k i=1 (λ i -min λ i )x i + k min λ i ty σ + (1 -t) 1 k k i=1 x i .
Then F 1 gives homotopy between ı σ→σ * yσ and f 1 : σ → σ * y σ defined as

f 1 k i=1 λ i x i = k i=1
(λ i -min λ i )x i + (k min λ i )y σ , giving homotopy equivalence as

[x 1 • • • x k ] k i=1 [x 1 • • • xi • • • x k y [x1•••x k ] ] in Rips(X , r)
And again, Claim 42 (iii) asserts that [

x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ]
] ∈ Rips(X , r) holds. Now, the homotopy map

F 2 : [x 1 • • • x k-1 y [x1•••x k ] ] × [0, 1] → [x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ]
is defined as

F 2 k-1 i=1 λ i x i + λ k y [x1•••x k ] , t = λ k y [x1•••x k ] + k-1 i=1 (λ i -min λ i )x i + (k -1) min λ i ty [x1•••x k-1 ] + (1 -t) 1 k -1 k-1 i=1 x i . Then F 2 gives homotopy between ı [x1•••x k-1 y [x 1 •••x k ] ]→[x1•••x k-1 y [x 1 •••x k-1 ] y [x 1 •••x k ] ] and f 2 : [x 1 • • • x k-1 y [x1•••x k ] ] → [x 1 • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ] defined as f 2 k-1 i=1 λ i x i + λ k y [x1•••x k ] = λ k y [x1•••x k ] + k-1 i=1 (λ i -min λ i )x i + (k -1) min λ i y [x1•••x k-1 ] ,
giving the homotopy equivalence as

[x 1 • • • x k-1 y [x1•••x k ] ] k-1 i=1 [x 1 • • • xi • • • x k-1 y [x1•••x k-1 ] y [x1•••x k ] ] in Rips(X , r)
By repeating this and concatenating the homotopy maps, we have the homotopy map F σ : σ × [0, 1] → Rips(X , r) giving homotopy between ı σ→Rips(X ,r) and f σ : σ → Rips(X , r) with f σ (σ) = ω∈S k [x ω(1) y [x ω [START_REF] Aamari | Estimating the reach of a manifold[END_REF] x ω( 2 Now, we extend f σ and F σ to the entire Vietoris-Rips complex Rips(X , r). Define f : Rips(X , r) → Rips(X , r) and F : Rips(X , r) × [0, 1] → Rips(X , r) as f | σ = f σ and F | σ×[0,1] = F σ for each σ ∈ Rips(X , r). Then for σ, τ ∈ Rips(X , r), F σ and F τ coincides on σ ∩ τ × [0, 1], so f and F are well defined. Also, from X being closed and discrete, Rips(X , r) is locally finite. Hence for any compact set C ⊂ Rips(X , r), C intersects with only finite number of simplices σ 1 , . . . , σ k ∈ Rips(X , r), so

F -1 (C) = k i=1 F -1
σi (C) is compact, and hence F is continuous. So F gives the homotopy between id Rips(X ,r) and f . Now, applying Claim 42 (iii) gives that Rad([x ω(1) y [x ω [START_REF] Aamari | Estimating the reach of a manifold[END_REF] x ω( 2 Hence by repeating this sufficiently many times (say N ), we can guarantee f (N ) (Rips(X , r)) to be consisting of simplices with their radii (i.e. Rad(σ)) at most rσ , where rσ is the solution of then f (r min ) ≤ 0 implies that rσ ≤ r min . Hence satisfying f (r min ) ≤ 0 implies that f (N ) (Rips(X , r)) ⊂ Čech R d (X , r min ). And Lemma 17 implies that f (N ) (Rips(X , r)) ⊂ Čech R d (X , r min ) ⊂ Čech X (X , r min ) ⊂ Čech X (X , r),

) ] • • • y [x1•••x k ] ]) ≤ d 2(d + 1)
f (t) = d 2(d + 1)    r2 b (t) -(2τ
i.e. f (N ) : Rips(X , r) → Čech X (X , r). Then by construction, ı Čech X (X ,r)→Rips(X ,r) • f (N ) is homotopy equivalent to id Rips(X ,r) . Hence by applying Lemma 40, X and Rips(X , r) are homotopy equivalent. Now, Corollary 22 is from the combination of Corollary 15 and Theorem 19 and 20. We restate Corollary 22 and formally write its proof below.

Corollary 22. Let X ⊂ R d be a subset with positive µ-reach τ µ > 0 and let X ⊂ R d be a set of points. Let {r x > 0 : x ∈ X } be a set of radii indexed by x ∈ X with r min := min x∈X {r x } and r max := max x∈X {r x }. Let s, t, ≥ 0 with t µ < s < τ µ , and let Y := (((X s ) ) t ) be the double offset, with d Y (x) ≤ for all x ∈ X . Suppose Y is covered by the union of balls centered at x ∈ X and radius δ as Then X is homotopy equivalent to the ambient Čech complex Čech R d (X , r).

(ii) Suppose r max ≤ d+1 2d (t -), and δ satisfies the following condition: Then X is homotopy equivalent to the Vietoris-Rips complex Rips(X , r).

Proof of Corollary 22. Consider the double offset Y := (((X s ) ) t ) . Since X has a positive µ-reach τ µ , s ≤ τ µ and t ≤ µs, Corollary 15 implies that the reach of Y is bounded by τ Y ≥ t.

(i) For the ambient Čech complex case, r x ≤ t -≤ τ Y -holds, so Theorem 19 applies under the appropriate condition of δ.

(ii)

For the Vietoris-Rips complex case, r x ≤ d+1 2d (t -) ≤ d+1 2d (τ Y -) as well, so Theorem 20 applies under the appropriate condition of δ.

To prove the covering lemma 23, we first show the following upper bound on the covering number holds.

Claim 43. Suppose the distribution P satisfies the (a, b)-condition in [START_REF] Edelsbrunner | Computational Topology: An Introduction[END_REF]. Then for all < 0 , the covering number N (X, • , 2 ) is bounded as

N (X, • , 2 ) ≤ 1 a -b .

x∈IBX

  (x, r x ), F (y, 0) = y and F (y, 1) = y 0 , and for all t ∈ [0, 1], F (y 0 , t) = y 0 . Hence the intersection x∈I B X (x, r x ) deformation retracts to a point {y 0 }. And hence the intersection x∈I B X (x, r x ) is contractible.

For

  the other case, let k := max j : b[x1•••xj ] -b σ > l be the largest integer that b [x1•••xj ] -b σ > l , and let σ := [x 1 • • • x k]. Let b := l bσ-b σ b σ + 1 -l bσ-b σ b σ , so that b -b σ = l. We first show that b -x i < r xi for i = 1, . . . , k. Since x i -b σ < r xi andx i -b σ < r xi , and hence from Claim 35,

  2τ -) τ + τ 2 -(r 2 σ + (2τ -)) , r2 δ,b := min δ 2 + (2τ -

τ 2 -

 2 (t 2 + (2τ -)) and r2 δ,b (t) = min δ 2 + (2τ -), 1 2 r2 b (t) . Let r min := τ 2 -(2τ -) -(2τ 2 -r 2 min -(2τ -)) 2 4τ 2 ,

  r2 b (r max ) -(2τ 2 -r2 b (r max )) b (r min ) -(2τ 2 -r2 b (r min )) min ,wherer min := τ 2 -(2τ -) -(2τ 2 -r 2 min -(2τ -)) 2 4τ 2 , r2 b (t) := 2τ t 2 + (2τ -) τ + τ 2 -(t 2 + (2τ -)) , r2 δ,b (t) := min δ 2 + (2τ -

  ) ] . . . y [x1•••x k ] ], i.e. F σ is giving homotopy equivalence between [x 1 , . . . , x k ] and ω∈S k [x ω(1) y [x ω(1) x ω(2) ] . . . y [x1•••x k ] ] in Rips(X , r).

  2τ -) τ + τ 2 -(r 2 σ + (2τ -)) , r2 δ,b := min δ 2 + (2τ -

  2τ (t 2 + (2τ -)) τ + √ τ 2 -(t 2 + (2τ -)) and r2 δ,b (t) = min δ 2 + (2τ -), 1 2 r2 b (t) . Let r min := τ 2 -(2τ -) -(2τ 2 -r 2 min -(2τ -)) 2 4τ 2 ,

1 ≤

 1 (i) Suppose r max ≤ t -, and δ satisfies the following condition:δ + r 2 max -l2 + (2t -) -((t -) 2 -r 2 max + l2 + (tl) 2 ) t t 2 -rδ,c --t + (t -) 2 -r 2 max -δ , l := t -(t -) 2 -r 2 max + l, r2 δ,c := min δ 2 + (2tmax -l2 + (2t -) + l(2tl)) , r min := t 2 -(2t -) -(2t 2 -r 2 min -(2t -)) 2 4t 2 , r2 b := 2t (r min ) 2 + (2t -) t + t 2 -((r min ) 2 + (2t -)) , r2δ,b := min δ 2 + (2t -

  r2 b (r max ) -(2t 2 -r2 b (r max )) b (r min ) -(2t 2 -r2 b (r min )) min ,wherer min := t 2 -(2t -) -(2t 2 -r 2 min -(2t -)) 2 4t 2 , r2 b (t) := 2t t 2 + (2t -) t + t 2 -(t 2 + (2t -)) , r2δ,b (t) := min δ 2 + (2t -

22

  Karsten Grove. Critical point theory for distance functions. In Differential geometry: Riemannian geometry (Los Angeles,CA, 1990), volume 54 of Proc. Sympos. Pure Math., pages 357-385. Amer. Math. Soc., Providence, RI, 1993. 23 Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. 24 Jean-Claude Hausmann. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. In Prospects in topology (Princeton, NJ, 1994), volume 138 of Annals of Mathematics Studies, pages 175-188. Princeton Univ. Press, Princeton, NJ, 1995. 25 Janko Latschev. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Introduction to smooth manifolds, volume 218 of Graduate Texts in Mathematics. Springer, New York, second edition, 2013. 27 Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Amit Singer and Hau-Tieng Wu. Vector diffusion maps and the connection laplacian. Communications on Pure and Applied Mathematics, 65(8):1067-1144, 2012. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21395, arXiv:https:// onlinelibrary.wiley.com/doi/pdf/10.1002/cpa.21395, doi:10.1002/cpa.21395. 30 Jean-Luc Starck, Vicent Martínez, D. Donoho, Ofer Levi, Philippe Querre, and Enn Saar.

	Archiv der Mathematik, 77(6):522-528, 2001. URL: https://doi.org/10.1007/PL00000526,
	doi:10.1007/PL00000526.
	26 John M. Lee. Discrete & Computational Geometry, 39(1-
	3):419-441, 2008. URL: http://dx.doi.org/10.1007/s00454-008-9053-2, doi:10.1007/
	s00454-008-9053-2.
	28 Vanessa Robins, James D. Meiss, and Elizabeth Bradley. Computing connectedness: dis-
	connectedness and discreteness. Physica D: Nonlinear Phenomena, 139(3):276 -300,
	2000. URL: http://www.sciencedirect.com/science/article/pii/S0167278999002286,
	doi:https://doi.org/10.1016/S0167-2789(99)00228-6.
	29

Analysis of the spatial distribution of galaxies by multiscale methods. EURASIP Journal on Applied Signal Processing, 2005(15):2455-2469, 2005. URL: https://doi.org/10.1155/ASP. 2005.2455, doi:10.1155/ASP.2005.2455.

Herbert Edelsbrunner and Ernst P. Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43-72, January 1994. URL: http://doi.acm.org/10.1145/174462.156635, doi:10.1145/174462.156635.

Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93:418-491, 1959. URL: https://doi.org/10.2307/1993504, doi:10.2307/1993504.

Partially supported by Samsung Scholarship

Acknowledgements We want to thank André Lieutier and Henry Adams for the thoughtful discussions and comments.

Proof of Claim 43. Let x 1 , . . . , x M be a maximal 2 -packing of X, with M = M(X, • , 2 ). Then B R d (x i , ) and B R d (x j , ) do not intersect for any i, j, and hence

Then for all < 0 , the (a, b)-condition implies

hence applying this to (72) gives that

Then from the relationship between the covering number and the packing number,

Now, we restate Lemma 23 and formally write its proof below. Lemma 23. Let {X 1 , . . . , X n } be an i.i.d. sample from the distribution P and let {r n = (r n,1 , . . . , r n,n )} n∈N be a triangular array of positive numbers such that, for each n,

log n an

Then, the probability that the sample is an r n -covering of X is bounded as

Proof of Lemma 23. Now, to prove Lemma 23, set := 1 4 min i r n,i . Under the (a, b)condition, the previous claim 43 implies that there exists x 1 , . . . , x N with N ≤ a -1 -b satisfying

Let E be the event that all B R d (x j , 2 ) have intersections with {X 1 , . . . , X n }, that is, for each 1 ≤ j ≤ N , there exists 1 ≤ i ≤ n with X i ∈ B R d (x j , 2 ). Then note that 4 = min i r n,i ≤ r n,i , and hence we have the following relations between balls:

Therefore, under the event E, we have

Now, P (E) can be lower bounded as

where the last line is from that 1 -t ≤ exp(-t) for all t ∈ R. Now, from the covering number bound N ≤ a -1 -b with the condition, 2 =