Abstract 1 Introduction 2 Preliminaries 3 Overview of the first two main results: Manifolds of positive reach, differentiability, and tangent variation 4 Global and local reach References

Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach

André Lieutier ORCID Aix-en-Provence, France    Mathijs Wintraecken ORCID Inria Centre d’Université Côte d’Azur, Sophia Antipolis, France
Abstract

This paper contains three main results.

Firstly, we give an elementary proof of the following statement: Let be a topological manifold without boundary embedded in d. If has positive reach, then can locally be written as the graph of a C1,1 function from the tangent space to the normal space. Conversely if can locally be written as the graph of a C1,1 function from the tangent space to the normal space, then has positive reach. The result was hinted at by Federer when he introduced the reach, and proved by Lytchak. Lytchak’s proof relies heavily on CAT(k)-theory. The proof presented here uses only basic results on homology.

Secondly, we give optimal Lipschitz-constants for the derivative, in other words we give an optimal bound for the angle between tangent spaces in term of the distance between the points. We stress that Lytchak did not provide any bound, let alone an optimal one, making his proof, although interesting from a mathematical perspective, ineffectual in an algorithmic setting. To provide precise and optimal bounds on the angle between tangent spaces, we formally introduce the local reach for sets of positive reach, based on Aamari et al.’s discussion for C2 manifolds. We prove that the local reach of a manifold is completely characterized by the variation of tangent spaces. This improves earlier results, that were either suboptimal or assumed that the manifold was C2.

Thirdly, we show that the value of the reach is equals minimum of the local reach of the set and a global bottleneck for any set. This generalizes a result by Aamari et al. which explains how the reach is attained for C2 manifolds.

Keywords and phrases:
Reach, Manifolds, Differentiability class, Lipschitz continuity, Tangent space
Funding:
Mathijs Wintraecken: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science fund (FWF) grant No. M-3073, the ANR grant StratMesh (ANR-24-CE48-1899), and the welcome package from IDEX of the Université Côte d’Azur (ANR-15-IDEX-01).
Copyright and License:
[Uncaptioned image] © André Lieutier and Mathijs Wintraecken; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Computational geometry
Related Version:
Full Version: https://hal.inria.fr/hal-04816588
Acknowledgements:
We thank Jean-Daniel Boissonnat for discussion. We would also like to acknowledge the organizers of the workshop on “Algorithms for the Medial Axis”, and Erin Chambers in particular for giving an impulse to this research. We further thank the reviewers for their comments that improved the exposition.
Editors:
Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

1 Introduction

In [13] Federer introduced the reach of a closed set 𝒮d as the minimum of the distance from 𝒮 to the medial axis ax(𝒮), i.e. the set of points in d for which the closest point in 𝒮 is not unique. Assumptions on the reach (and its local version the local feature size [4]) underpin the correctness of many algorithms in computational geometry and topology. In this paper we consider the differentiability class of manifolds of positive reach and give tight bounds on the angle between nearby tangent spaces for general manifolds of positive reach. For arbitrary sets of positive reach we give a geometrical explanation on how the reach in attained.

Previous work
Differentiability.

Federer proved that the reach is stable under C1,1-diffeomorphisms of the ambient space. Here we write C1,1 to indicate C1 maps whose derivative is Lipschitz, and by a C1,1-diffeomorphism we mean that both the diffeomorphism and its inverse are C1,1. Federer [13, Remark 4.20] furthermore mentioned (without going into much detail on one direction of the implication) that the graph of a function has positive reach if and only if it is C1,1. Lytchak [21, 22] proved that a topologically embedded manifold without boundary has positive reach if and only if it is C1,1, without a quantitative bound on the Lipschitz constant. This statement is quantified in our Theorem 1 below. We emphasize that quantifying these constants is essential for the result to allow us to formulate sampling criteria that guarantee the correctness of algorithms.

Lytchak’s proof requires significant background in CAT(k)-theory. Lytchak, motivated by bounds on intrinsic curvature, does not give any quantified bound on the extrinsic curvature, which play an important role in this paper.

Scholtes [27] also gave a proof that a hypersurface has positive reach if and only if it is C1,1, using different techniques from both the ones employed by Lytchak and in this paper. Scholtes’ method uses the fact that the manifold has codimension one in an essential way.

Rataj and Zajíček [26] prove that if a Lipschitz manifold has positive reach, then it is C1,1. They also use Lemma 17, however the assumption that the manifold is already Lipschitz simplifies the matter considerably, in particular they can skip the topological analysis. Moreover, again, they do not quantify their results in the way that we do and is essential for guarantees for algorithms. Recently, Leobacher and Steinicke [18] also reproved Lytchak’s result, but once more the result was not quantified. We further stress that the bounds that we provide on the Lipschitz constants are tight, as we’ll discuss in more detail below.

Geometric bounds and tangent variation.

Bounding the tangent angle variation on smooth manifolds is crucial for establishing constants in the context manifolds reconstruction and meshing [4, 10, 12, 7]. If we now focus on more recent results, some authors consider angle variation bounds for a given local feature size bound [17]. Other authors, including the ones of the present paper, give angle variation bounds based on the reach [8]. Assuming the surface to be smooth, more specifically C2 smooth, allows using standard differential geometry tools such as second fundamental forms, curvatures and Riemannian geometry, while, as hinted at by Federer’s and Lytchak’s results, the weaker positive reach assumption is sufficient for many properties to hold.

For example, in [8], the angle variation bound given for C2 manifolds are clearly optimal (the bound is attained on spheres) while only suboptimal bounds are derived for C1,1, or positive reach, manifolds.

Attaining the reach.

In [1, Theorem 3.4], Aamari et al. make the following observation for C2 manifolds: The reach of a submanifold of Euclidean space can be expressed as the minimum of a global quantity, realized at so called “bottlenecks”, and a local quantity, the inverse of the maximal extrinsic curvature. These “bottlenecks” can be formally related to a global reach and the local quantity with a local reach, which we’ll do in this paper. We stress that the concepts of the local and global reach are mentioned once in the introduction of [1], no formal definition was given in that paper. Moreover, while this assumption is somewhat implicit in the proof of [1, Theorem 3.4], the analysis uses the context of Riemannian geometry, assuming the C2 regularity of the manifold. We further emphasize that [1] focused uniquely on manifolds, which contrasts with the definition for global reach and local reach for any set of positive reach in this paper.

These results explain how the reach is attained, see Figure 1. This gives insight in which parts of a set of positive reach present the “difficult” parts for algorithms, in the examples we’ll discuss now.

Motivation and related work

The assumption of positive reach is central to almost all triangulation algorithms, see for example [10, 12, 7], manifold learning, see for example [15, 14, 2, 28], and homotopy inference, see for example [24, 29]. Closing the gap between C2 and positive reach manifolds significantly extends the applications domains. This extension is necessary to include for example the boundary of objects that have been designed by computer aided design software. These boundaries are generically tangent continuous and have bounded curvature (e.g. two planar faces connected through a cylindrical fillet surface), but don’t have continuous curvature.

The main result of this paper makes precise what it means for a topologically embedded submanifold of Euclidean space to have positive reach: The embedding is necessarily C1,1-smooth (Theorem 1) and we give a tight bound on the (generalized) extrinsic curvature of the submanifold (Theorem 4).

Generalized tangent and normal spaces.

Federer showed that although sets of positive reach are more general than smooth manifolds, they still posses generalized tangent and normal spaces, which are convex cones instead of just linear spaces. Roughly speaking, the normal cone at a point p of a set with positive reach determines the topological “link” of point p in the set, that is the local topology.

To prove the Theorem 1 it is essential to show that the normal cone at any point of a positive reach, topologically embedded n-manifold is a (dn)-dimensional vector space. In the proofs of [21, 22] the relation between the normal cone at a point p of a topologically embedded manifold with positive reach and the “link” of p is established using CAT(k)-theory. In contrast, our (short) proof (see the overview in Section 3 and Lemma 31 of [20]) is based on elementary properties of (the homology of) convex cones makes this correspondence more transparent in our opinion.

We further extend the results of [21, 22] by giving an optimal bound on the angle variation of tangent spaces. This also extends the same bound obtained in the particular context of C2 manifolds [8]. We even obtain a significantly stronger result, that is, we characterize the local reach of a manifold completely by the tangent variation.

Contribution.

In this paper we give an elementary proof of the following characterizations of manifolds of positive reach. Moreover the statement is quantified with optimal constants. Here we write B(p,r) or B(p,r) for the closed or open ball centred at p with radius r.

Theorem 1.

If is a topologically embedded manifold with positive reach and p a point in , then B(p,2rch())πTp1(B(0,rch())) is the graph of a C1,1 function above the open domain B(0,rch())Tp.

We also generalize the notations of local and global reach from C2 submanifolds [1] to arbitrary compact sets (of positive reach):

Definition 2 (Local and global reach).

For a closed set 𝒮d, we define the local rchloc.(𝒮) and global rchglob.(𝒮) reach as:

rchglob.(𝒮)=def.inf{|ab|2|a,b𝒮,B(a+b2,|ab|2)𝒮=} (1)
rchloc.(p,𝒮)=def.limρ0ρ>0rch(𝒮B(p,ρ))[0,+] (2)
rchloc.(𝒮)=def.infp𝒮rchloc.(p,𝒮)[0,+], (3)

where inf()=+.

 Remark 3.

If rch(𝒮)>0, then ρrch(𝒮B(p,ρ)) is non-increasing (this follows from Theorem 16 because 𝒮B(p,ρ) is geodesically convex [8, Corollary 1] for all ρ<rch(𝒮) so that the set of bounds that need to be satisfied in (9) is larger, c.f. [6, Lemma 5]) as soon as ρ<rch(𝒮), so that the limit in (2) exists. Moreover, since for any p one has rchloc.(p,𝒮)rch(𝒮), we get that:

rchloc.(𝒮)rch(𝒮). (4)

To be able to give the bounds on the tangent variation/extrinsic curvature we need to introduce some notation.

We write Gr(n,d) for the Grassmannian, that is the space of n-linear subspaces of d with metric given by the sine of the maximum angle. We recall that the maximum angle is given by

A,B=def.maxaA{0}minbB{0}a,b=maxbB{0}minaA{0}a,b. (5)

We use this maximal angle as our metric. It is not that difficult to establish that this is indeed a metric, see [30] or [25] for a far reaching generalization.111The sine of this angle also defines a metric on the Grassmannian as can be found in e.g. [16, Chapter IV, Section 2.1] or [3, Section 34], see Appendix B of [20] for a more extensive description. It seems that in a number of fields the sine of the angles is a more common metric, but it is suboptimal in this context. We further stress that neither of these metrics equal the standard Riemannian metric on the Grassmannian, which is given by the sum of the squares of the principal angles, see e.g. [31].

Figure 1: In this figure we see the two ways in which the reach can be attained for a general set of positive reach, by means of the global reach (top) or local reach (bottom), for two sets of positive reach in the plane. The shading indicates a solid set. The points (red) and the circle (blue) in which the reach is attained are indicated.
Theorem 4.

If d is a topologically embedded n-manifold with reach at least R>0, then tangent spaces and normal spaces to are linear spaces at any point p and the maps Tan:Gr(n,d) and Nor:Gr(dn,d) are Lipschitz.

Moreover, the smallest Lipschitz constant satisfied by pTan(p,𝒮) is 1rchloc.():

supp,qpqTan(p,),Tan(q,)d(p,q)=1rchloc.(), (6)

where d denotes the geodesic distance on and we say that d(p,q)= when p and q are not connected by any path in and that 1/=0.

 Remark 5.

If d is a manifold with boundary then the results of Theorem 4 still hold as long as there is a shortest path geodesic between p and q that lies completely in the interior of .

Next theorem is a generalization of [1, Theorem 3.4] which was formulated in the particular situation where 𝒮 is a C2 embedded manifold, in which case rchloc.(𝒮) is also the supremum of extrinsic curvature.

Theorem 6.

If 𝒮 is a compact subset of d, then:

rch(𝒮)=min(rchglob.(𝒮),rchloc.(𝒮))

We refer to Figure 1 for an illustration.

2 Preliminaries

In this section we first recall some results and definitions concerning sets of positive reach. The results concerning the reach are mainly taken from [13] and [8].

2.1 Sets of positive reach

Throughout this paper we will write 𝒮 for a general closed set (mostly with positive reach) and for a manifold (mostly without boundary) and in some (rare) cases for its boundary (if it exists).

The concept of a tangent space of a smoothly embedded manifold has been generalized by Federer to tangent cones in the following manner:

Definition 7 (Generalized tangent spaces, Definitions 4.3 and 4.4 of [13]).

If 𝒮d and p𝒮, then the generalized tangent space

Tan(p,𝒮)

is the set of all tangent vectors of 𝒮 at p consists of all those ud, such that either u=0 or for every ϵ>0 there exists a point q𝒮 with

0< |qp|<ϵ and |qp|qp|u|u||<ϵ.

The set

Nor(p,𝒮)

of all normal vectors of 𝒮 at p consists of all those vd such that vu0 for all uTan(p,𝒮).

Definition 8.

We write π𝒮 for the closest point projection on 𝒮.

Although it is possible to define a set valued version of π𝒮, we only use the projection map outside the medial axis, that is at those points where there is a single closest point.

For the remainder of this subsection we will recall the properties of this map and sets of positive reach that are essential for this paper.

Lemma 9 (Angle with tangent space, Theorem 4.8(7) of [13]).

Suppose that 𝒮 is a set positive reach rch(𝒮). Let p,q𝒮d such that |pq|<rch(𝒮). We have

sin(qp,Tan(p,𝒮))|pq|2rch(𝒮). (7)

Moreover, a variant of the previous lemma characterizes the reach for arbitrary closed sets, that is:

Lemma 10 (Distance to tangent space characterizes the reach, Theorem 4.18 of [13]).

For a closed subset 𝒮 of Euclidean space 𝔼=d, one has:

rch(𝒮)=infp,q𝒮pq|pq|22d𝔼(q,p+Tan(p,)) (8)
Lemma 11 (Theorem 4.8 (4) of [13]).

π𝒮 is continuous on dax(𝒮).

In fact the following lemma strengthens the previous.

Lemma 12 (Theorem 4.8 (8) of [13]).

If x,yd, and

max{|xπ𝒮(x)|,|yπ𝒮(y)|}=μrch(𝒮),

then

|π𝒮(x)π𝒮(y)|rch(𝒮)rch(𝒮)μ|xy|
Lemma 13 (Theorem 4.8 (12) of [13]).

If p𝒮 and lfs(p)>ρ>0, then

Nor(p,𝒮)={λvλ0,|v|=ρ,π𝒮(p+v)=p}.

Tan(p,𝒮) is the convex cone dual to Nor(p,𝒮), and

limt0+t1d(p+tu,)=0,

for uTan(p,𝒮), where d is the Euclidean distance.

Lemma 14 (Remark 4.15 (1) of [13]).

If p𝒮 and lfs(p)>ρ>0, then 𝒮B(p,ρ) is contractible.

2.1.1 Geodesics

We also recall a result from the second paragraph of Part III, Section 1: “Die Existenz geodätischer Bogen in metrischen Räumen” in [23]:

Lemma 15 (Menger’s existence of geodesics).

For a closed set 𝒮d, d𝒮 denotes the geodesic distance in 𝒮, i.e. d𝒮(a,b) is the infimum of lengths of paths in 𝒮 between a and b. If there is at least one path between a and b with finite length, then it is known that a minimizing geodesic, i.e. a path with minimal length connecting a to b exists. When no such path between a and b with finite length exists, we write d𝒮(a,b)=.

We’ll be using the metric characterization of the reach from [8] quite often in this paper.

Theorem 16 (Theorem 1 of [8]).

If 𝒮d is a closed set, then

rch𝒮=sup{r>0,a,b𝒮,|ab|<2rd𝒮(a,b)2rarcsin|ab|2r}, (9)

where the sup over the empty set is 0.

2.2 Embeddings and atlases

We consider below an embedded, compact n-manifold d with an atlas associated with an open cover (Ui)iI:

=iIUi

and charts fi:Uin that are homeomorphisms on their images, where the topology on is the one induced by the ambient metric of d.

Note that, topologically222We say that an embedding is topological to stress that we don’t make any assumption beyond the assumption that it is a homeomorphism onto its image, in particular no assumptions on differentiability are made. embedded manifold does not exclude wild embeddings [11] but, as seen below, the positive reach assumption does, because the embedding is proven to be C1,1.

3 Overview of the first two main results: Manifolds of positive reach, differentiability, and tangent variation

In this section we provide an overview of the proof of the first two main results of this paper Theorems 1 and 4. We discuss this in complete detail with full proofs of the statements in the appendix of the full version of this paper, that is [20].

A topologically embedded manifold with positive reach is differentiably embedded.

Consider a topologically embedded manifold with positive reach. That is, we don’t assume anything on the embedding of the manifold except that it is a homeomorphism with its image. However, the assumption that the manifold has positive reach yields that the generalized tangent spaces (see Definition 7) are cones.

Refer to caption
Refer to caption
Figure 2: Convex cones come in two variants, a tapering object or a half space on the one hand and vector spaces on the other.

We characterize convex cones by topological means (roughly speaking) as follows. We recall that a convex cone is a subset of d that is convex and for each v in the set we have that λv is also in the set for λ0. By this we mean that, roughly speaking, convex cones A come into two classes:

  1. 1.

    The convex cone is defined by

    A={λa|λ0,aA~},

    where A~ is a contractible subset of 𝕊d1. Note that A~=A𝕊d1. In this case A is (again roughly speaking) either a tapering object or a half space.

  2. 2.

    The convex cone is defined by

    A={λa|λ0,aA~},

    where A~ is a (k dimensional, with 0kd1) geodesic sphere in 𝕊d1. In this case A is a vector space.

These two classes are characterized by the homology of B(0,1)A. The contractibility of A~ is the key ingredient, see Lemma 30 of [20]. More precisely, we’ll use that A~ is contractible on the sphere if and only if A isn’t a vector space.

In Section A.2 of the appendix of [20] we’ll establish, based on the characterization of Appendix A.1 of [20], that for topologically embedded manifolds the tangent cones are in fact tangent spaces. The proof proceeds in two steps:

  • In Lemma 31 of [20], we’ll see that B(p,ρ)(p+Nor(p,𝒮)) has the same homology as 𝒮B(p,ρ){p}, see Figure 3. This result will rely on the deformation retract along the closest point projection of sets of positive reach and its continuity as established by Federer [13]. We stress that the normal cone Nor(p,𝒮) is the dual of the tangent cone Tan(p,𝒮), which explains the link with Lemma 30 of [20].

  • In the proof of Lemma 32 of [20], we’ll see that if is manifold, then B(p,ρ){p} has the homology of a sphere of dimension n1, which with the previous lemma allows us to conclude that Tan(p,) is a vector space. The proof combines topological reasoning with arguments based on the charts of the manifold .

Figure 3: Sketch of the proof of Lemma 31 of [20]. We establish a homotopy between B(p,ρ)(p+Nor(p,𝒮)) and 𝒮B(p,ρ){p} by deformation retract induced by the map π𝒮B(p,ρ).

By definition we have that if a manifold has a tangent space it is differentiably embedded, but that does not mean that the manifold has to be continuously differentiably embedded, this is what will be the topic we’ll address next.

Semi-continuity of normal cones and 𝑪𝟏 embeddings.

In Section A.3 of [20] we will first prove a more general statement (Lemma 33 of [20]), namely semi-continuity of the normal cones for general sets of positive reach. By this we mean that given a point p and its normal cone Nor(p,𝒮), for all ϵ there exists a neighbourhood of p such that for all p in this neighbourhood, we have that the normal cone Nor(p,𝒮) makes only an ϵ angle with some subset of Nor(p,𝒮). The proof is elementary, but rather technical, and relies on compactness arguments and the manipulation of offsets.

Lemma 33 of [20] together with the observation that the tangent spaces are k-dimensional vector spaces the one sided bound on the angle between the normal cones above is in fact a two-sided bound, see Lemma 34 of [20], yields that the manifold is C1, that is continuously differentiable. Lemma 35 of [20] strengthens this even further and explains that can locally be written as the graph of a function. To put it differently, using some geometrical and analytical arguments we see that the manifold (locally) projects injectively on its tangent cone (which is an affine space by Lemma 32 of [20]). This then allows us to identify it, locally, as the graph of a differentiable map from the tangent space to the normal space.

From 𝐂𝟏 to 𝐂𝟏,𝟏 embeddings.

Appendix A.4 of [20] proves the majority of the main statements of the paper, namely that manifolds with positive reach are C1,1 and characterizes the Lipschitz constants of the derivative in terms of the local reach. It is the most technical section and relies heavily on the theory of semiconcave functions. Most crucially we’ll use the following result, namely Corollary 3.3.8 of [9]:

Lemma 17.

Let F:U be a function defined on a convex open set Un. Then the following properties are equivalent:

  • F is of class C1,1 with 1-Lipschitz derivative.

  • both x1/2x2F(x) and x1/2x2+F(x) are convex functions.

Figure 4: A manifold with empty tangent balls (blue) and (locally) empty tangent parabola (red).

Although that the precise technical way that this result is used is too intricate to explain in a paragraph or two, the link between sets of positive reach and Lemma 17 can be explained in geometrical terms. Assume for the moment that has reach 1. As a consequence of Lemma 13 the interior of every ball that is tangent to a manifold , that has radius less or equal to 1 (the reach of ) does not intersect itself. Geometrically speaking the fact that x1/2x2F(x) and x1/2x2+F(x) are convex functions can be expressed by the fact that (locally) the interior of parabolae that are tangent to the manifold have an empty interior, see Figure 4. Of course these parabolae are just second order approximations of the spheres. Because we are just interested in the Lipschitz constants of the derivative this approximation suffices.

Using Lemma 17 we do not directly prove our bound on the angle between nearby tangent spaces, instead we first establish the bound

Dϕ(y2)Dϕ(y1)1(rchloc.(p,)ϵ)|y2y1|,

see Lemma 39 of [20], where ϕ is the local function (from the tangent to normal space) of which is locally the graph and denotes the operator two norm, in other words we regard the Jacobians as matrices depending on y and bound their Lipschitz constant in a way that is ϵ close to optimal.

From the result of Lemma 39 of [20] it is not very difficult to derive a local bound between tangent spaces, which is done in Lemma 40 of [20]. This local bound can then be extended (Lemma 41 of [20]) to a non-local statement by gluing the local estimates on the angle between tangent spaces along a geodesic, which exists thanks to Lemma 15. This allows us to establish one of the main results, the characterization of the local reach in terms of the tangent variation in Theorem 4, whose proof requires a significant amount of computation. The optimal size of the domain (in a fixed tangent space) such that can be written as the graph of a function from a (fixed) tangent space to its normal space is then given in Theorem 1. The proof can be sketched as follows: By combining Theorems 4 and 16 with the submersion theorem we can establish a local diffeomorphism. The global diffeomorphism is established by proving that the covering number is one.

4 Global and local reach

In this section we stablish the third main result of the paper, that is Theorem 6. This theorem generalizes the results of [1] on how the reach is attained from C2 manifolds to arbitrary sets of positive reach. It states that the reach is a consequence of either curvature maxima or so-called bottlenecks. In our result we replace the curvature by the local reach, which in turn is defined using local metric distortion, while the bottlenecks are similar in nature. In a number of cases we will have to assume that the set is bounded/compact.

Athough some of the details of the proof of Theorem 6 are a bit technical, the main idea is not that complicated. In fact we provide a sketch of the proof in Figure 5 and its caption.

Figure 5: To derive a contradiction assume that rch(𝒮)<rchloc.(𝒮) and 𝒮 is tangent to the ball with radius rch(𝒮) (blue) in two distinct points (red) that are closer than 2rch(𝒮), and therefore not antipodal. Consider the cord connecting these two points (dashed red), then Theorem 16 yields that the length of the geodesic is at most equal to part of the circle indicated in red, however that is the only curve of that length (or less) that connects the two red points that does not intersect the interior of the ball of radius rch(𝒮). This implies that this curve has to lies inside 𝒮, moreover this curve has local reach rch(𝒮). Combining these observations yields that rch(𝒮)rchloc.(𝒮).

We recall the definition from the introduction: See 2

Lemma 18.

The map prchloc.(p,𝒮) defined over 𝒮 is lower semi-continuous, in other words:

rchloc.(p,𝒮)=limρ0ρ>0infq𝒮B(p,ρ)rchloc.(q,𝒮).
Proof.

By definition of rchloc.(p,𝒮), we have that for any ϵ>0 there is ρ>0 such that:

rch(p,𝒮B(p,ρ))>rchloc.(p,𝒮)ϵ. (10)

One gets

rchloc.(p,𝒮) infq𝒮B(p,ρ)rchloc.(q,𝒮)
=infq𝒮B(p,ρ)rchloc.(q,𝒮B(p,ρ))
rchloc.(𝒮B(p,ρ)) (by (3) applied to the set 𝒮B(p,ρ))
rch(𝒮B(p,ρ)) (by (4))
>rchloc.(p,𝒮)ϵ. (by (10))

Because this inequality holds for any positive ϵ, the equality follows.

 Remark 19.

As a consequence, when 𝒮 is compact, the inf in (3) is a min, in other words there exists at least one point p𝒮 such that rchloc.(p,𝒮)=rchloc.(𝒮).

Definition 20.

A bottleneck is a pair of points (a,b)𝒮2 such that

B(a+b2,|ab|2)𝒮=.

We have the following variant of Lemma 12 of [8], which in turn is a relatively straightforward generalization to arbitrary dimension of Property I of [5]:

Lemma 21.

If a geodesic (or more generally a curve) γ parametrized according to arc length on the interval [0,] satisfies

γ˙(s1),γ˙(s2)1R|s2s1|, (11)

then as long as 2πR,

|qp|2rch()sin(2R),

where p=γ(0) and q=γ().

Proof.

The length of γ in the direction γ˙(2) is

qp,γ˙(2) =0γ˙(s),γ˙(/2)ds
=0/2γ˙(s),γ˙(/2)ds+/2γ˙(s),γ˙(/2)ds
0/2cos|s/2|Rds+/2cos|s/2|Rds
=2Rsin(2R).

where, in the above inequality, we use the assumption 2πR and the fact that θcosθ is decreasing on [0,π].

Because |qp|qp,γ˙(2), we see that

|qp|2Rsin(2R).

Combining Lemmas 42 of [20] and 21 we get:

Corollary 22.

If γ is a geodesic in 𝒮 with length 2πrchloc.(𝒮), then

2rchloc.(𝒮)arcsin|pq|2rchloc.(𝒮).

The Lemma 23 below is a special case of [19, Lemma 4.6], we still provide a proof for completeness.

Lemma 23.

Let xax(𝒮) and denote by x~ the unique point closest to x in 𝒮.
Then, for any ϵ>0, there is α>0 such that,

|yx|<α{z𝒮d(y,z)=d(y,𝒮)}B(x~,ϵ). (12)
Proof.

Consider the closed set 𝒮:=𝒮B(x~,ϵ). The minimum distance d(x,𝒮) to x is attained at least at some point z in 𝒮 so that

d(x,𝒮)=d(x,z)>d(x,x~)=d(x,𝒮).

Taking

α:=d(x,𝒮)d(x,𝒮)2,

we get, for any y such that |yx|<α and z𝒮 that:

d(y,z) d(y,𝒮)d(x,𝒮)d(y,x)
=d(x,𝒮)+2αd(y,x)=d(x,x~)+2αd(y,x)
>d(x,x~)+d(y,x)d(y,x~)d(y,𝒮).

We have shown that if z𝒮, then d(y,z)>d(y,𝒮). It follows that any closest point to y in 𝒮 is in 𝒮𝒮=𝒮B(x~,ϵ) which is (12).

Theorem 6. [Restated, see original statement.]

If 𝒮 is a compact subset of d, then:

rch(𝒮)=min(rchglob.(𝒮),rchloc.(𝒮))
Proof.

We consider first the situation where rch(𝒮)=0. In this case, since 𝒮 is bounded, there exists some point pax(𝒮)¯𝒮. Then, for any ρ>0, there is some pax(𝒮) such that d(p,p)<ρ/2, so that there are at least two points in 𝒮B(p,ρ) closest to p. Thus, rch(𝒮B(p,ρ))<ρ/2, and, since this holds for any ρ>0, we get that rchloc.(p,𝒮)=0 and as a direct consequence rchloc.(𝒮)=infq𝒮rchloc.(q,𝒮)=0.

We assume now that rch(𝒮)>0.

As we have seen in Equation (4) of Remark 3, we have that rch(𝒮)rchloc.(𝒮). Therefore it suffices to prove that, if rch(𝒮)<rchloc.(𝒮), then rch(𝒮)=rchglob.(𝒮). So let us assume now that rch(𝒮)<rchloc.(𝒮).

Since 𝒮 is compact and thus bounded, which implies that a closed rch(𝒮)-neighbourhood of 𝒮 is also bounded, there must exist xax(𝒮)¯, where ax(𝒮)¯ is the closure of the medial axis ax(𝒮), such that d(x,𝒮)=rch(𝒮).

If xax(𝒮)¯ax(𝒮), in particular xax(𝒮) and there is a unique point x~ closest to x in 𝒮. Choose some 0<ϵ<rch(𝒮) and, as in Lemma 23, take α>0 so that (12) holds and, moreover, such that

α<rchloc.(𝒮)rch(𝒮).

Since xax(𝒮)¯, there exists yax(𝒮)B(x,α)), and therefore Lemma 23 yields that there exists at least two points p,qB(x~,ϵ) such that d(y,p)=d(y,q)=d(y,𝒮).

Because d(p,q)<2ϵ<2rch(𝒮), by Theorem 16, there is a geodesic from p to q of length at most πrch(𝒮), which is less that 2πrchloc.(𝒮). But then one can apply Corollary 22, which implies that the length of a geodesic from p to q is at most

max=2rchloc.(𝒮)arcsin|pq|2rchloc.(𝒮).

However, since projecting a curve outside a given sphere onto the given sphere only decreases its length, a curve from p to q outside the ball centered at y whose radius is at most rch(𝒮)+|yx|<rch(𝒮)+α<rchloc.(𝒮) must have length strictly greater than max, a contradiction.

We have so far proven that when rch(𝒮)<rchloc.(𝒮), then the reach cannot be realized in ax(𝒮)¯ax(𝒮). One must then have xax(𝒮) and there are at least two points pq closest points to x on 𝒮.

If |pq|<2rch(𝒮) then by Theorem 16 one has that d𝒮(p,q)2rch(𝒮)arcsin|pq|2rch(𝒮) which is less than 2πrchloc.(𝒮). Again, Corollary 22 implies that the length of a geodesic from p to q is a most 2rchloc.(𝒮)arcsin|pq|2rchloc.(𝒮), which, again, is impossible without entering the ball centered at x with radius rch(𝒮)<rchloc.(𝒮).

Since |pq|2rch(𝒮), the only possibility is that |pq|=2rch(𝒮), i.e. x=(p+q)/2, a bottleneck.

References

  • [1] Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman. Estimating the reach of a manifold. Electronic journal of statistics, 13(1):1359–1399, 2019.
  • [2] Eddie Aamari and Clément Levrard. Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction. Discrete & Computational Geometry, 59(4):923–971, 2018. doi:10.1007/s00454-017-9962-z.
  • [3] Naum Il’ich Akhiezer and Izrail Markovich Glazman. Theory of linear operators in Hilbert space. Courier Corporation, 2013.
  • [4] N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete & Computational Geometry, 22(4):481–504, December 1999. doi:10.1007/PL00009475.
  • [5] Dominique Attali, Herbert Edelsbrunner, and Yuriy Mileyko. Weak Witnesses for Delaunay triangulations of Submanifold. In ACM Symposium on Solid and Physical Modeling, pages 143–150, Beijing, China, June 2007. doi:10.1145/1236246.1236267.
  • [6] Dominique Attali and André Lieutier. Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape. Discrete & Computational Geometry, 54(4):798–825, 2015. doi:10.1007/S00454-015-9733-7.
  • [7] Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. Geometric and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2018. doi:10.1017/9781108297806.
  • [8] Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology, 3(1):29–58, June 2019. doi:10.1007/s41468-019-00029-8.
  • [9] Piermarco Cannarsa and Carlo Sinestrari. Semiconcave functions, Hamilton-Jacobi equations, and optimal control, volume 58. Springer Science & Business Media, 2004.
  • [10] S.-W. Cheng, T.K. Dey, and J.R. Shewchuk. Delaunay Mesh Generation. Computer and information science series. CRC Press, 2013.
  • [11] Robert J Daverman and Gerard Venema. Embeddings in manifolds, volume 106. American Mathematical Soc., 2009.
  • [12] T.K. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Number 23 in Cambridge monographs on applied and computational mathematics. Cambridge University Press, 2007.
  • [13] H. Federer. Curvature measures. Transactions of the American mathematical Society, 93:418–491, 1959.
  • [14] Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, and Hariharan Narayanan. Reconstruction and interpolation of manifolds. I: The geometric Whitney problem. Foundations of Computational Mathematics, 2019. doi:10.1007/s10208-019-09439-7.
  • [15] Charles Fefferman, Sergei Ivanov, Matti Lassas, and Hariharan Narayanan. Fitting a manifold of large reach to noisy data. arXiv e-prints, page arXiv:1910.05084, October 2019. arXiv:1910.05084.
  • [16] Tosio Kato. Perturbation theory for linear operators, volume 132. Springer Science & Business Media, 2013.
  • [17] Marc Khoury and Jonathan Richard Shewchuk. Approximation bounds for interpolation and normals on triangulated surfaces and manifolds. arXiv preprint arXiv:1911.03424, 2019. arXiv:1911.03424.
  • [18] Gunther Leobacher and Alexander Steinicke. Existence, uniqueness and regularity of the projection onto differentiable manifolds. Annals of Global Analysis and Geometry, 60(3):559–587, July 2021. doi:10.1007/s10455-021-09788-z.
  • [19] André Lieutier. Any open bounded subset of n has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029–1046, 2004. Solid Modeling Theory and Applications. doi:10.1016/j.cad.2004.01.011.
  • [20] André Lieutier and Mathijs Wintraecken. Manifolds of positive reach, differentiability, tangent variation, and attaining the reach. Full version, 2026. URL: https://inria.hal.science/hal-04816588.
  • [21] Alexander Lytchak. On the geometry of subsets of positive reach. manuscripta mathematica, 115(2):199–205, 2004.
  • [22] Alexander Lytchak. Almost convex subsets. Geometriae Dedicata, 115(1):201–218, 2005.
  • [23] K. Menger. Untersuchungen über allgemeine Metrik. Vierte Untersuchung. Zur Metrik der Kurven. Mathematische Annalen, 103:466–501, 1930.
  • [24] P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39(1-3):419–441, 2008. doi:10.1007/S00454-008-9053-2.
  • [25] Li Qiu, Yanxia Zhang, and Chi-Kwong Li. Unitarily invariant metrics on the grassmann space. SIAM Journal on Matrix Analysis and Applications, 27(2):507–531, 2005. doi:10.1137/040607605.
  • [26] Jan Rataj and Luděk Zajíček. On the structure of sets with positive reach. Mathematische Nachrichten, 290(11-12):1806–1829, 2017.
  • [27] S. Scholtes. On hypersurfaces of positive reach, alternating Steiner formulae and Hadwiger’s Problem. ArXiv e-prints, April 2013. arXiv:1304.4179.
  • [28] Barak Sober and David Levin. Manifold approximation by moving least-squares projection (MMLS). Constructive Approximation, pages 1–46, 2019. doi:10.1007/s00365-019-09489-8.
  • [29] Yuan Wang and Bei Wang. Topological inference of manifolds with boundary. Computational Geometry, 88:101606, 2020. doi:10.1016/j.comgeo.2019.101606.
  • [30] Per Åke Wedin. On angles between subspaces of a finite dimensional inner product space. In Matrix Pencils: Proceedings of a Conference Held at Pite Havsbad, Sweden, March 22–24, 1982, pages 263–285. Springer, 2006.
  • [31] Yung-Chow Wong. Differential geometry of Grassmann manifolds. Proceedings of the National Academy of Sciences of the United States of America, 57(3):589, 1967.