domain: info math

text:
André Lieutier
email: andre.lieutier@gmail.com

Mathijs Wintraecken
email: mathijs.wintraecken@inria.fr

Hausdorff and Gromov-Hausdorff stable subsets of the medial axis

Keywords: • Theory of computation → Computational geometry Medial axis, Gromov-Hausdorff distance, metric stability, computable analysis

published or not. The documents may come

Hausdorff and Gromov-Hausdorff stable subsets of the medial axis

on its boundary 𝜕𝐾. Note that the definitions of the medial axis used in preceding papers on the same topic [START_REF] Chazal | The 𝜆-medial axis[END_REF][START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF] considered an open subset O ⊂ R 𝑛 instead. Because the medial axis was then defined as the set of points in O with at least two closest points on the complement O 𝑐 we see that the difference is only cosmetic by setting 𝐾 = O 𝑐 . The properties of the medial axis and its computation have been intensively studied, both in theory and in particular applications contexts, see [START_REF] Attali | Stability and Computation of Medial Axes -a State-of-the-Art Report[END_REF] for an overview, or [START_REF] Tagliasacchi | 3D Skeletons: A state-of-the-art report[END_REF] 1 for an application oriented review of general notions of shapes skeletons and computation methods.

One obvious motivation for studying the stability of the medial axis is to be able to guarantee the (approximate) correctness of the information that can be extracted from the medial ax(𝐾 ′ ) axis of an approximated shape 𝐾 ′ of an exact, or ideal, shape 𝐾. Here the approximation error could be the unavoidable finite accuracy of physical measurements or some small perturbations induced by rounding or geometric data conversions.

Another, more formal, motivation for studying the stability is related to its formal computation. Indeed, among the significant amount of practical proposed algorithms for the map 𝐾 ↦ → ax(𝐾), the model of computation is usually implicit, which we find problematic in the case of this particularly unstable object. We refer to Section 4.1 for a more extensive discussion of this issue.

The idea of pruning, or filtering, the medial axis, in order to improve its stability, has been, sometime implicitly, a key ingredient in realistic algorithms. For example, in [START_REF] Foskey | Efficient computation of a simplified medial axis[END_REF], the 𝜃 -simplified medial axis of 𝐾 is defined as the set of points 𝑥 on the medial axis of 𝐾 for which 𝑥 has at least 2 closest points 𝑝, 𝑞 ∈ 𝐾 such that the angle ∠𝑝𝑥𝑞 is greater than 𝜃 . Since the medial axis of a finite discrete set 𝑆 ⊂ R 𝑑 is the (𝑑 -1)-skeleton of the Voronoi diagram of 𝑆, following some pioneering works such as [START_REF] Amenta | The crust and the 𝛽-skeleton: Combinatorial curve reconstruction[END_REF][START_REF] Attali | Computing and simplifying 2D and 3D continuous skeletons[END_REF], in [START_REF] Tamal | Approximating the medial axis from the Voronoi diagram with a convergence guarantee[END_REF], the Voronoi cells of a point sample are pruned along some parametrized criterion, namely a angle condition or a ratio condition on the circumradius of the set of closest points and the distance between the point on the medial axis and its closest projection.

This paper pursues the quest for provably stable filtrations of the medial axis for general closed subset of Euclidean space, in the spirit of [START_REF] Chazal | The 𝜆-medial axis[END_REF]. Other prunings of the medial axis have been suggested in e.g. [START_REF] Attali | Modeling noise for a better simplification of skeletons[END_REF][START_REF] Blanc-Beyne | A salience measure for 3D shape decomposition and sub-parts classification[END_REF][START_REF] Tamal | Defining and Computing Curve-Skeletons with Medial Geodesic Function[END_REF][START_REF] Giesen | The Scale Axis Transform[END_REF][START_REF] Liu | Extended grassfire transform on medial axes of 2D shapes[END_REF][START_REF] Shaked | Pruning Medial Axes[END_REF][START_REF] Yan | Burning the Medial Axis[END_REF][START_REF] Yan | Erosion Thickness on Medial Axes of 3D Shapes[END_REF]. Each pruning method comes with some drawbacks (as well as strong points). We refer to [START_REF] Chambers | Video: A Cautionary Tale: Burning the Medial Axis Is Unstable[END_REF] for a discussion of the particular deficiencies of a number of these methods in more detail.

THE CRITICAL FUNCTION AND THE 𝜆-MEDIAL AXIS

In this section we review a number of results from [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF][START_REF] Chazal | The 𝜆-medial axis[END_REF] on the critical function of a compact set and some related notions. These results are both key ingredients in our proofs and a source of inspiration for some of the statements. The reach of a set 𝐾 is the minimal distance between a set and its medial axis. It was introduced by Federer [START_REF] Federer | Curvature measures[END_REF] in order to extend curvature measures to more general sets. The reach is also the lowest upper bound over the set of the local feature size [START_REF] Amenta | The power crust[END_REF][START_REF] Federer | Curvature measures[END_REF], that is the distance of a point to the medial axis. 2 The critical function 𝜒 𝐾 : (0, ∞) → [0, 1] ( [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] and [START_REF] Boissonnat | Geometric and topological inference[END_REF]Section 9]) of a compact set 𝐾 has been introduced in order to quantify how the topology of a set can be determined from a Hausdorff approximation of it, in particular when the reach is 0, which is common for non-smooth sets.

For a point 𝑥 ∈ R 𝑛 , we denote by 𝑅 𝐾 (𝑥) its distance to 𝐾 and by F 𝐾 (𝑥) the radius of the smallest ball enclosing the points in 𝐾 closest to 𝑥, see Section 8.2 for details. The critical function 𝜒 𝐾 of 𝐾 is then defined as:

𝜒 𝐾 (𝑡) = def. inf 𝑅 𝐾 (𝑥)=𝑡 √ 1 - F 𝐾 (𝑥)
𝑅 𝐾 (𝑥)

.

(

) 1
The medial axis ax(𝐾) can be defined as the set of points 𝑥 in R 𝑛 such that F 𝐾 (𝑥) > 0. It follows that, when 𝐾 has positive reach, 𝜒 𝐾 (𝑡) = 1 for 𝑡 smaller than the reach. We write 𝐾 ⊕𝑡 = def.

{𝑥 ∈ R 𝑛 , 𝑑 (𝑥, 𝐾) ≤ 𝑡 } for the 𝑡-offset of 𝐾. For 𝑡 > 0, the topology of this offset can only change at critical values of the distance function, that is values for which 𝜒 𝐾 vanishes. For a given 𝜇 ∈ (0, 1], the 𝜇-Reach (𝑟 𝜇 ) is defined as

𝑟 𝜇 (𝐾) = def.
inf {𝑡 | 𝜒 𝐾 (𝑡) < 𝜇}.

If 𝐾 has positive 𝜇-reach for some 𝜇 > 0, then 𝐾 ⊕𝑟 𝜇 deforms retract on 𝐾, see [START_REF] Kim | Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex[END_REF]Theorem 12]. Notices that 𝑟 1 (𝐾) is the reach of 𝐾.

In [START_REF] Chazal | The 𝜆-medial axis[END_REF] the 𝜆-medial axis of 𝐾, denoted here ax 𝜆 (𝐾), was introduced. Where the medial axis is the set of points in R 𝑛 such that F 𝐾 (𝑥) > 0, the 𝜆-medial axis of 𝐾 is a filtered version of it, defined as the set of points in R 𝑛 such that F 𝐾 (𝑥) ≥ 𝜆. Since F 𝐾 is upper semi-continuous [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]Corollary 4.7], ax 𝜆 (𝐾) is a closed set. For a given value of the filtering (pruning) parameter 𝜆, ax 𝜆 (𝐾) enjoys some geometrical and topological stability, see [START_REF] Chazal | The 𝜆-medial axis[END_REF] and the overview in Section 5 for details. The medial axis is the limit of 𝜆-medial axes in the sense that: 𝜆 ′ ≤ 𝜆 ⇒ ax 𝜆 ′ (𝐾) ⊃ ax 𝜆 (𝐾) and 𝜆>0 ax 𝜆 (𝐾) = ax(𝐾).

(2)

OVERVIEW OF RESULTS

In this paper, we show that a simple variant of the previous filtering 𝜆 ↦ → ax 𝜆 (𝐾), enables significantly stronger stability statements.

The (𝜆, 𝛼)-medial axis of a closed set 𝐾 ⊂ R 𝑛 , denoted here ax 𝛼 𝜆 (𝐾), is the 𝜆-medial axis of the 𝛼-offset3 of 𝐾:

ax 𝛼 𝜆 (𝐾) = def.
ax 𝜆 (𝐾 ⊕𝛼 ).

It is just another similar way of filtering the medial axis, where (2) is replaced by

𝜆>0 0<𝛼 <𝜆 ax 𝛼 𝜆 (𝐾) = ax(𝐾). (35)
The stability properties are then improved in two different ways: First, for 𝜆, 𝛼 > 0, if 𝜒 𝐾 does not vanish on some interval [𝑎, 𝑏] such that 𝑎 < 𝛼 and 𝛼 + 𝜆 < 𝑏, then the map (𝜆, 𝛼, 𝐾) ↦ → ax 𝛼 𝜆 (𝐾) is continuous for the (two-sided) Hausdorff distance on both the input 𝐾 and the output ax 𝛼 𝜆 (𝐾). Moreover, we give an explicit Hölder exponent in terms of 𝜆, 𝛼: For 𝐾 : (𝜆, 𝛼, 𝐾) ↦ → ax 𝛼 𝜆 (𝐾) the Hölder exponent is 1 with respect to 𝜆 and 𝛼, i.e. it is locally Lipschitz with respect to 𝜆 and 𝛼 (Lemma 9.4 and Lemma 9.5). The map is 1 2 -Hölder with respect to 𝐾 (Lemma 10.7).

Secondly, we extend the stability results to the Gromov-Hausdorff distance, see Section 8.4 for a formal definition. We show here that connected (𝜆, 𝛼)-medial axes are compact subsets of Euclidean space and have finite geodesic diameter (Theorem 9.12). Therefore (𝜆, 𝛼)-medial axes equipped with intrinsic geodesic distances on ax 𝛼 𝜆 (𝐾)) give meaningful metric spaces. We show that ax 𝛼 𝜆 (𝐾) seen as metric spaces is Gromov-Hausdorff stable under Hausdorff distance perturbation of 𝐾, which can be expressed as the continuity of the map (𝜆, 𝛼, 𝐾) ↦ → ax 𝛼 𝜆 (𝐾) under the associated metrics. Moreover we again establish bounds on the Hölder exponent in this new metric context: this map is locally Lipschitz with respect to 𝜆 and 𝛼 (Lemmas 9.14 and 9.15) and 1 4 -Hölder with respect to 𝐾 (Theorem 11.1).

This Gromov-Hausdorff stability gives metric stability which complements the homotopy type preservation and Hausdorff distance stability. It is the strongest form of stability we can hope for because the stronger property of bounded Fréchet distance 4 is impossible to achieve because of topological instability. In particular small smooth changes in a set can create changes in the topology of the medial axis.

Figure 1 illustrates three situations where the two shapes, the red and the blue, share the same homotopy type, as they all deform retract to a circle, and are close to each other with respect to the Hausdorff distance: any point in the red shape is near the blue shape and the reverse holds as well. On the first example, both distances, Fréchet (𝑑 𝐹 ) and Gromov-Hausdorff (𝑑 𝐺𝐻 ) are large, because the distances in the 'tail' differ significantly thanks to the zigzag. Because of our bound on the Gromov-Hausdorff distance (Theorem 11.1), this situation cannot occur if the red and blue sets are the medial axis of two sets with small Hausdorff distance between them.

On the two next examples of Figure 1 the red and the blue shapes do correspond to medial axes of two sets close to each other in Hausdorff distance (in dotted lines). On the middle, the medial axes are similar but not homeomorphic, so that the Frechet distance is infinite. In the last case they are homeomorphic but the Fréchet distance would still be large (you would need to rotate one of them by 90 • for the homeomorphism). In contrast, as asserted by Theorem 11.1, the Gromov-Hausdorff distance between them is small. Gromov-Hausdorff stability can be seen informally as a weakening of Frechet distance that ignores small scale features.

d F is large d GH is large d F is infinite d GH is small d F is large d GH is small

MOTIVATION 4.1 Medial axis computation algorithms and models of computation

The medial axis is known to be unstable in theory [START_REF] Attali | Stability and Computation of Medial Axes -a State-of-the-Art Report[END_REF], and, as a consequence, its computation is often problematic in practice. A typical illustration of this instability is when 𝐾 𝑐 is an open disk in the plane: its medial axis is a point, but a 𝐶 ∞ perturbation, arbitrary small, in the 𝐶 0 sense of differential topology [START_REF] Hirsch | Differential Topology[END_REF], of its boundary, may produce an arbitrary large perturbation (measured in the Hausdorff distance) of the resulting medial axis.

Computing the medial axis consists in, given as input some representation of the closed set 𝐾, to compute as output some representation of ax(𝐾). Let us recall two possible computation models under which what it means to "compute" 𝐾 ↦ → ax(𝐾).

In computational geometry, the implicit computation model (sometimes called exact computation paradigm in order to distinguish it from the unrealistic "Real RAM" computation model) assumes that both input and output can be exactly represented by finite data in the computer. This implies that input and output have to belong to countable sets,5 such as, for example, integer, rational or algebraic numbers, or polynomials built on top of them. Given a set of rational or algebraic points, or given a polyhedron with rational or algebraic vertices coordinates, for example, we now that the medial axis is a finite algebraic complex and, as such, belongs to a countable set, therefore exactly presentable on a computer. These are situations where it makes sense to compute the medial axis in this exact computation model, even if it may be difficult.

Computable analysis, pioneered with the notion of computable real numbers introduced by Turing in his 1936 undecidability paper [START_REF] Turing | On Computable Numbers, with an Application to the Entscheidungs problem, 1936. The essential Turing: seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma[END_REF][START_REF] Turing | On Computable Numbers, with an Application to the Entscheidungsproblem[END_REF], is studied in the logic and theoretical computer science literature [START_REF] Battenfeld | Topological domain theory[END_REF][START_REF] Brattka | A Tutorial on Computable Analysis[END_REF][START_REF] Grzegorczyk | Computable functionals[END_REF][START_REF] Ker | Complexity theory of real functions[END_REF][START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles[END_REF][START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles II[END_REF][START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles III[END_REF][START_REF] Lacombe | Remarques sur les opérateurs récursifs et surles fonctions récursives d'une variable réelle[END_REF][START_REF] Weihrauch | Computable analysis: an introduction[END_REF], but its formalism is most often ignored in applications.

However, it is actually implicit in many practical computations involving real numbers and real functions, for example in numerical analysis, where a typical example would be the finite element method. In this context, one considers that input and output can belong to topological spaces with countable bases of neighbourhoods, typically metric spaces with dense countable subsets, called separable metric spaces, who, as a consequence, have at most the cardinality of real numbers. Examples of such metric spaces are:

• Real numbers with their natural topology (rational numbers are dense). • Continuous functions on a compact set with the sup norm (polynomials with rational coefficients are dense, by the Stone-Weierstrass Theorem). • 𝐿 𝑝 (classes of) functions with their associated 𝐿 𝑝 norms (rational step functions are dense). • Compacts subsets of Euclidean spaces endowed with the Hausdorff distance (finite points sets in Q 𝑛 are dense).

In the context of these separable metric spaces, an algorithm, in this model of computation, takes as input a sequence belonging to the dense subset, so that each element of the sequence, belonging to a countable space, admits a finite representation. 6 It then computes, for each element of the input sequence, an element of the output sequence in such a way that the output sequence converges to the image of the limit of the input sequence. This mere definition assumes that the (theoretical) output of the limit of the input sequence, is the limit of the sequence of (actual) outputs of items of the input sequence. This is the reason why, in the context of computable analysis, only continuous functions, that commute with limits, can be computable 7 . For example, integer part function is computable, in this model, only at non-integer numbers. In decimal representation, if, after the dot, an infinite sequence of 9s appears, the algorithm would read the input forever.

Recall that a continuous function 𝜔 : R ≥0 → R ≥0 , with 𝜔 (0) = 0, is a modulus of continuity of a map 𝑓 : 𝑋 → 𝑌 between metric spaces if for all 𝑥 1 , 𝑥 2 ∈ 𝑋 ,

𝑑 𝑌 (𝑓 (𝑥 1 ), 𝑓 (𝑥 2 )) ≤ 𝜔 (𝑑 𝑋 (𝑥 1 , 𝑥 2 )).
If one wishes to control some form of theoretical algorithmic efficiency in the context of computable analysis, a modulus of continuity of the operator, that associates to some uncertainty on the input an upper bound on the induced uncertainty on the output, needs to be estimated.

We do not need to enter here in the technicalities of computable analysis. Our contribution consists in stating some explicit modulus of continuity, which, on the theoretical side, would be a crucial ingredient in the proofs of computability and complexity in the context of computable analysis, but is also, on the application side, a way to guarantee some accuracy in practical computations. Indeed, practical implementations of the computation of the medial axis apply some kind of approximation during the computation process. In a practical situation, this approximation process is already inherent to the data collection process, as any physical numerical measure is meant at some, finite, accuracy. Second, the actual input of an algorithm is often the output of a preceding algorithm which cannot, reasonably, be assumed recursively to compute exact output from exact inputs: recursion on algebraic numbers representations are possible along a finite depth of computation only. When, along the process, some form of rounding, pixelization, small features collapses or filtering, is performed, being able to upper bound the impact on the output seems sensible, and in fact necessary for provably correct algorithms.

Since 𝐾 ↦ → ax(𝐾) is not continuous in general when the topology of both inputs and outputs are defined by the Hausdorff distance, we see two ways of stating a continuity, or stability, property, for the operator 𝐾 ↦ → ax(𝐾). One possibility is to consider a stronger topology on the input, a form of Fréchet, or ambient diffeomorphism based, 𝐶 𝑘 distance, which would apply to smooth objects and representations.

Another possibility is to consider a weaker topology on the output, by considering filtered medial axes. In this model, the input sequence encodes 𝐾 in the form of approximations K𝑖 𝑖 ∈N that converge to 𝐾 in Hausdorff distance. For the K𝑖 one would typically choose finite point sets or (geometric) simplicial complexes (meshes/triangulations). As 𝑖 would increase in one would not only add more points or simplices to 𝐾 𝑖 , but also make the coordinates of the points/vertices more precise by adding digits to their coordinates.

The output sequence encodes ax(𝐾), in the form of progressive approximations of the map (𝜆, 𝜇) ↦ → ax 𝛼 𝜆 (𝐾), for decreasing values of 𝜆, 𝛼. These approximations (effectively) converge, where a basis of neighbourhoods (in the space of functions) of (𝜆, 𝛼) ↦ → ax 𝛼 𝜆 (𝐾) is given by the sets of maps (𝜆, 𝛼) ↦ → 𝑓 (𝜆, 𝛼) satisfying 𝜆, 𝛼 > 𝑡 ⇒ 𝑑 ★ (𝑓 (𝜆, 𝛼), ax 𝛼 𝜆 (𝐾)) < 𝜖 for some 𝜖, 𝑡 > 0. This approach does not require any smoothness assumption on 𝐾. The present paper focuses on this filtered approach, where the considered distance 𝑑 ★ between sets is either the Hausdorff distance, either the Gromov-Hausdorff distance on geodesic metric spaces.

Describing formally effective types and algorithms for the computation of the medial axis is beyond the scope of this paper. However, let us make some suggestions for further work in this direction. Probably the simplest model would consider the space of finite set of points with rational coordinates as inputs. These inputs together form a countable, and recursively enumerable set which is naturally equipped with the Hausdorff distance. The topological completion of the set of inputs gives all compact subsets of Euclidean space. The corresponding output space would consist of the filtered Voronoi Diagrams for which the coordinates of the Voronoi vertices are rational numbers. The Hölder modulii of continuity proven in this paper would allow to formally state the effectivity of the model.

The model could also be formalized in the context of Scott domains [START_REF] Abramsky | Domain theory[END_REF][START_REF] Edalat | A computational model for metric spaces[END_REF], [START_REF] Roberto | Domains and lambda-calculi[END_REF]Chapter 1] and their associated information orders. 8 In this context, our results answer the following question: If the only information we have about some compact set 𝐾 is its Hausdorff approximation 𝐾 ′ , what information can we infer about its medial axis ax(𝐾)?

4.2 Motivation from mathematics: the stability of the cut locus.

The medial axis is closely related to the cut locus. We recall Definition 4.1. Let M be a smooth (closed) Riemannian manifold and let 𝑝 ∈ M. For every 𝑣 ∈ 𝑇 𝑝 M, with |𝑣 | = 1, we can consider the geodesic 𝛾 𝑣 (𝑡) = exp 𝑝 (𝑡𝑣) emanating from 𝑝 in the direction 𝑣. Let 𝛾 𝑣 (𝜏) be the first point along 𝛾 𝑣 such that the geodesic {𝛾 𝑣 (𝑡) | 𝑡 ∈ [0, 𝜋]} is no longer the unique minimizing geodesic to 𝑝. The cut locus of 𝑝 is the union of these points for all unit length 𝑣 in 𝑇 𝑝 M.

The cut locus is therefore more general in the sense that it is defined for general Riemannian manifolds, while more restrictive in the sense that it only considers a single point. 9The stability and structure of the singularities of the cut locus has been a studied intensely. Buchner [START_REF] Michael | Stability of the cut locus in dimensions less than or equal to 6[END_REF] derived the following result: Theorem 4.2. Let 𝐺 be the space of metrics on a smooth manifold, endowed with the Whitney topology. Each metric 𝑔 ∈ 𝐺 and 𝑝 ∈ M yield a cut locus 𝐶 𝑝,𝑔 . The cut locus 𝐶 𝑝,𝑔 is called stable if there is a neighbourhood 𝑊 ⊂ 𝐺 of 𝑔 such that for any 𝑔 ′ ∈ 𝑊 there exists a diffeomorphism Φ : M → M such that Φ(𝐶 𝑝,𝑔 ′ ) = 𝐶 𝑝,𝑔 . If the dimension of M is low (≤ 6) then 𝐶 𝑝,𝑔 is stable for an open and dense subset of 𝐺.

Wall [START_REF] Wall | Geometric properties of generic differentiable manifolds[END_REF] extended this result to arbitrary dimensions at the cost of weakening the diffeomorphism to a homeomorphism. The structure of the singularities of the cut locus were also described by Buchner in [START_REF] Michael | The structure of the cut locus in dimension less than or equal to six[END_REF]. A similar description for the singularities of medial axis of a smooth manifold can be found in [START_REF] Yomdin | On the local structure of a generic central set[END_REF], see also [START_REF] Mather | Distance from a submanifold in Euclidean space[END_REF], as well as [START_REF] Martijn Van Manen | Maxwell strata and caustics[END_REF].

This paper follows the tradition of these investigations of the stability of cut locus and the medial axis. However, there are also some significant differences. First and foremost we take a metric viewpoint instead of analytical. This viewpoint does not require us to make a distinction between low dimensional and high dimensional spaces. We made the constants explicit in view of the applications in computer science, in particular computational geometry and topology, shape recognition, shape segmentation, and manifold learning.

The authors are currently working on the stability of the cut locus and medial axis of smooth sets, using the tools which we develop in this paper.

OVERVIEW OF THE STABILITY OF THE 𝜆-MEDIAL AXIS

Under mild conditions, the 𝜆-medial axis enjoys some nice stability properties, assuming that 𝐾 𝑐 is bounded. Informally:

( Property 1 gives some stability on the homotopy type with respect to Hausdorff perturbation of 𝐾, since, under similar conditions on the critical function of 𝐾, when 𝑑 ℎ (𝐾, 𝐾 ′ ) is small, the offsets of 𝐾 ′ may share the homotopy type of 𝐾 [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF][START_REF] Chazal | Weak feature size and persistent homology: computing homology of solids in R 𝑛 from noisy data samples[END_REF]. Properties 2 and 3 give precise, quantified, stability results, much stronger than the mere half-continuity of the medial axis itself, see e.g. [START_REF] Attali | Stability and Computation of Medial Axes -a State-of-the-Art Report[END_REF].

CONTRIBUTIONS: THE IMPROVED STABILITY OF THE (𝜆, 𝛼)-MEDIAL AXIS

Before entering into the formal proofs, let us give some intuition about the (𝜆, 𝛼)-medial axis stability. This improved stability can be illustrated in the case of a finite set 𝐾. Figure 2 illustrates the (𝜆, 𝛼)-medial axis in the simplest nontrivial case, where 𝐾 consists of two points in the plane. In this case the 𝜆-medial axis would be empty as long as 𝜆 is strictly greater than the half distance between the two points and it would become the whole bisector line as soon as 𝜆 is smaller or equal to this value. Comparison between 𝜆-medial axis and (𝜆,𝛼)medial axis evolutions for increasing 𝜆, in the particular case where 𝐾 consists of two points in the plane. The 𝜆medial axis would be either the whole bisector line of the two points, for 𝜆 smaller or equal to half the distance between the points, either the empty set for larger value of 𝜆. By contrast, the evolution, for increasing 𝜆, of the (𝜆, 𝛼)medial axis, which is also the 𝜆-medial axis of the union of two disks of radius 𝛼, evolves continuously, in Hausdorff distance, as 𝜆 increases.

By contrast, the (𝜆, 𝛼)-medial axis, for a fixed value of 𝛼 > 0, here the radius of the two disks of the 𝛼-offset of 𝐾, is Hausdorff continuous with respect to 𝜆. Indeed, as 𝜆 increases, when 𝛼 + 𝜆 equals the half distance between the two points, ax 𝛼 𝜆 (𝐾), which until then is the whole bisector line, starts to be disconnected, creating a hole. But, since the hole grows continuously, its birth is not a discontinuity for the Hausdorff distance. However, in the neighborhood of this event, the hole size grows quadratically with 𝜆: This does not contradict the claim that the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is Lipschitz, as the precise conditions of the claim require us to avoid situations where 𝛼 + 𝜆 is a zero of 𝜒 𝐾 . Figure 3: Comparison between 𝜆-medial axis and (𝜆,𝛼)medial axis evolutions for increasing 𝜆, in the particular case where 𝐾 is a finite subset of the plane. In this case both filtered medial axes are subsets of the union of the edges of the Voronoi diagram. On the second row, the points have been replaced by disks of radius 𝛼, offset of the points. The evolution of the (𝜆,𝛼)-medial axis is Hausdorff continuous whenever 𝛼 + 𝜆 is not a critical value of the distance function. On the other hand, as seen on first row, the 𝜆-medial axis contains precisely the whole Voronoi edges or vertices whose dual simplex lies in a ball of radius 𝜆. The 𝜆-medial axis is therefore Hausdorff discontinuous for each value of 𝜆 which is the radius of the smallest ball enclosing some Delaunay simplex.

Figure 3 shows a situation where 𝐾 is made of four points in the plane. The 𝜆-medial axis is made of these edges and vertices whose dual Delaunay simplex has smallest enclosing radius greater or equal to 𝜆. As a function of 𝜆, it is therefore Hausdorff distance discontinuous for each value of 𝜆 that is equal to a such radius.

In contrast, the (𝜆, 𝛼)-medial axis, as a function of 𝜆 for fixed 𝛼 > 0, can be Hausdorff discontinuous only when 𝛼 + 𝜆 is a zero of the critical function 𝜒 𝐾 . We have depicted such a transition in Figure 4: Here we increase 𝜆 further until 𝛼 + 𝜆 = 𝜌, where 𝜌 is the circumradius of the unique acute triangle in the Delaunay diagram, and therefore the unique value of the distance to 𝐾 corresponding to a local maximum. Until 𝛼 + 𝜆 = 𝜌 the (𝜆, 𝛼)-medial axis would contain the Voronoi vertex dual to this acute triangle (for 𝛼 + 𝜆 = 𝜌 the Voronoi vertex would be an isolated point). Since this points would disappear from the (𝜆, 𝛼)-medial axis for 𝛼 + 𝜆 > 𝜌, it results a Hausdorff distance discontinuity of 𝜆 ↦ → ax 𝛼 𝜆 (𝐾). In general, Hausdorff distance discontinuities of 𝜆 ↦ → ax 𝜆 (𝐾) may appear anywhere, at some "non regular values", as mentioned in item 3 of Section 5 and illustrated on top row of Figure 3 (where 𝜆 is a zero of 𝜒 𝐾 ) and in Figure 9 (where 𝜆 is not a zero of 𝜒 𝐾 ). By contrast, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾), for 𝛼 > 0, is continuous (locally Lipschitz) when 𝜒 𝐾 (𝛼 + 𝜆) does not vanish, in other words the interval on which the homotopy type of ax 𝛼 𝜆 (𝐾) remains stable.

6.1 The case of a set 𝐾 ⊂ R 𝑛 with positive 𝜇-reach and its Hausdorff approximation 𝐾 ′

In Part II we consider the general situation of sets whose 𝛼-offsets have positive 𝜇-reach. In particular, Lemma 10.7 and Theorem 11.1 use a symmetrical formulations on the pair of sets 𝐾 and 𝐾 ′ in order to state a modulus of continuity for the map 𝐾 ↦ → ax 𝛼 𝜆 (𝐾), where the metric on 𝐾 is the Hausdorff distance and the metric on the medial axis can be either the Hausdorff distance or the Gromov-Hausdorff distance.

In this section we consider the simpler setting, where we don't need to offset for 𝐾 to achieve positive 𝜇 reach, that is 𝑟 𝜇 (𝐾) > 0 and we are given a set 𝐾 ′ that is close to 𝐾 in terms of the Hausdorff distance. This allows a concise formal expression of our main results in a simpler setting, while illustrating a typical application.

Overall this section, we make the following assumption: Assumption 6.1 (Assumption for Section 6.1). We assume 𝐾, 𝐾 ′ to be closed sets such that, for some 𝜖 > 0, 𝑑 𝐻 (𝐾 ′ , 𝐾) < 𝜖, 𝑟 𝜇 (𝐾) > 0 and, the complements 𝐾 𝑐 and 𝐾 ′𝑐 to be bounded: denoting B(0, 𝑅) ⊂ R 𝑛 the ball of radius 𝑅 > 0, one has 𝐾 ∪B(0, 𝑅) = 𝐾 ′ ∪B(0, 𝑅) = R 𝑛 . We assume moreover 0 < 𝛼 < 𝛼 max and 0 < 𝜆 < 𝜆 max , for 𝛼 max + 𝜆 max < 𝑟 𝜇 (𝐾)/2 and we denote μ = min(𝜇,

√ 3/2).
In particular, assuming 𝛼 max + 𝜆 max < 𝑟 𝜇 (𝐾)/2 allows a simple expression for μ.

Hausdorff stability.

As a consequence of Lemma 9.4 and Lemma 9.5 we have that: Proposition 6.2. For any 𝜆 min > 0, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is

𝑅 2 𝛼𝜆 min μ2 -Lipschitz in the interval [𝜆 min , 𝜆 max ] for Hausdorff distance.
Similarly, for 𝛼 min > 0, the map 𝛼 ↦ → ax 𝛼 𝜆 (𝐾) is

𝑅 2
𝛼 min 𝜆 μ2 -Lipschitz in the interval [𝛼 min , 𝛼 max ] for Hausdorff distance.

We will now combine this with a result from [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]Theorem 3.4]. Let 𝜇 ′ < 𝜇 and 𝛼 > 0. By definition of 𝑟 𝜇 (𝐾), the critical function of 𝐾 is above 𝜇 on the interval (0, 𝑟 𝜇 (𝐾)). Theorem 3.4 of [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] now says that if 𝐾 ′ is sufficiently close to 𝐾 in Hausdorff distance, then the critical function of 𝐾 ′ will also be above 𝜇 ′ on the interval (𝛼, 𝑟 𝜇 (𝐾) -𝛼), see Figure 7. In other words, there is 𝜖 > 0 such that:

𝑑 𝐻 (𝐾 ′ , 𝐾) < 𝜖 ⇒ 𝑟 𝛼 𝜇 ′ (𝐾 ′ ) > 𝑟 𝜇 (𝐾) -𝛼 . (3)
Then, Lemma 10.7 gives us that:

Proposition 6.3. Denoting μ′ = min(𝜇 ′ , √ 3/2)
, there is 𝜖 max > 0 depending only on 𝐾, such that, for, 𝜖 < 𝜖 max , one has:

𝑑 𝐻 ax 𝛼 𝜆 (𝐾 ′ ), ax 𝛼 𝜆 (𝐾) < 22 3 𝑅 2 𝛼 1 2 μ′ 3 2 𝜆 𝜖 1 2 . ( 4
)
Note that, thanks to [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF], under the conditions of the proposition, that is for sufficiently small 𝜖, ax 𝛼 𝜆 (𝐾 ′ ), ax(𝐾) and 𝐾 𝑐 have same homotopy type (Theorem 9.7 below).

6.1.2 Gromov-Hausdorff stability. Lemma 9.11 and Theorem 9.12 give an explicit upper bound in the geodesic diameter of ax 𝛼 𝜆 (𝐾), assuming 𝐾 𝑐 to be connected, as:

GeoDiameter(ax 𝛼 𝜆 (𝐾)) ≤ 2 𝑅 μ2 + 2𝛼 4𝑅 𝛼 𝑛 + 1 + 2 𝜇 𝑒 1 𝜇 + 𝑅 𝛼 μ2
(5) Thanks to (3), a similar bound holds for GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ )), for sufficiently small 𝜖.

This bound is exponential in 2𝑅 𝛼 μ2 and therefore increases quickly as 𝛼 → 0. We do not know if this bound is close to be tight. 10 Lemmas 9.14 and 9.15 give: Proposition 6.4. For any 𝜆 min > 0, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is

𝑅 2 (2𝛼 min 𝜆 min +𝐷 𝛼 2 min μ2 -Lipschitz in the interval [𝜆 min , 𝜆 max ] for Gromov- Hausdorff distance, where 𝐷 = max 𝜆 ∈ [𝜆 min ,𝜆 max ]
GeoDiameter(ax 𝛼 𝜆 (𝐾)).

Similarly, for 𝛼 min > 0, the map

𝛼 ↦ → ax 𝛼 𝜆 (𝐾) is 𝑅 (2𝛼 min +𝐷 𝛼 2 min μ2 - Lipschitz in the interval [𝛼 min , 𝛼 max ] for Gromov-Hausdorff distance, where 𝐷 = max 𝜆 ∈ [𝛼 min ,𝛼 max ] GeoDiameter(ax 𝛼 𝜆 (𝐾)
). Note that the geodesic diameter enters as a factor in the Lipschitz constant. This is due to the fact that the Gromov-Hausdorff distance is defined as a global upper bound on differences of lengths, while, here, the metrics differ mainly by a multiplicative factor. In a sense, the metric discrepancy would be more tightly bounded by a mix of additive and multiplicative bounds, where Gromov-Hausdorff distances consider additive discrepancy only. Replacing 𝐷 by its universal upper bound ( 5) is likely, in general, to give an overestimated Lipschitz constant with respect to the one using the actual diameter 𝐷 = max 𝜆 ∈ [𝛼 min ,𝛼 max ] GeoDiameter(ax 𝛼 𝜆 (𝐾)). Also, Theorem 11.1 gives us: Proposition 6.5. Denoting μ′ = min(𝜇 ′ , √ 3/2), there is 𝜖 max > 0 depending only on 𝐾, such that, for, 𝜖 < 𝜖 max , one has:

𝑑 𝐺𝐻 ax 𝛼 𝜆 (𝐾 ′ ), ax 𝛼 𝜆 (𝐾) < 2 22 3 3 2 𝑅 3 (2𝛼 min + 𝐷) 𝛼 7 4 min μ′ 9 4 𝜆 3 2 𝜖 1 4 , (6)
where 𝐷 = max(GeoDiameter(ax 𝛼 𝜆 (𝐾)), GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ ))). Again, taking for 𝐷 the upper bound (5) allows a uniform bound which is enough in theory.

For a more practical bound on 𝑑 𝐺𝐻 ax 𝛼 𝜆 (𝐾 ′ ), ax 𝛼 𝜆 (𝐾) it would be easier to calculate a bound on the geodesic diameter of ax 𝛼 𝜆 (𝐾 ′ ). For example, if 𝐾 ′ is finite (in fact the union of the complement of B • (0, 𝑅) with a finite set) one could determine a bound on the geodesic diameter of the subset of the (𝑛 -1)-skeleton of part of the Voronoi diagram corresponding to ax 𝛼 𝜆 (𝐾 ′ ).

Method

All proofs in the paper are based on the flow of the (generalized) gradient of the distance function from a point 𝑥 to 𝐾, see Section 8.2 for a formal definition. The flow has been used before, among others to establish the following results:

• The medial axis has the same homotopy type as the set [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF].

• The topologically guaranteed reconstruction for non-smooth sets [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]. The flow also plays a central role in the work on the 𝜆-medial axis [START_REF] Chazal | The 𝜆-medial axis[END_REF]. These tools were developed for non-smooth objects, and rely on the weak regularity properties based on the 𝜇-reach and the critical function (Section 8.2). Our stability results rely on the stability of the flow and its gradient under Hausdorff perturbation of 𝐾, and by quantifying how quickly we enter the (𝜆, 𝛼)-medial axis following the flow of the gradient, assuming that we start not too far from the (𝜆, 𝛼)-medial axis.

FUTURE WORK

Beyond the stability properties presented in this paper, several questions remain open. We do not know if our moduli of continuity are optimal, or if other filtrations could offer better Hölder exponents for the stability. More precisely, because the dependence of the (𝜆,𝛼)-medial axis on 𝜆 and 𝛼 is Lipschitz, it is only the Lipschitz constant that can be improved. This contrasts with the Hölder exponents for the map 𝐾 ↦ → ax 𝛼 𝜆 , namely 1 2 for the Hausdorff distance and 1 4 the Gromov-Hausdorff distance, which may not be optimal. Our stability property expressed in term of Gromov-Hausdorff distance hides a stronger statement. Indeed the Gromov-Hausdorff distance applies to two independent metric spaces, while our two metric spaces are also subset of a same Euclidean space. While this has not been made explicit in the statement of Theorem 11.1, when 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖, (82) gives a O (𝜖 ) Gromov-Hausdorff distance. For example, in Figure 1 on the right, a simple rotation could define a relation giving a zero Gromov-Hausdorff distance (an isometry), while in fact our construction defines another relation for which points in relation are much closer in ambient space. In order to fully express our stability properties induced by the flow, we should introduce in a future work a sharpening of the Gromov-Hausdorff distance, where the relation realizes not only a small geodesic metric distortion, but also a small ambient displacement.

PART II: THE TECHNICAL STATEMENTS AND PROOFS 8 DEFINITIONS AND PREVIOUS WORK

In this section, we recall some definitions and results, mainly introduced in [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF][START_REF] Chazal | The 𝜆-medial axis[END_REF][START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF], in order to make the paper self-contained.

Throughout the paper, 𝐾 will be a closed subset of R 𝑛 , whose complement 𝐾 𝑐 is bounded and connected.The fact that 𝐾 𝑐 is connected is essential for the medial axis to be patch connected and thus is needed for a bound on the geodesic diameter. The geodesic diameter in turn is needed for the bound on the Gromov-Hausdorff distance (our bound is proportional to the geodesic diameter). We stress that the connectedness assumption is not required for our results on the Hausdorff distance.

Homotopy equivalence and weak deformation retraction

A homotopy equivalence between topological spaces 𝑋 and 𝑌 where 𝑌 ⊂ 𝑋 and the map from 𝑌 to 𝑋 is the inclusion map, is called weak deformation retract, more formally: Definition 8.1 (weak deformation retract). If 𝑌 ⊂ 𝑋 and there exists a continuous map 𝐻 : [0, 1] × 𝑋 → 𝑋 such that:

• ∀𝑥 ∈ 𝑋, 𝐻 (0, 𝑥) = 𝑥, • ∀𝑥 ∈ 𝑋, 𝐻 (1, 𝑥) ∈ 𝑌 , • ∀𝑦 ∈ 𝑌, ∀𝑡 ∈ [0, 1], 𝐻 (𝑡, 𝑦) ∈ 𝑌 ,
then we say that 𝐻 is a weak deformation retract of 𝑋 on 𝑌 . In particular 𝑋 and 𝑌 have same homotopy type.

The medial axis and associated flow

We define the following functions on R 𝑛 associated to 𝐾:

𝑥 ↦ → 𝑅 𝐾 (𝑥) = def. 𝑑 (𝑥, 𝐾) = min 𝑦 ∈𝐾 𝑑 (𝑥, 𝑦) (7)
𝑥 ↦ → Θ 𝐾 (𝑥) = def. {𝑦 ∈ 𝐾 | 𝑑 (𝑥, 𝑦) = 𝑅 𝐾 (𝑥)} . (8)
For a bounded set 𝑆 we denote the center of the smallest ball enclosing 𝑆 by center(𝑆), we write radius(𝑆) for the radius of this ball.

We further define,

F 𝐾 (𝑥) = def. radius(Θ 𝐾 (𝑥)) (9)
and for 𝑥 ∉ 𝐾:

∇ 𝐾 (𝑥) = def. 𝑥 -center(Θ 𝐾 (𝑥)) 𝑅 𝐾 (𝑥) (10)
The medial axis ax(𝐾) of 𝐾 is defined as: For any 𝑥 ∈ 𝐾 𝑐 , including when 𝑥 ∈ ax(𝐾), ∇ 𝐾 (𝑥) could have been equivalently defined as the projection of 0 on the Clarke gradient, see [START_REF] Frank | Optimization and Nonsmooth Analysis[END_REF], of 𝑥 ↦ → 𝑅 𝐾 (𝑥). However the definition ( 10) is more convenient in our context and does not require the formal introduction of Clarke gradient, which is technical. For this reason, we call ∇ 𝐾 (𝑥) the generalized gradient of 𝑥 ↦ → 𝑅 𝐾 (𝑥). Thanks to the definition of ∇ 𝐾 (𝑥), and Pythagoras, see that for 𝑥 ∉ 𝐾 one has:

ax(𝐾) = def. {𝑥 ∈ R 𝑛 | F 𝐾 (𝑥) > 0} = {𝑥 ∈ R 𝑛 | ♯ (Θ 𝐾 (𝑥)) ≥ 2} (
∀𝑥 ∈ 𝐾 𝑐 , ∥∇ 𝐾 (𝑥) ∥ 2 = 1 - F 𝐾 (𝑥) 𝑅 𝐾 (𝑥) 2 . (12)
In [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF] we have seen that there exists a locally Lipschitz, and therefore continuous, flow Φ 𝐾 : R ≥0 × 𝐾 𝑐 → 𝐾 𝑐 such that: It was established in [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF] that ax(𝐾) has same homotopy type as 𝐾 𝑐 . This result is based on the fact that the flow Φ 𝐾 realizes the homotopy equivalence 𝐾 𝑐 → ax(𝐾) for a finite 𝑡 (see Definition 8.1). In the particular case when 𝐾 is a finite set, the flow Φ 𝐾 is equivalent to the flow that induces the flow complex [START_REF] Giesen | The flow complex: A data structure for geometric modeling[END_REF] of 𝐾.

∀𝑥 ∈ 𝐾 𝑐 , Φ 𝐾 (0, 𝑥) = 𝑥 ∀𝑥 ∈ 𝐾 𝑐 , ∀𝑡 ≥ 0, 𝑑 𝑑𝑡 + Φ 𝐾 (𝑡, 𝑥) = ∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) (13) ∀𝑥 ∈ 𝐾 𝑐 , ∀𝑡 1 , 𝑡 2 ≥ 0, Φ 𝐾 (𝑡 1 , Φ 𝐾 (𝑡 2 , 𝑥)) = Φ 𝐾 (𝑡 1 + 𝑡 2 , 𝑥). (14)
We further recall the following: Lemma 8.2 (Lemma 4.16 of [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]). [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]). The map F 𝐾 is upper semicontinuous.

∀𝑡 ≥ 0, ∀𝑥 ∈ 𝐾 𝑐 , 𝑑 𝑑𝑡 + 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) = ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) ∥ 2 . (15) Lemma 8.3 (Corollary 4.7 of
Lemma 8.4 (Lemma 4.17 of [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]). The map 𝑡 ↦ → F 𝐾 (Φ 𝐾 (𝑡, 𝑥)) is non-decreasing (i.e. increasing but not necessarily strictly increasing) and therefore, by Lemma 8.3 right-continuous.

𝑅 𝐾 (𝑥 1 ), 𝑅 𝐾 (𝑥 2 ) ≥ 𝛼 ⇒ ∥Φ 𝐾 (𝑡, 𝑥 2 ) -Φ 𝐾 (𝑡, 𝑥 1 )∥ ≤ ∥𝑥 2 -𝑥 1 ∥ 𝑒 𝑡 𝛼 . ( 16
)

Critical function, 𝜇-reach and Weak

Feature Size

As we have seen in Section 2, the critical function 𝜒 𝐾 : (0, ∞) → [0, 1], is defined as

𝜒 𝐾 (𝑡) = def.
inf

𝑅 𝐾 (𝑥)=𝑡 √ 1 - F 𝐾 (𝑥) 𝑅 𝐾 (𝑥) 2 . (1)
In this setting we say that the infimum over the empty set yields 1.We'll now discuss the intuition behind this function. The critical function provides us in a certain sense with some lower bound on the norm of the vector field ∇ 𝐾 (𝑥) whose flow (Φ 𝐾 ) we follow. Figure 7 illustrates the critical function when 𝐾 is a (hollow) square in R 3 . The medial axis of the square is an infinite prism, which is the product of the squares's diagonals and the line orthogonal to the square supporting plane. The infimum in (1) is first attained along the square diagonals, where

𝜒 𝐾 (𝑡) = 1/ √ 2 since there F 𝐾 (𝑥) = 𝑅 𝐾 (𝑥) √ 2
. Then when the offset reaches the square center we get F 𝐾 (𝑥) = 𝑅 𝐾 (𝑥) and therefore 𝜒 𝐾 (𝑡) = 0. The topology of the offset then changes and, after this critical value, the inf is then reached on the line through the square center and orthogonal to the square supporting plane.

The critical function enjoys some stability properties with respect to Hausdorff distance perturbation [19, Theorem 4.2], illustrated in Figure 7. If two sets 𝐾 and 𝐾 ′ are close enough in Hausdorff distance, their critical functions 𝑡 ↦ → 𝜒 𝐾 (𝑡) and 𝑡 ↦ → 𝜒 𝐾 ′ (𝑡) are close to each other, for 𝑡 large enough.

The critical function has been introduced in Section 2 and illustrated in Figure 7. In [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] the critical function 𝜒 𝐾 : (0, ∞) → [0, 1] was defined for a compact set 𝐾. We adapt it to a closed set 𝐾 with bounded complement.

On a closed set 𝐾 with bounded complement the function 𝑅 𝐾 attains a maximum:

𝑅 max (𝐾) = def. sup 𝑥 ∈𝐾 𝑐 𝑅 𝐾 (𝑥) = max 𝑥 ∈𝐾 𝑐 𝑅 𝐾 (𝑥). ( 17
)
Figure 7: (Adapted from [START_REF] Boissonnat | Geometric and topological inference[END_REF])). On the top, the critical function 𝜒 𝐾 of a square 𝐾 in R 3 together with the corresponding level sets 𝑅 -1 𝐾 (𝑡) of the distance to 𝐾, on which the inf is taken in equation [START_REF] Abramsky | Domain theory[END_REF]. The topology of offsets changes only when 𝜒 𝐾 (𝑡) = 0, that is when 𝑡 = 𝑡 𝑐𝑟𝑖𝑡 . which is the half of the square side. For 𝑡 ∈ (0, 𝑡 𝑐𝑟𝑖𝑡 . ),

𝜒 𝐾 (𝑡) = 1/ √ 2 since, for 0 < 𝑡 < 𝑡 𝑐𝑟𝑖𝑡 . , the inf in (1) is For 𝑡 ∈ (0, 𝑡 𝑐𝑟𝑖𝑡 . ) we have that 𝜒 𝐾 (𝑡) = 1/ √ 2.
This can be seen as follows: For 0 < 𝑡 < 𝑡 𝑐𝑟𝑖𝑡 . the inf in (1) is attained on the intersection of 𝑅 -1 𝐾 (𝑡), the supporting plane of the square, and the medial axis. This intersection equals the diagonals of the square. It follows immediately from Pythagoras that F 𝐾 (𝑥)

= 𝑅 𝐾 (𝑥) √ 2
. This value is indeed strictly smaller than 1 as the reach of the square is 0.

At the bottom, the critical function of a set 𝐾 ′ (here a finite set), close, in Hausdorff distance, to 𝐾. For large enough offset 𝑡, 𝜒 𝐾 ′ is close to 𝜒 𝐾 . In particular, if 𝑑 𝐻 (𝐾 ′ , 𝐾) is small enough with respect to 𝑡 𝑐𝑟𝑖𝑡 . , Theorem [19, Theorem 4.2] provides a lower bound on the critical function of 𝐾 ′ , which is then guaranteed to not vanish on some interval subset of (0, 𝑡 𝑐𝑟𝑖𝑡 . ).

The critical function of 𝐾 is the function 𝜒 𝐾 : (0, 𝑅 max (𝐾)] → [0, 1] defined as:

𝜒 𝐾 (𝑡) = def. inf 𝑅 𝐾 (𝑥)=𝑡 ∥∇ 𝐾 (𝑥)∥.
As a consequence of [START_REF] Martin R Bridson | Metric spaces of non-positive curvature[END_REF], one has 𝜒 𝐾 (𝑅 max ) = 0. For 𝜇 ∈ (0, 1], the 𝜇-reach of 𝐾, denoted 𝑟 𝜇 (𝐾) is defined as:

𝑟 𝜇 (𝐾) = def. inf {𝑡 | 𝜒 𝐾 (𝑡) < 𝜇} = sup {𝑟 | 𝑅 𝐾 (𝑥) < 𝑟 ⇒ ∥∇ 𝐾 (𝑥)∥ ≥ 𝜇} .
For 𝜇 = 1, 𝑟 1 (𝐾) is also known as the reach of 𝐾. The Weak Feature Size of 𝐾, denoted wfs(𝐾) is defined as the first critical value of the distance function, that is the first value at which 𝜒 𝐾 vanishes

wfs(𝐾) = def. inf {𝑡 | 𝜒 𝐾 (𝑡) = 0}. ( 18
)
Since 𝑥 ↦ → F 𝐾 (𝑥) is upper semi-continuous, see Corollary 4.7 of [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF], 𝜒 𝐾 is lower semi-continuous. The lower semi-continuity of 𝜒 𝐾 has a number of consequences:

• If 0 < wfs(𝐾), then we have 𝜒 𝐾 (wfs(𝐾)) = 0, so that

wfs(𝐾) > 0 ⇒ wfs(𝐾) = min{𝑡 | 𝜒 𝐾 (𝑡) = 0}.
This follows by combining the lower semi-continuity with the definition of the weak feature size [START_REF] Chambers | Video: A Cautionary Tale: Burning the Medial Axis Is Unstable[END_REF]. • By definition of 𝑟 𝜇 (𝐾) (and lower semi-continuity of 𝜒 𝐾 ) we have that, for any 𝜇 > 0, 𝑟 𝜇 (𝐾) < wfs(𝐾).

• If 0 < sup{𝑟 𝜇 (𝐾) | 𝜇 > 0} < ∞, then 𝜒 𝐾 (sup{𝑟 𝜇 (𝐾) | 𝜇 > 0}) = 0. Because wfs(𝐾) > 0 ⇒ sup{𝑟 𝜇 (𝐾) | 𝜇 > 0} > 0, it follows that: wfs(𝐾) > 0 ⇒ wfs(𝐾) = sup{𝑟 𝜇 (𝐾) | 𝜇 > 0}. ( 19
)

Gromov-Hausdorff distance

For 𝛼 ≥ 0, the 𝛼-offset of 𝐾 denoted 𝐾 ⊕𝛼 is the set of points lying at distance at most 𝛼 from 𝐾:

𝐾 ⊕𝛼 = def. {𝑥 ∈ R 𝑛 | 𝑑 (𝑥, 𝐾) ≥ 𝛼 }, (20)
where 𝑑 (𝑥, 𝐾) =

We now define the Gromov-Hausdorff distance between two metric spaces 𝑋 1 and 𝑋 2 . We follow [15, Section 5.33], with minor modifications in the formulation for compatibility. Definition 8.7 (Gromov-Hausdorff distance). An 𝜀-relation between two metric spaces 𝑋 1 and and 𝑋 2 is a subset R ⊂ 𝑋 1 × 𝑋 2 such that:

(1) For 𝑖 = 1, 2, the projection of R to 𝑋 𝑖 is surjective.

(

) If (𝑥 1 , 𝑥 2 ), (𝑥 ′ 1 , 𝑥 ′ 2 ) ∈ R then, 𝑑 𝑋 1 (𝑥 1 , 𝑥 ′ 1 ) -𝑑 𝑋 2 (𝑥 2 , 𝑥 ′ 2 ) < 𝜀. 2
If there exists an 𝜀-relation between 𝑋 1 and and 𝑋 2 then we write 𝑋 1 ≃ 𝜀 𝑋 2 . We define the Gromov-Hausdorff distance between 𝑋 1 and 𝑋 2 to be

𝑑 GH (𝑋 1 , 𝑋 2 ) = inf {𝜀, 𝑋 1 ≃ 𝜀 𝑋 2 } . ( 23
)

The topology of the 𝜆-medial axis

In [START_REF] Chazal | The 𝜆-medial axis[END_REF] the 𝜆-medial axis was introduced for 𝜆 > 0 as:

ax 𝜆 (𝐾) = def. {𝑥 ∈ R 𝑛 | F 𝐾 (𝑥) ≥ 𝜆}.
By definition the 𝜆-medial axis has the following properties: It follows from Lemma 8.3 that: Lemma 8.8. ax 𝜆 (𝐾) is closed and therefore, since 𝐾 𝑐 is bounded, it is compact.

𝜆 1 ≥ 𝜆 2 ⇒ ax 𝜆 1 (𝐾) ⊂ ax 𝜆 2 (𝐾),
As a consequence of Lemma 8.4, using Definition 8.1, the flow Φ 𝐾 can be used to show that: Theorem 8.9 (Theorem 2 of [START_REF] Chazal | The 𝜆-medial axis[END_REF]). If 𝜆 < wfs(𝐾), then ax 𝜆 (𝐾) has the homotopy type of 𝐾 𝑐 .

Fundamental Theorem of calculus for Lipschitz functions

As in [START_REF] Chazal | The 𝜆-medial axis[END_REF][START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF] we apply the fundamental theorem of calculus to Lipschitz functions while it is usually stated in the context of differentiable functions.

We recall that it follows trivially from the definitions that Lipschitz functions are in particular absolutely continuous and: Theorem 8.10 (Adapted from Theorem 6.4.2 in [32]). If 𝑓 : [𝑎, 𝑏] → R, then the following two statements are equivalent. ). We note that even though this result is ascribed to Čaplygin the result was already known to Peano, we refer to [46, page 316] and the reference mentioned there for more information.

However because we deal with functions that are not differentiable we need an integral version of the statement. For this we'll adapt a number of definitions and results on Volterra integral inequalities from [55, Chapter I], see also [START_REF] Alekseev | A theorem on an integral inequality and some of its applications[END_REF][START_REF] Perov | On integral inequalities[END_REF]. We first make the following definitions: Integral equations of the form

𝑥 (𝑡) = 𝑔(𝑡) + ∫ 𝑡 0 𝑘 (𝑥 (𝜏))d𝜏
are called Volterra integral equations and 𝑘 (𝑥) its kernel. In general these kernels are allowed to depend on 𝑡, but we don't need this in our context. The class 𝑍 𝑐 (𝑘) of admissible function for the kernel 𝑘 are the functions 𝜙 (𝜏) such that 𝑘 (𝜙 (𝜏)) exists and is integrable.

We say that the kernel is monotone increasing if 𝑘 (𝑥) ≤ 𝑘 (x) for all 𝑥 ≤ x in its domain, and strictly monotone if this still holds when both bounds are replaced by strict inequalities. We have, Theorem 8.12. Suppose that 𝑘 (𝑥) is a monotone increasing kernel, 𝑥 (𝑡), 𝑦 (𝑡) ∈ 𝑍 𝑐 (𝐾), and 𝐶 1 a constant. Further assume that

𝑦 (𝑡) = 𝐶 1 + ∫ 𝑡 0 𝑘 (𝑦 (𝜏))d𝜏 𝑥 (𝑡) ≥ 𝐶 1 + ∫ 𝑡 0 𝑘 (𝑥 (𝜏))d𝜏,
for all 𝑡 in the domain, where equality in the second equation only occurs for 𝑡 = 0. Moreover assume that there exists a 𝛿 ′ > 0 such that for all 𝑡 ′ ∈ (0, 𝛿 ′ ), we have 𝑦 (𝑡 ′ ) < 𝑥 (𝑡 ′ ). Then for all 𝑡 in the domain, 𝑦 (𝑡) ≤ 𝑥 (𝑡), where equality occurs only for 𝑡 = 0.

Proof. For any 𝑡 ′ ∈ (0, 𝛿 ′ ), the result follows from the hypothesis. If the assertion would be false, there would be a 𝑡 0 > 0 such that 𝑥 (𝑡 0 ) = 𝑦 (𝑡 0 ). However because 𝑘 is assumed to be monotone,

𝑦 (𝑡 0 ) = 𝐶 1 + ∫ 𝑡 0 0 𝑘 (𝑦 (𝜏))d𝜏 ≤ 𝐶 1 + ∫ 𝑡 0 0 𝑘 (𝑥 (𝜏))d𝜏 < 𝑥 (𝑡 0 ).
The result now follows. □

THE (𝜆, 𝛼)-MEDIAL AXIS

In this section, we define the (𝜆, 𝛼)-medial axis and prove its stability with respect to both 𝜆 and 𝛼.

The definition

It is easy to check that the subset of ax(𝐾) that lies at distance greater than 𝛼 from 𝐾 coincides with the medial axis ax(𝐾 ⊕𝛼 ) of the 𝛼-offset of 𝐾, ax(𝐾 ⊕𝛼 ) = {𝑥 ∈ ax(𝐾) | 𝑅 𝐾 (𝑥) > 𝛼 }.

Moreover, we observe that

𝑅 𝐾 (𝑥) > 𝛼 ⇒ 𝑅 𝐾 ⊕𝛼 (𝑥) = 𝑑 𝑥, 𝐾 ⊕𝛼 = 𝑑 (𝑥, 𝐾) -𝛼 = 𝑅 𝐾 (𝑥) -𝛼 . (24)
We further note that when 𝑦 ∈ Θ 𝐾 (𝑥) one has ∥𝑦 -𝑥 ∥ = 𝑅 𝐾 (𝑥), by definition of Θ 𝐾 , see [START_REF] Attali | Computing and simplifying 2D and 3D continuous skeletons[END_REF]. Using these two observation and the definition of Θ 𝐾 we see that Θ 𝐾 (𝑥) and Θ 𝐾 ⊕𝛼 are related as follows,

𝑦 ∈ Θ 𝐾 (𝑥) ⇐⇒ 𝑥 + 𝑅 𝐾 ⊕𝛼 (𝑥) 𝑦 -𝑥 𝑅 𝐾 (𝑥) ∈ Θ 𝐾 ⊕𝛼 (𝑥),
assuming that 𝑅 𝐾 (𝑥) > 𝛼. So that, under the same condition,

(Θ 𝐾 ⊕𝛼 (𝑥) -𝑥) = 𝑅 𝐾 ⊕𝛼 (𝑥) 𝑅 𝐾 (𝑥) (Θ 𝐾 (𝑥) -𝑥) , (25)
which yields

F 𝐾 ⊕𝛼 (𝑥) = radius (Θ 𝐾 ⊕𝛼 (𝑥)) = 𝑅 𝐾 ⊕𝛼 (𝑥) 𝑅 𝐾 (𝑥) radius (Θ 𝐾 (𝑥)) , (26)
and thus

center (Θ 𝐾 ⊕𝛼 (𝑥)) -𝑥 = 𝑅 𝐾 ⊕𝛼 (𝑥) 𝑅 𝐾 (𝑥) (center (Θ 𝐾 ) -𝑥) .
Thanks to the definitions ( 9) and ( 10), we find that

𝑅 𝐾 (𝑥) > 𝛼 ⇒ ∇ 𝐾 ⊕𝛼 (𝑥) = ∇ 𝐾 (𝑥),
which in turn implies that the flows Φ 𝐾 and Φ 𝐾 ⊕𝛼 coincide in 𝐾 ⊕𝛼 𝑐 .

x

center(Θ K⊕α (x)) R K ⊕α (x) Θ K ⊕α (x) ∇ K (x) K ⊕α = ∇ K⊕α (x)
1

Figure 8: Pictorial overview of the definitions and notation.

The set 𝐾 ⊕𝛼 is indicated in grey.

We introduce the map

F 𝛼 𝐾 : 𝐾 ⊕𝛼 𝑐 → R ≥0 as F 𝛼 𝐾 = def. F 𝐾 ⊕𝛼 . (27)
Therefore ( 9), ( 24) , ( 25) and [START_REF] Edalat | A computational model for metric spaces[END_REF] give us that for 𝑥 ∈ 𝐾 ⊕𝛼 𝑐 , that is 𝑅 𝐾 (𝑥) > 𝛼, one has,

F 𝛼 𝐾 (𝑥) = 𝑅 𝐾 (𝑥) -𝛼 𝑅 𝐾 (𝑥) F 𝐾 (𝑥). (28)
The (𝜆, 𝛼)-medial axis of 𝐾, denoted ax 𝛼 𝜆 (𝐾) is the 𝜆-medial axis of the 𝛼-offset of 𝐾

ax 𝛼 𝜆 (𝐾) = def.
ax 𝜆 (𝐾 ⊕𝛼 )

= {𝑥 ∈ R 𝑛 | F 𝛼 𝐾 (𝑥) ≥ 𝜆}.
(by ( 27))

We note that Lemma 8.8 extends to (𝜆, 𝛼)-medial axis of 𝐾 which is therefore compact as well. Since, for 𝑟 ≥ 𝛼, the map 𝑟 ↦ → 𝑟 -𝛼 𝑟 is increasing, we get from (15), Lemma 8.4, and (28) that

𝑡 ↦ → F 𝛼 𝐾 (Φ 𝐾 (𝑡, 𝑥)) is not decreasing. ( 30
)
In fact, when 𝛼 > 0, 𝑡 ↦ → 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) is strictly increasing as long as ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) ∥ > 0, moreover the map 𝑡 ↦ → F 𝛼 𝐾 (Φ 𝐾 (𝑡, 𝑥)) is strictly increasing, which will be quantified in [START_REF] Mather | Distance from a submanifold in Euclidean space[END_REF] below.

The monotonicity in [START_REF] Giesen | The Scale Axis Transform[END_REF], together with the definition of ax 𝛼 𝜆 (𝐾), implies that ax 𝛼 𝜆 (𝐾) is mapped to itself under the action of the flow:

∀𝑡 ≥ 0, Φ 𝐾 (𝑡, ax 𝛼 𝜆 (𝐾)) ⊂ ax 𝛼 𝜆 (𝐾). (31)
Observe that for 𝜆 > 𝛼 one has

𝑥 ∈ ax 𝜆 (𝐾) ⇒ 𝑅 𝐾 (𝑥) ≥ F 𝐾 (𝑥) ≥ 𝜆. (32)
So if 𝑥 ∈ ax 𝜆 (𝐾), we get from (28) that

F 𝛼 𝐾 (𝑥) = 𝑅 𝐾 (𝑥) -𝛼 𝑅 𝐾 (𝑥) F 𝐾 (𝑥) ≥ 𝜆 -𝛼 𝜆 F 𝐾 (𝑥).
So that,

𝑥 ∈ ax 𝜆 (𝐾) ⇒ F 𝐾 (𝑥) ≥ 𝜆 ⇒ F 𝛼 𝐾 (𝑥) ≥ 𝜆 -𝛼 𝜆 𝜆 = 𝜆 -𝛼 ⇒ 𝑥 ∈ ax 𝛼 𝜆-𝛼 (𝐾).
This in turn implies that if 𝜆 > 𝛼, one has,

ax 𝜆 (𝐾) ⊂ ax 𝛼 𝜆-𝛼 (𝐾) ⊂ ax 𝜆-𝛼 (𝐾) (33) ax 𝛼 𝜆 (𝐾) ⊂ ax 𝜆 (𝐾) ⊂ ax 𝛼 𝜆-𝛼 (𝐾), (34)
and for any 𝑐 such that 0 < 𝑐 < 1 one has:

𝜆>0 0<𝛼 <𝜆 ax 𝛼 𝜆 (𝐾) = 𝜆>0 ax 𝑐𝜆 𝜆 (𝐾) = ax(𝐾). (35)
It follows from ( 28) and ( 29) that (𝜆, 𝛼) ↦ → ax 𝛼 𝜆 (𝐾) is decreasing for inclusion order:

𝜆 1 ≤ 𝜆 2 , 𝛼 1 ≤ 𝛼 2 ⇒ ax 𝛼 2 𝜆 2 (𝐾) ⊂ ax 𝛼 1 𝜆 1 (𝐾). ( 36
)

The (𝜆, 𝛼)-medial axis is Hausdorff-stable under 𝜆 perturbation

The purpose of this section is to show that the (𝜆, 𝛼)-medial axis does not suffer much from instabilities. In this subsection we treat the stability with respect to 𝜆 (Lemma 9.4 ), the following subsection is dedicated to the stability with respect to 𝛼 (Lemma 9.5).

We start with introducing the (𝛼, 𝜇)-reach.

Definition 9.1. For 𝜇 ∈ (0, 1] and 𝛼 ≥ 0, the (𝛼, 𝜇)-reach of 𝐾, denoted by 𝑟 𝛼 𝜇 (𝐾), is defined as:

𝑟 𝛼 𝜇 (𝐾) = def.
inf {𝑡 > 𝛼, 𝜒 𝐾 (𝑡) < 𝜇} = 𝛼 + 𝑟 𝜇 (𝐾 ⊕𝛼 ).

We need an easy lemma that gives a lower bound on the norm of ∥∇ 𝐾 (𝑥)∥ for 𝑥 ∈ 𝐾 ⊕𝛼 ′ 𝑐 \ ax 𝛼 𝜆 , for 0 < 𝛼 ′ ≤ 𝛼. To be able to state the result we define,

μ𝛼,𝛼 ′ 𝜇,𝜆 (𝐾) = def. min 𝜇, 1 - 𝜆 𝑟 𝛼 ′ 𝜇 (𝐾) -𝛼 2 . ( 37
)
Lemma 9.2. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼, 𝜆 > 0, 𝜇 ∈ (0, 1] and 𝛼 ′ such that 0 < 𝛼 ′ ≤ 𝛼 and

𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆. For any 𝑥 ∈ 𝐾 ⊕𝛼 ′ 𝑐 \ ax 𝛼 𝜆 , one has ∥∇ 𝐾 (𝑥)∥ ≥ μ,
where μ = μ𝛼,𝛼 ′ 𝜇,𝜆 (𝐾) > 0.

Proof. Because the lower bound μ is defined as a minimum over two values we distinguish two cases:

• If 𝑅 𝐾 (𝑥) < 𝑟 𝛼 ′ 𝜇 (𝐾) then by definition of 𝑟 𝛼 ′ 𝜇 one has ∥∇ 𝐾 (𝑥) ∥ ≥ 𝜇.

𝑅 𝐾 ⊕𝛼 (𝑥) 2 > 1 - 𝜆 𝑟 𝛼 ′ 𝜇 (𝐾) -𝛼 2 > 0.
So that in both cases, we get:

∥∇ 𝐾 (𝑥) ∥ ≥ μ𝛼,𝛼 ′ 𝜇,𝜆 (𝐾) > 0. (38)

□

As observed in [START_REF] Chazal | The 𝜆-medial axis[END_REF], the 𝜆-medial axis seen as a function 𝜆 ↦ → ax 𝜆 (𝐾) is not continuous: ax 𝜆 (𝐾) may "increase" abruptly at some "singular" values of 𝜆, even when 𝜆 is small with respect to wfs(𝐾). This is illustrated in Figures 9 and10. This is related to the fact that, for 𝑥 ∈ ax 𝜆 (𝐾), the map 𝑡 ↦ → F 𝐾 (Φ 𝐾 (𝑡, 𝑥)) may remain constant on some intervals. In contrast, for 𝛼 > 0, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is continuous with respect to the Hausdorff distance, as long as 𝛼 + 𝜆 < wfs(𝐾), or, more generally, as long as 𝛼 + 𝜆 < 𝑟 𝛼 𝜇 (𝐾) for some 𝜇 > 0. The continuity follows from the fact that the rate of increase of the map 𝑡 ↦ → F 𝛼 𝐾 (Φ 𝐾 (𝑡, 𝑥)) is lower bounded as soon as F 𝛼 𝐾 (𝑥) > 0. More precisely, we have:

Proof. For 𝑟 ≥ 𝛼 the map 𝑡 ↦ → 𝑟 -𝛼 𝑟 is increasing, this together with (15), Lemma 8.4 and (28) yields

F 𝛼 𝐾 (Φ 𝐾 (𝑡, 𝑥)) ≥ 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) -𝛼 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) F 𝐾 (𝑥). (41)
Observe that, using [START_REF] Martin R Bridson | Metric spaces of non-positive curvature[END_REF]

𝑡 ∈ [0,𝑇 ] ⇒ 𝑑 𝑑𝑡 + 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) -𝛼 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) > 𝛼 μ2 𝑅 2 max . (43)
This, thanks to Theorem 8.10, leads us to the following bound,

F 𝛼 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) -F 𝛼 𝐾 (𝑥) ≥ F 𝐾 (𝑥) 𝑅 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) -𝛼 𝑅 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) - 𝑅 𝐾 (𝑥) -𝛼 𝑅 𝐾 (𝑥)
(by ( 41))

= F 𝐾 (𝑥)

∫ 𝑇 0 𝑑 𝑑𝑡 + 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) -𝛼 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) 𝑑𝑡 > F 𝐾 (𝑥)𝑇 𝛼 μ2 𝑅 2 max .
(by ( 43))

Because 𝑥 ∈ ax 𝛼 𝜆 (𝐾), F 𝛼 𝐾 (𝑥) ≥ 𝜆, and (34) we find that 𝑥 ∈ ax 𝜆 (𝐾). The fact that 𝑥 ∈ ax 𝜆 (𝐾) in turn implies that F 𝐾 (𝑥) ≥ 𝜆. This then yields,

F 𝛼 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) > 𝜆 + 𝜆𝛼 μ2 𝑅 2 max 𝑇 .
We have shown that: Proof. From [START_REF] Foskey | Efficient computation of a simplified medial axis[END_REF] we conclude that,

𝑥 ∈
𝛿 ≥ 0 ⇒ ∀𝑥 ∈ 𝐾 ⊕𝛼+𝛿 𝑐 , F 𝛼 𝐾 (𝑥) ≥ F 𝛼+𝛿 𝐾 (𝑥).
It follows that

𝛿 ≥ 0 ⇒ ax 𝛼+𝛿 𝜆 (𝐾) ⊂ ax 𝛼 𝜆 (𝐾). (45)
Let us assume that for some 𝜇 > 0 one has 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝛿 + 𝜆 and take 𝑥 ∈ ax 𝛼 𝜆 (𝐾). Using Lemma 9.2, we see that

Φ 𝐾 (𝑡, 𝑥) ∉ ax 𝛼+𝛿 𝜆 (𝐾) ⇒ ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) ∥ > μ > 0, (46)
where μ = μ𝛼+𝛿,𝛼 𝜇,𝜆 (𝐾) > 0. It then follows from (15) that,

𝑅 𝐾 Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, 𝑥 = ∫ 𝑅max 𝛼 μ2 𝛿 0 𝑑 𝑑𝑡 ′+ 𝑅 𝐾 (Φ 𝐾 (𝑡 ′ , 𝑥))d𝑡 ′ + 𝑅 𝐾 (𝑥) = ∫ 𝑅max 𝛼 μ2 𝛿 0 ∇ 𝐾 Φ 𝐾 (𝑡 ′ , 𝑥) 2 d𝑡 ′ + 𝑅 𝐾 (𝑥) > 𝑅 𝐾 (𝑥) + 𝑅 max 𝛼 𝛿 (by (46)) ≥ 𝑅 𝐾 (𝑥) 𝛼 + 𝛿 𝛼 .
Using (28), we see

F 𝛼+𝛿 𝐾 Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, 𝑥 = 𝑅 𝐾 Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, 𝑥 -(𝛼 + 𝛿) 𝑅 𝐾 Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, 𝑥 F 𝐾 Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, 𝑥 > 𝑅 𝐾 (𝑥) 𝛼+𝛿 𝛼 -(𝛼 + 𝛿) 𝑅 𝐾 (𝑥) 𝛼+𝛿 𝛼 F 𝐾 (𝑥) = 𝑅 𝐾 (𝑥) -𝛼 𝑅 𝐾 (𝑥) F 𝐾 (𝑥) = F 𝛼 𝐾 (𝑥) (by definition) ≥ 𝜆, (because 𝑥 ∈ ax 𝛼 𝜆 )
where in the second line we used that for 𝑟 ≥ 𝛼 + 𝛿, the map 𝑟 ↦ →

𝑟 -(𝛼+𝛿) 𝑟

is increasing, as well as the previous bound and Lemma 8.4.

With this we have shown that

𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝛿 + 𝜆 ⇒ Φ 𝐾 𝑅 max 𝛼 μ2 𝛿, ax 𝛼 𝜆 ⊂ ax 𝛼+𝛿 𝜆 (𝐾). (47)
As for Lemma 9.4, this together with ( 31) and ( 45) completes the proof of the lemma. □

9.4 The (𝜆, 𝛼)-medial axis has the right homotopy type and a finite geodesic diameter

In this section, we recover that the (𝜆, 𝛼)-medial axis preserves the homotopy type, as for the usual medial axis [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]. We then prove that there exists a path of finite length between any two points in the (𝜆, 𝛼)-medial axis, that is it has a finite geodesic diameter. Both results are again based on manipulations of the flow Φ 𝐾 .

The next lemma gives an upper bound on the time needed for the flow Φ 𝐾 to map 𝐾 𝑐 inside ax 𝛼 𝜆 (𝐾). It is instrumental for characterizing the homotopy type of ax 𝛼 𝜆 (𝐾) (Theorem 9.7) and establishing that it has finite geodesic diameter (Theorem 9.12). Lemma 9.6. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼 ≥ 0, 𝜆 > 0, 𝜇 ∈ (0, 1] and 𝛼 ′ such that 0 < 𝛼 ′ ≤ 𝛼

and 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆. Then, Φ 𝐾 𝑅 max μ2 , 𝐾 ⊕𝛼 ′ 𝑐 ⊂ ax 𝛼 𝜆 (𝐾), where 𝑅 max = 𝑅 max (𝐾) < ∞ and μ = μ𝛼,𝛼 ′ 𝜇,𝜆 > 0.
Proof. Consider 𝑥 ∈ 𝐾 ⊕𝛼 ′ 𝑐 . Using [START_REF] Grzegorczyk | Computable functionals[END_REF]

⇒ 𝑅 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) = ∫ 𝑇 0 𝑑 𝑑𝑡 + 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥))d𝑡 + 𝑅 𝐾 (Φ 𝐾 (0, 𝑥)) > 𝑇 μ2 . Since 𝑅 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) ≤ 𝑅 max one gets, Φ 𝐾 (𝑇 , 𝑥) ∉ ax 𝛼 𝜆 (𝐾) ⇒ 𝑇 μ2 < 𝑅 max ⇒ 𝑇 < 𝑅 max μ2 .
The contraposition gives,

Φ 𝐾 𝑅 max μ2 , 𝑥 ∈ ax 𝛼 𝜆 (𝐾). □
We now define the map Pushing a path 𝛾 along the flow Φ, while keeping its endpoints fixed, will be instrumental in several subsequent proofs. We introduce therefore a specific notation for such pushed paths. Definition 9.8 (Pushed paths). Let 𝐾 ⊂ R 𝑛 be a closed set, 𝛾 : [0, 1] → 𝐾 𝑐 a rectifiable path and 𝑇 ≥ 0. The path 𝛾 pushed along a time 𝑇 by the flow Φ 𝐾 with fixed end points, denoted 𝛾 [𝑇 ] 𝐾 is the path 𝛾 [𝑇 ] 𝐾 : [0, 1] → 𝐾 𝑐 from 𝛾 (0) to 𝛾 (1) defined by:

𝐻 : [0, 1] × 𝐾 ⊕𝛼 ′ 𝑐 → 𝐾 ⊕𝛼 ′ 𝑐 (𝑡, 𝑥) ↦ → Φ 𝐾 𝑅 max μ2 𝑡, 𝑥 = 𝐻 (𝑡,
𝛾 [𝑇 ] 𝐾 (𝑡) =          Φ 𝐾 (3𝑡𝑇 , 𝛾 (0)) if 𝑡 ∈ [0, 1/3] Φ 𝐾 (𝑇 , 𝛾 (3𝑡 -1)) if 𝑡 ∈ [1/3, 2/3] Φ 𝐾 ((3(1 -𝑡)𝑇 , 𝛾 (1)) if 𝑡 ∈ [2/3, 1].
The next simple lemma says that 𝛾 [𝑇 ] 𝐾 (𝑡) is rectifiable and allows to upper bound path lengths in several subsequent proofs (Theorems 9.12 and 11.1, Lemmas 9.14 and 9.15 ). Lemma 9.9. Let 𝐾 ⊂ R 𝑛 be a closed set and 𝛼 > 0. Let 𝛾 : [0, 1] → 𝐾 ⊕𝛼 𝑐 be a rectifiable path with length 𝐿(𝛾) and 𝑇 ≥ 0. 𝛾 [𝑇 ] 𝐾 is rectifiable and has length 𝐿 𝛾 [𝑇 ] 𝐾 upper bounded by:

𝐿 𝛾 [𝑇 ] 𝐾 ≤ 2𝑇 + 𝐿(𝛾)𝑒 𝑇 𝛼 .
Proof. Since the norm of ∇ 𝐾 (𝑥) is upper bounded by 1, 𝛾 [𝑇 ] 𝐾 is 3-Lipschitz on the first and third intervals [0, 1/3] and [2/3, 1] so that the length of each of these parts is upper bounded by 𝑇 .

Because im(𝛾) is included in 𝐾 ⊕𝛼 𝑐 , the length of 𝛾 [𝑇 ] 𝐾 ([1/3, 2/3]) is bounded by

𝐿(𝛾)𝑒 𝑇 𝛼 .
This follows, because ( 16) can be applied to arbitrary small subdivisions of 𝛾, the bound on the expansion factor extends to the length of the curve through the definition of the length of rectifiable curves.

□

The next theorem shows that connected components of (𝜆, 𝛼)medial axes have finite geodesic diameter. In particular, geodesic distances inside connected components of (𝜆, 𝛼)-medial axes are finite, and are realized by minimal paths.

Before we can go into the precise statement we need to introduce some notation. For a Borel set 𝑋 ⊂ R 𝑛 we denote by Vol(𝑋 ) its 𝑛-Lebesgue measure, or volume. We write 𝑉 𝑛 = Vol(B 𝑛 (0, 1)) for the volume of the unit 𝑛-ball, 𝑉 𝑛 = 𝜋 . For this reason, the next statements related to geodesic diameters and Gromov-Hausdorff distance assumes 𝐾 ⊕𝛼 𝑐 connected without real loss of generality.

While any connected open subset of R 𝑛 is path-wise connected [START_REF] Wilson | Introduction to metric and topological spaces[END_REF]Proposition 12.25], some connected open bounded subset may not have a finite geodesic diameter. We'll illustrate this in the following example. Let

𝑆 = (𝑥, 𝑦) ∈ R 2 0 < 𝑥 < 1, - 1 2 + sin 1 𝑥 < 𝑦 < 1 2 + sin 1 𝑥 Observe that 𝑆 is indeed a connected,
𝑑 ((𝑥 1 , 𝑦 1 , 𝑧 1 ), (𝑥 2 , 𝑦 2 , 𝑧 2 )) ≤ 𝑑 ((𝑥 1 , 𝑦 1 ), (𝑥 2 , 𝑦 2 )) + 2ℎ.
Here we wrote (𝑥 1 , 𝑦 1 , 𝑧 1 ), (𝑥 2 , 𝑦 2 , 𝑧 2 ) for elements of 𝐾 ⊕𝛼 𝑐 and (𝑥 1 , 𝑦 1 ), (𝑥 2 , 𝑦 2 ) for the elements of 𝑆 with the same first two coordinates. Conversely, 𝑑 ((𝑥 1 , 𝑦 1 ), (𝑥 2 , 𝑦 2 )) ≤ 𝑑 ((𝑥 1 , 𝑦 1 , 𝑧 1 ), (𝑥 2 , 𝑦 2 , 𝑧 2 )) because for any rectifiable curve 𝛾 (𝑡) ⊂ R 3 we have 𝐿(𝜋 R 2 (𝛾 (𝑡))) ≤ 𝐿(𝛾 (𝑡)), where 𝜋 R 2 denotes the projection onto R 2 . It follows from the bound 𝑑 𝐺𝐻 ( 𝐾 ⊕𝛼 𝑐 , 𝑆) ≤ 2ℎ that 𝐾 ⊕𝛼 𝑐 also has infinite geodesic diameter. So to be the complement of an offset does not imply finite geodesic diameter either.

However, we have the following: Lemma 9.11. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded, open set 𝐾 𝑐 . Assume there are 𝜇 > 0 and 𝛼 > 𝛼 ′ > 0 such that 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼. Then, if 𝐾 ⊕𝛼 𝑐 is connected it has finite geodesic diameter. In particular, if for some 𝑧 ∈ R 𝑛 and 𝑅 bound > 0, one has 𝐾 𝑐 ⊂ B(𝑧, 𝑅 bound ), then:

GeoDiameter 𝐾 ⊕𝛼 𝑐 ≤2 𝛼 -𝛼 ′ 𝜇 + 2 4𝑅 bound 𝛼 -𝛼 ′ 𝑛 + 1 (𝛼 -𝛼 ′ )𝑒 𝛼 -𝛼 ′ 𝛼 𝜇 .
This diameter is bounded by constructing a very dense graph inside the set 𝐾 ⊕𝛼 ′ 𝑐 and bounding the distance between any two points in the graph. The result then follows by pushing this path inside 𝐾 ⊕𝛼 𝑐 .

of Lemma 9.11. Since 𝐾 ⊕𝛼 𝑐 is compact, we can cover it by a

finite number of open balls B • (𝑦 𝑖 , 𝛼-𝛼 ′ 2 )

𝑖 ∈𝐼 0

, where 𝐼 0 is a finite set and

𝑦 𝑖 ∈ 𝐾 ⊕𝛼 𝑐 . It is possible to extract an 𝜀-net {𝑦 𝑖 , 𝑖 ∈ 𝐼 } from {𝑦 𝑖 , 𝑖 ∈ 𝐼 0 }, that is 𝐼 ⊂ 𝐼 0 and 𝐾 ⊕𝛼 𝑐 ⊂ 𝑖 ∈𝐼 B • 𝑦 𝑖 , 𝛼 -𝛼 ′ ⊂ 𝐾 ⊕𝛼 ′ 𝑐 , (48)
with

𝑖, 𝑗 ∈ 𝐼 and 𝑖 ≠ 𝑗 ⇒ B 𝑦 𝑖 , 𝛼 -𝛼 ′ 4 ∩ B 𝑦 𝑖 , 𝛼 -𝛼 ′ 4 = ∅. ( 49
)
Let us denote the cardinality of 𝐼 by 𝑁 . Since by [START_REF] Wilson | Introduction to metric and topological spaces[END_REF] the balls

B 𝑦 𝑖 , 𝛼-𝛼 ′ 4 are disjoint and ∪ 𝑖 ∈𝐼 B 𝑦 𝑖 , 𝛼-𝛼 ′ 4 ⊂ 𝐾 𝑐 ⊂ B(𝑧, 𝑅 bound ) one has 𝑁 ≤ Vol(B(𝑧, 𝑅 bound )) Vol B 0, 𝛼-𝛼 ′ 4 ≤ 4𝑅 bound 𝛼 -𝛼 ′ 𝑛 . (50)
Let 𝐺 be the graph with one vertex for each 𝑦 𝑖 ∈ {1, . . . , 𝑁 } and one edge for each pair (𝑖, 𝑗) such that B • (𝑦 𝑖 , 𝛼-𝛼 ′ )∩B • (𝑦 𝑗 , 𝛼-𝛼 ′ ) ≠ ∅. This graph is connected as otherwise, from [START_REF] Shaked | Pruning Medial Axes[END_REF], 𝐾 ⊕𝛼 𝑐 would be the disjoint union of two non-empty disjoint open sets, which would contradict its connectedness.

Consider 𝑥, 𝑥 ′ ∈ 𝐾 ⊕𝛼 𝑐 and let 𝑘, 𝑘 ′ be such that 𝑥 ∈ B • (𝑦 𝑘 , 𝛼 -𝛼 ′ ) and 𝑥 ′ ∈ B • (𝑦 𝑘 ′ , 𝛼 -𝛼 ′ ). We define a piecewise linear path P from 𝑥 to 𝑥 ′ as follows. First let 𝑦 𝑘 = 𝑦 𝑖 0 . . . 𝑦 𝑖 𝑀 = 𝑦 𝑘 ′ a shortest path between 𝑦 𝑘 and 𝑦 𝑘 ′ in the graph 𝐺. We define the piecewise linear path P in 𝐾 ⊕𝛼 ′ 𝑐 as the concatenation of the segments

[𝑥𝑦 𝑖 0 ], [𝑦 𝑖 0 𝑦 𝑖 1 ], . . . , [𝑦 𝑖 𝑀-1 𝑦 𝑖 𝑀 ], [𝑦 𝑖 𝑀 , 𝑥 ′ ].
The length of 𝑃 is then lower bounded:

𝐿(P) ≤ 2(𝑁 +1) (𝛼 -𝛼 ′ ). By definition of 𝑟 𝛼 ′ 𝜇 (𝐾), since 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 we have that ∥∇ 𝐾 (𝑥) ∥ ≥ 𝜇 for 𝑥 ∈ 𝐾 ⊕𝛼 ′ 𝑐 \ 𝐾 ⊕𝛼 𝑐 , so that 𝑃 𝛼 -𝛼 ′ 𝜇 𝐾 ⊂ 𝐾 ⊕𝛼 𝑐
. Applying Lemma 9.9 we get:

𝐿 𝑃 𝛼 -𝛼 ′ 𝜇 𝐾 ≤ 2 𝛼 -𝛼 ′ 𝜇 + 𝐿(𝑃)𝑒 𝛼 -𝛼 ′ 𝛼 𝜇 .
□ Theorem 9.12. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded, open set 𝐾 𝑐 and 𝛼, 𝜆 > 0 such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆 and assume 𝐾 ⊕𝛼 𝑐 to be connected with finite geodesic diameter:

GeoDiameter 𝐾 ⊕𝛼 𝑐 < ∞.
Then ax 𝛼 𝜆 (𝐾) is a geodesic space with finite geodesic diameter given by (51) below. More precisely, if 𝑥, 𝑥 ′ ∈ ax 𝛼 𝜆 (𝐾), then there exists a path 𝛾 : [0, 1] → ax 𝛼 𝜆 (𝐾) of minimal length such that 𝛾 (0) = 𝑥 and 𝛾 (1) = 𝑥 ′ . This path satisfies,

length(𝛾) ≤ GeoDiameter(ax 𝛼 𝜆 (𝐾)) ≤ 2 𝑅 max μ2 + GeoDiameter 𝐾 ⊕𝛼 𝑐 𝑒 𝑅max 𝛼 μ2 , (51)
where

𝑅 max = 𝑅 max (𝐾), μ = μ𝛼, 𝛼 2
𝜇,𝜆 . The length length(𝛾) is the geodesic distance between 𝑥 and 𝑥 ′ in ax 𝛼 𝜆 (𝐾). The proof follows by pushing paths into the medial axis, using Lemma 9.9. 𝐾 ( [1/3, 2/3]) also lies in ax 𝛼 𝜆 (𝐾). This upper bound (52) on the length is independent of 𝑥, 𝑥 ′ ∈ ax 𝛼 𝜆 (𝐾) and it therefore gives an upper bound on the geodesic diameter of ax 𝛼 𝜆 (𝐾). It is known that if a finite length path exists between two points in a compact subset of Euclidean space, then there exists a path of minimal length, see the second paragraph of Part III, Section 1: Die Existenz geodätischer Bogen in metrischen Räumen, in [START_REF] Menger | Untersuchungen uber allgemeine Metrik, Vierte Untersuchungen Zur Metrik Kurven[END_REF]. □

Proof

As a consequence of Lemma 9.11 and Theorem 9.12 we get: Corollary 9.13. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded, open set 𝐾 𝑐 , 𝛼 > 𝛼 ′ > 0 and 𝜆 > 0 such that 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆 and assume 𝐾 ⊕𝛼 𝑐 to be connected.

Then ax 𝛼 𝜆 (𝐾) is a geodesic space with finite geodesic diameter.

The (𝜆, 𝛼)-medial axis is Gromov-Hausdorff-stable under 𝜆 perturbation

Thanks to Theorem 9.12, ax 𝛼 𝜆 (𝐾) is a geodesic space with finite length inside connected components. Equipped with this geodesic distance ax 𝛼 𝜆 (𝐾) is a metric space which is stable under 𝜆 perturbation in the following sense: Lemma 9.14. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded, open set 𝐾 𝑐 and 𝛼, 𝛿, 𝜆 > 0, 𝜇 ∈ (0, 1] such that, for some 𝛼 ′ < 𝛼 one has 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆 + 𝛿 and 𝐾 ⊕𝛼 𝑐 is connected. Then, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is locally Lipschitz for the Gromov-Hausdorff distance with respect to the intrinsic metric.

More precisely, one has

𝑑 GH (ax 𝛼 𝜆+𝛿 (𝐾), ax 𝛼 𝜆 (𝐾)) ≤ 2𝑇 + 𝐷 𝑒 𝑇 𝛼 -1 = 𝑂 (𝛿) , with 𝑇 = 𝑅 2 max 𝛼𝜆μ 2 𝛿.
and 𝐷 < ∞ is the geodesic diameter of ax 𝛼 𝜆 (𝐾). The core of the proof consists of pushing the geodesics in ax 𝛼 𝜆 into ax 𝛼 𝜆+𝛿 , which is again achieved by the flow. The other properties we need to verify to establish a bound on the Gromov-Hausdorff distance are relatively straightforward.

Proof. The value of the geodesic diameter 𝐷 is given by Theorem 9.12. In order to upper bound the Gromov-Hausdorff distance between ax 𝛼 𝜆+𝛿 (𝐾) and ax 𝛼 𝜆 (𝐾) we use Definition 8.7. Consider the relation R ⊂ ax 𝛼 𝜆 (𝐾) × ax 𝛼 𝜆+𝛿 (𝐾) defined by: R =

(𝑥 1 , 𝑥 2 ) ∈ ax 𝛼 𝜆 (𝐾) × ax 𝛼 𝜆+𝛿 (𝐾), ∃𝑡 ∈ [0,𝑇 ], 𝑥 2 = Φ 𝐾 (𝑡, 𝑥 1 )
,

where 𝑇 = 𝑅 2 max 𝛼𝜆 μ2 𝛿.
We have to check the two conditions of Definition 8.7. Recall that, by Lemma 9.3, one has

Φ 𝐾 𝑇 , ax 𝛼 𝜆 (𝐾) ⊂ ax 𝛼 𝜆+𝛿 (𝐾) ⊂ ax 𝛼 𝜆 (𝐾).
Condition (1): R is surjective. This condition follows because, if 𝑥 1 ∈ ax 𝛼 𝜆 (𝐾) then Φ 𝐾 (𝑇 , 𝑥 1 ) ∈ ax 𝛼 𝜆+𝛿 (𝐾), thanks to Lemma 9.3. This is in turn equivalent to

(𝑥 1 , Φ 𝐾 (𝑇 , 𝑥 1 )) ∈ R. Conversely, if 𝑥 2 ∈ ax 𝛼 𝜆+𝛿 (𝐾), then 𝑥 2 ∈ ax 𝛼 𝜆 (𝐾) and (𝑥 2 , 𝑥 2 ) ∈ R since Φ 𝐾 (0, 𝑥 2 ) = 𝑥 2 .
Condition (2): The bound on the distance distortion. Consider

(𝑥 1 , 𝑥 2 ), (𝑥 ′ 1 , 𝑥 ′ 2 ) ∈ R, with 𝑥 2 = Φ 𝐾 (𝑡, 𝑥 1 ) and 𝑥 ′ 2 = Φ 𝐾 (𝑡 ′ , 𝑥 ′ 1 ) with 𝑡, 𝑡 ′ ∈ [0,𝑇 ]. Denote
[𝑇 ] 𝐾 𝑡 3𝑇 = 𝑥 2 and 𝛾 1 [𝑇 ] 𝐾 1 -𝑡 ′ 3𝑇 = 𝑥 ′ 2 . Moreover, (30) and (39) yields 𝛾 1
[𝑇 ] 𝐾 𝑡 3𝑇 , 1 - 𝑡 ′ 3𝑇 ⊂ ax 𝛼 𝜆 (𝐾), so that 𝛾 1 [𝑇 ] 𝐾 𝑡 3𝑇 , 1 -𝑡 ′ 3𝑇
is a path from 𝑥 2 to 𝑥 ′ 2 inside ax 𝛼 𝜆+𝛿 (𝐾) and its length is therefore lower bounded by 𝑑 2 (𝑥 2 , 𝑥 ′ 2 ). It follows that

𝑑 2 (𝑥 2 , 𝑥 ′ 2 ) ≤ 𝐿 𝛾 1 [𝑇 ] 𝐾 𝑡 3𝑇 , 1 - 𝑡 ′ 3𝑇 ≤ 𝐿 𝛾 1 [𝑇 ] 𝐾 ≤ 2𝑇 + 𝑑 1 (𝑥 1 , 𝑥 ′ 1 )𝑒 𝑇 𝛼 , so that 𝑑 2 (𝑥 2 , 𝑥 ′ 2 )-𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) ≤ 2𝑇 +𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) 𝑒 𝑇 𝛼 -1 ≤ 2𝑇 +𝐷 𝑒 𝑇 𝛼 -1 . (53) Since ax 𝛼 𝜆+𝛿 (𝐾) is connected, there is a path 𝛾 2 : [0, 1] → ax 𝛼 𝜆+𝛿 (𝐾) such that 𝑑 2 (𝑥 2 , 𝑥 ′ 2 ) = 𝐿(𝛾 2 ). Consider now the path Γ : [0, 1] → ax 𝛼
𝜆 (𝐾) defined as:

Γ(𝑢) =          Φ 𝐾 (3𝑢𝑡, 𝑥 1 ) if 𝑢 ∈ [0, 1/3] 𝛾 2 (3𝑢 -1)) if 𝑢 ∈ [1/3, 2/3] Φ 𝐾 ((3(1 -𝑢)𝑡 ′ , 𝑥 ′ 1 ) if 𝑢 ∈ [2/3, 1].
Here we used that

ax 𝛼 𝜆+𝛿 (𝐾) ⊂ ax 𝛼 𝜆 for 𝑢 ∈ [1/3, 2/3]. By (30) Γ is a path from 𝑥 1 to 𝑥 ′ 1 inside ax 𝛼 𝜆 (𝐾) so that 𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) ≤ 𝐿 (Γ) ≤ 2𝑇 + 𝐿 (𝛾 2 ) = 2𝑇 + 𝑑 2 (𝑥 2 , 𝑥 ′ 2 )
and with [START_REF] Martijn Van Manen | Maxwell strata and caustics[END_REF] we get as required

𝑑 2 (𝑥 2 , 𝑥 ′ 2 ) -𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) ≤ 2𝑇 + 𝐷 𝑒 𝑇 𝛼 -1 .
Note that by Corollary 9.13 (using the assumption 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 +𝜆+𝛿) the geodesic diameter 𝐷 of ax 𝛼 𝜆 (𝐾) is finite. □ 9.6 The (𝜆, 𝛼)-medial axis is Gromov-Hausdorff-stable under 𝛼 perturbation

Using almost identical arguments as in the previous section we also get the Gromov-Hausdorff stability with respect the offset 𝛼.

Lemma 9.15. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼, 𝛿, 𝜆 > 0, 𝜇 ∈ (0, 1] such that, for some 𝛼 ′ < 𝛼 one has Proof. This is similar to Section 9.5 using (47) instead of [START_REF] Lacombe | Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles II[END_REF]. □

𝑟 𝛼 ′ 𝜇 (

HAUSDORFF STABILITY OF THE (𝜆, 𝛼)-MEDIAL AXIS UNDER HAUSDORFF PERTURBATION OF 𝐾

In this section, we prove one of the main stability theorems of this paper, namely stability in the Hausdorff sense of the (𝜆, 𝛼)medial axis under Hausdorff perturbations of 𝐾. This requires some further results on the flow that are proven in the first subsections, while the main result is proven in the final subsection. As in the previous section we use the flow to establish our main result, namely the Hausdorff stability. Intuitively this may seem straightforward, because near the medial axis the flow we follow points towards the medial axis. However, establishing that the flow is fast enough requires a number of technical estimates. Firstly we need that the distance to the closest points (𝑅 𝐾 ) increases sufficiently fast as we follow the flow. This is proven in Section 10.

A lower bound on 𝑅 𝐾 along the flow trajectories

The technical result that underpins the lemma in this section is the Volterra integral inequality, as discussed in Section 8.7.

Lemma 10.1. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 , 𝛼 ≥ 0 and 𝜆 > 0. Consider 𝑦 ∈ 𝐾 ⊕𝛼 𝑐 \ ax 𝛼 𝜆 (𝐾) and denote by 𝑠 ↦ → 𝑦 (𝑠) the trajectory of 𝑡 ↦ → Φ 𝐾 (𝑡, 𝑦), parametrized by arc length. We stress that 𝑦 (0) = 𝑦. Assume that 𝑅 𝐾 (𝑦) -𝛼 > 𝜆 and that for some 𝑆 > 0 one has 𝑦 (𝑆) ∉ ax 𝛼 𝜆 (𝐾), then

(𝑅 𝐾 (𝑦 (𝑆)) -𝛼) 2 ≥ (𝑆 0 + 𝑆) 2 + 𝜆 2 ,
where 𝑆 0 > 0 is defined as

𝑆 2 0 = (𝑅 𝐾 (𝑦) -𝛼) 2 -𝜆 2 .
Proof. We define the map 𝑅 0 : [0, 𝑆] → R as

𝑅 0 (𝑠) = √ (𝑆 0 + 𝑠) 2 + 𝜆 2 +𝛼 .
We need to prove that 𝑅 𝐾 (𝑦 (𝑠)) ≥ 𝑅 0 (𝑠), which we'll do by means of Theorem 8.12. By definition of 𝑆 0 , one has 𝑅 0 (0) = 𝑅 𝐾 (𝑦). For 𝑠 ∈ [0, 𝑆] we get

𝑑 𝑑𝑠 (𝑅 0 (𝑠) -𝛼) 2 = 2(𝑆 0 + 𝑠).
It follows that where the kernel 𝑘 is

𝑑 𝑑𝑠 𝑅 0 (𝑠) = (𝑆 0 + 𝑠) 𝑅 0 (𝑠) -𝛼 = √ (𝑅 0 (𝑠) -𝛼) 2 -𝜆 2 𝑅 0 (𝑠) -𝛼 = √ 1 - 𝜆 𝑅 0 (𝑠) -𝛼
𝑘 (𝑥) = √ 1 - 𝜆 𝑥 -𝛼 2 .
Combining [START_REF] Boissonnat | The reach of subsets of manifolds[END_REF], and [START_REF] Martin R Bridson | Metric spaces of non-positive curvature[END_REF] gives

𝑑 𝑑𝑠 + 𝑅 𝐾 (𝑦 (𝑠)) = ∥∇ 𝐾 (𝑦 (𝑠))∥ = √ 1 - F 𝛼 (𝑦 (𝑠)) 𝑅 𝐾 (𝑦 (𝑠)) -𝛼 2 ,
see also [START_REF] Chazal | The 𝜆-medial axis[END_REF]Equation (5)]. Because 𝑅 𝐾 (𝑦 (𝑠)) is Lipschitz, Theorem 8.10 yields that

𝑅 𝐾 (𝑦 (𝑠)) = 𝑅 𝐾 (𝑦) + ∫ 𝑠 0 √ 1 - F 𝛼 (𝑦 (𝜏)) 𝑅 𝐾 (𝑦 (𝜏)) -𝛼 2 d𝜏 = 𝑅 0 (0) + ∫ 𝑠 0 √ 1 - F 𝛼 (𝑦 (𝜏)) 𝑅 𝐾 (𝑦 (𝜏)) -𝛼 2 d𝜏 .
By assumption 𝑦 (𝑆) ∉ ax 𝛼 𝜆 , so [START_REF] Giesen | The Scale Axis Transform[END_REF] implies that 𝑠 ≤ 𝑆 ⇒ F 𝛼 (𝑦 (𝑠)) < 𝜆. Moreover, for sufficiently small 0 < 𝛿 ′ ≤ 𝑆 we can assume that F 𝛼 (𝑦 (𝑠)) ≤ 𝜆 ′ < 𝜆, for 𝑠 ∈ [0, 𝛿], by Lemma 8.4. This means that 𝑅 𝐾 (𝑦 (𝑠)) satisfies the following integral inequality of Volterra type,

𝑅 𝐾 (𝑦 (𝑠)) ≥ 𝑅 0 (0) + ∫ 𝑠 0 √ 1 - 𝜆 𝑅 𝐾 (𝑦 (𝜏)) -𝛼 2 d𝜏 = 𝑅 0 (0) + ∫ 𝑠 0 𝑘 (𝑅 𝐾 (𝑦 (𝜏)))d𝜏,
where the equality occurs only when 𝑠 = 0. We note that, because 𝑅 𝐾 (𝑦) -𝛼 > 𝜆 > 0 and 𝑅 𝐾 (𝑦) is monotone,

𝑑 𝑑𝑥 𝑘 (𝑥) = 𝜆 2 (𝑥 -𝛼) 3 √ 1 -𝜆 2 (𝑥-𝛼) 2 ≥ 0
on the domain and thus the kernel is monotone. Because 𝑅 𝐾 (𝑦 (𝑠)) is 1-Lipschitz in 𝑠 and we can assume that there is some 𝛿 ′ ≤ 𝛿 such that for all 𝑠 ∈ (0, 𝛿 ′ ), we have 𝑅 𝐾 (𝑦 (𝑠)) > 𝑅 0 (𝑠). In fact 𝛿 ′ is determined by the condition

√ 1 - 𝜆 ′ 𝑅 0 (0) -𝛿 ′ -𝛼 2 ≥ √ 1 - 𝜆 𝑅 0 (0) + 𝛿 ′ -𝛼 2 𝜆 ′ 𝑅 0 (0) -𝛿 ′ -𝛼 ≤ 𝜆 𝑅 0 (0) + 𝛿 ′ -𝛼 .
The result is now a direct consequence of the application of Theorem 8. Proof. Consider 𝑦 ∈ ax 𝛼 𝜆 (𝐾) ⊕𝜖 and 𝑎 ∈ ax 𝛼 𝜆 (𝐾) such that ∥𝑦 -𝑎∥ ≤ 𝜖. Denote by 𝑠 ↦ → 𝑦 (𝑠) the trajectory of 𝑡 ↦ → Φ 𝐾 (𝑡, 𝑦), parametrized by arc length, so that 𝑦 (0) = 𝑦. Let us now assume that for some 𝑠 > 0 one has 𝑦 (𝑠) ∉ ax 𝛼 𝜆-𝛿 (𝐾). Since 𝑎 ∈ ax 𝛼 𝜆 (𝐾) [START_REF] Kim | Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex[END_REF] yields that 𝑎 ∈ ax 𝜆 (𝐾). The bound (32) gives that 𝑅 𝐾 (𝑎) ≥ 𝐹 𝐾 (𝑎). This together with ( 29) and [START_REF] Foskey | Efficient computation of a simplified medial axis[END_REF] gives

𝑅 𝐾 (𝑎) -𝛼 ≥ 𝜆. ( 54
)
By the conditions of the theorem we have 𝜖 < 𝛿 and ∥𝑦 -𝑎∥ ≤ 𝜖, (54) therefore implies

𝑅 𝐾 (𝑦) -𝛼 > 𝜆 -𝛿, (55)
by the triangle inequality. This means that the condition of Lemma 10.1 are satisfied.

We can then apply Lemma 10.1 with 𝜆 replaced by 𝜆 -𝛿, which gives us

(𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≥ (𝑆 0 + 𝑠) 2 + (𝜆 -𝛿) 2 , (56)
where

𝑆 2 0 = (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝜆 -𝛿) 2 . ( 57
)
Since 𝑅 𝐾 (𝑎) -𝛼 ≥ 𝜆 there is 𝑆 𝑎 ≥ 0 such that

𝑆 2 𝑎 + 𝜆 2 = (𝑅 𝐾 (𝑎) -𝛼) 2 . ( 58
)
We recall Lemma 4.15 of [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF]. The correspondence between the notation is the following:

We pick O to be equal to 𝐾 ⊕𝛼 𝑐 , 𝑥 to be 𝑎 and 𝑦 to be 𝑦 (𝑠), then ℛ(𝑥) is 𝑅 𝐾 (𝑎) -𝛼, ℛ(𝑦) is 𝑅 𝐾 (𝑦 (𝑠)) -𝛼, and ℱ(𝑥) is F 𝛼 𝐾 (𝑎). So that the inequality of Lemma 4.15 of [START_REF] Lieutier | Any open bounded subset of R 𝑛 has the same homotopy type as its medial axis[END_REF] reads (using our notation): Because ∥𝑦 (𝑠) -𝑎∥ ≤ ∥𝑦 -𝑎∥ + ∥𝑦 (𝑠) -𝑦 ∥ ≤ 𝜖 + 𝑠, we get

(𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≤ (𝑅 𝐾 (𝑎) -𝛼) 2 + 2∥𝑦 (𝑠) -𝑎∥ √ (𝑅 𝐾 (𝑎) -𝛼) 2 -F 𝛼 𝐾 (𝑎)
(𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≤ (𝑆 𝑎 + 𝑠 + 𝜖) 2 + 𝜆 2 . ( 59
)
Combining this with (56) yields,

(𝑆 𝑎 + 𝑠 + 𝜖) 2 + 𝜆 2 ≥ (𝑆 0 + 𝑠) 2 + (𝜆 -𝛿) 2 ,
which can be rewritten as

2(𝑆 0 -𝑆 𝑎 -𝜖)𝑠 ≤ (2𝜆 -𝛿)𝛿 -𝑆 2 0 -𝑆 2 𝑎 + (2𝑆 𝑎 + 𝜖) 𝜖. (60)
To recover an upper bound on 𝑠 from (60), we need a lower bound on (𝑆 0 -𝑆 𝑎 -𝜖) and an upper bound on the right hand side of the previous inequality, that is an upper bound on (2𝜆 -𝛿)𝛿 -𝑆 2 0 -𝑆 2 𝑎 + (2𝑆 𝑎 + 𝜖) 𝜖. From ( 57) and ( 58) we get

𝑆 2 0 -𝑆 2 𝑎 = (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝜆 -𝛿) 2 -(𝑅 𝐾 (𝑎) -𝛼) 2 + 𝜆 2 = (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝑅 𝐾 (𝑎) -𝛼) 2 + (2𝜆 -𝛿)𝛿, so that, 𝑆 2 0 -𝑆 2 𝑎 -(2𝜆 -𝛿)𝛿 = (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝑅 𝐾 (𝑎) -𝛼) 2 . ( 61
)
Since |𝑅 𝐾 (𝑦) -𝑅 𝐾 (𝑎)| < 𝜖 we get,

| (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝑅 𝐾 (𝑎) -𝛼) 2 | < |𝑅 𝐾 (𝑦)+𝑅 𝐾 (𝑎)-2𝛼 | 𝜖 ≤ 2𝑅 max 𝜖,
where we used that 𝑅 𝐾 (𝑦), 𝑅 𝐾 (𝑎) ≤ 𝑅 max by definition of 𝑅 max and 𝛼 ≤ 𝑅 max . Now (61), in turn gives,

|(2𝜆 -𝛿)𝛿 -(𝑆 2 0 -𝑆 2 𝑎 )| < 2𝑅 max 𝜖 (62)
or, equivalently

(2𝜆 -𝛿)𝛿 -2𝑅 max 𝜖 < 𝑆 2 0 -𝑆 2 𝑎 < (2𝜆 -𝛿)𝛿 + 2𝑅 max 𝜖. ( 63
)
With the assumption 𝜖 < (2𝜆-𝛿)𝛿 8𝑅 max , which gives 2𝑅 max 𝜖 < 1 4 (2𝜆 -𝛿)𝛿, (63) yields,

0 < 3 4 (2𝜆 -𝛿)𝛿 < 𝑆 2 0 -𝑆 2 𝑎 < 5 4 (2𝜆 -𝛿)𝛿. (64)
This in turn implies that Remark 10.4. While we do not need it in subsequent proofs, thanks to remark 10.3, we could omit the condition 𝜖 < 2𝛼 in Lemma 10.2, so that the lemma holds as well without this condition and then also for 𝛼 = 0, that is for the 𝜆-medial axis, at the mild price of a larger constant, replacing the flow time Proof. The proof is similar to the proof of Lemma 10.2, except that now we start with a point in ax 𝛼 𝜆 (𝐾 ′ ) and flow to ax 𝛼 𝜆-𝛿 (𝐾). We consider 𝑦 ∈ ax 𝛼 𝜆 (𝐾 ′ ). Denote by 𝑠 ↦ → 𝑦 (𝑠) the trajectory of 𝑡 ↦ → Φ 𝐾 (𝑡, 𝑦), parametrized by arc length, so that 𝑦 (0) = 𝑦. Assume that for some 𝑠 > 0 one has:

𝑆 0 -𝑆 𝑎 = 𝑆 2 0 -𝑆 2 𝑎 𝑆 0 + 𝑆 𝑎 > 3
𝑦 (𝑠) ∉ ax 𝛼 𝜆-𝛿 (𝐾) Recall that 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖 implies that |𝑅 𝐾 ′ (𝑥) -𝑅 𝐾 (𝑥)| < 𝜖, (67)
for all 𝑥. Similarly to [START_REF] Wall | Geometric properties of generic differentiable manifolds[END_REF], once again has 𝑦 ∈ ax 𝛼 𝜆 (𝐾 ′ ) ⇒ 𝑅 𝐾 ′ (𝑦) -𝛼 > 𝜆 ⇒ 𝑅 𝐾 (𝑦) -𝛼 > 𝜆 -𝜖. Moreover due to the hypothesis of the lemma one has 𝜖 < 𝛿, so one sees,

𝑅 𝐾 (𝑦) -𝛼 > 𝜆 -𝛿. (55)
As in the proof of Lemma 10.2 we can apply Lemma 10.1 with 𝜆 replaced by 𝜆 -𝛿, which gives us,

(𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≥ (𝑆 0 + 𝑠) 2 + (𝜆 -𝛿) 2 , (68)
where:

𝑆 2 0 = (𝑅 𝐾 (𝑦) -𝛼) 2 -(𝜆 -𝛿) 2 . (69) Since 𝑦 ∈ ax 𝛼 𝜆 (𝐾 ′ ), 𝑅 𝐾 ′ (𝑦) -𝛼 ≥ 𝜆 and there is 𝑆 𝑦 ≥ 0 such that 𝑆 2 𝑦 = (𝑅 𝐾 ′ (𝑦) -𝛼) 2 -𝜆 2 . ( 70
)
Again following the same steps as in the proof of Lemma 10.

0 ≤(𝑆 𝑦 + 𝑠) 2 -(𝑆 0 + 𝑠) 2 + 𝜆 2 -(𝜆 -𝛿) 2 + (𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 -(𝑅 𝐾 (𝑦 (𝑠)) -𝜖 -𝛼) 2 ,
which can be rewritten (in two steps) as,

0 ≤ (𝑆 𝑦 + 𝑠) 2 -(𝑆 0 + 𝑠) 2 + (2𝜆 -𝛿) 𝛿 + (2𝑅 𝐾 (𝑦 (𝑠)) -2𝛼 -𝜖) 𝜖 2 𝑆 0 -𝑆 𝑦 𝑠 ≤ (2𝜆 -𝛿) 𝛿 -𝑆 2 0 -𝑆 2 𝑦 + 2𝑅 max 𝜖. (73)
Again as in the proof of Lemma 10.2, combining (69) and (70) gives us Remark 10.6. The previous lemma can be interpreted as a stability result with respect to the one-sided Hausdorff distance. Moreover, the lemma applies when 𝛼 = 0, in which case the statement can be compared to Theorem 3 of [START_REF] Chazal | The 𝜆-medial axis[END_REF]. Theorem 3 of [START_REF] Chazal | The 𝜆-medial axis[END_REF] says that the 𝜆-medial axis is 1 2 -Hölder stable in the following sense: If 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖, then for 𝑥 ∈ ax 𝜆 (𝐾 ′ ) there is 𝑦 ∈ 𝑎𝑥 𝜆-𝛿 (𝐾) with ∥𝑦 -𝑥 ∥ = 𝑂 (𝜖 1 2 ). In other words the one sided Hausdorff distance between ax 𝜆 (𝐾 ′ ) and ax 𝜆 (𝐾) is 𝑂 (𝜖 1 2 ). Lemma 10.5 proves the stronger linear bound ∥𝑦 -𝑥 ∥ = 𝑂 (𝜖). The effect of a translation on 𝐾 shows that one cannot expect a bound better than linear.

(2𝜆 -𝛿) 𝛿 -𝑆 2 0 -𝑆 2 𝑦 = (𝑅 𝐾 ′ (𝑦) -𝛼) 2 -(𝑅 𝐾 (𝑦) -𝛼) 2 = (𝑅 𝐾 (𝑦) + 𝑅 𝐾 ′ (𝑦) -2𝛼) |𝑅 𝐾 (𝑦) -𝑅 𝐾 ′ (𝑦)| ≤ (𝑅 𝐾 (𝑦) + 𝑅 𝐾 ′ (𝑦) -2𝛼) 𝜖 (by (67)) ≤ 2𝑅 max 𝜖, (74)
The proofs of Theorem 3 in [START_REF] Chazal | The 𝜆-medial axis[END_REF] and Lemma 10.5 are based on the same idea. However, here we get a better bound by using the lower bound on 𝑅 𝐾 (𝑦 (𝑆)) given by Lemma 10.1 which is tighter than the one used in [START_REF] Chazal | The 𝜆-medial axis[END_REF]. where we use [START_REF] Brattka | A Tutorial on Computable Analysis[END_REF] and 𝑅 max = 𝑅 max (𝐾) < ∞ and μ = μ𝛼,𝛼 𝜇,𝜆 > 0. Here we still have to choose a value of 𝛿 that minimizes the first argument of Φ 𝐾 in (78), that is,

𝛿 ↦ → 𝑅 2 max 𝛼 (𝜆 -𝛿) μ2 𝛿 + 8𝑅 2 max (2𝜆 -𝛿) 𝛿 μ 𝜖. (79)
To this end we first observe that when 𝜖 is small, the value of 𝛿 that minimizes, (79) is small. When 𝛿 is small (79) is well approximated by

𝛿 ↦ → 𝑅 2 max 𝛼𝜆μ 2 𝛿 + 4𝑅 2 max 𝜆𝛿 μ 𝜖. (80)
The value of 𝛿 that minimizes (80) is

𝛿 = 2 √ 𝛼 μ𝜖. (81)
We now substitute (81) in ( 79). If we also observe that if 𝜖 < 𝜆 2 16𝛼 μ , (81) gives 𝛿 < 𝜆/2 and thus 2𝜆 -𝛿 > 3/2𝜆 and 𝜆 -𝛿 > 1/2𝜆 we find the following upper bound

𝑅 2 max 𝛼 (𝜆 -𝛿) μ2 𝛿 + 8𝑅 2 max (2𝜆 -𝛿) 𝛿 μ 𝜖 < 22 3 𝑅 2 max 𝛼 1 2 μ 3 2 𝜆 𝜖 1 2 .

□

Remark 10.8. The symmetric condition 𝑟 𝛼 𝜇 (𝐾), 𝑟 𝛼 𝜇 (𝐾 ′ ) > 𝛼 + 𝜆 can be replaced by a condition on 𝐾 only. More precisely, in the limit where some 𝛿 tends to zero as 𝑑 𝐻 (𝐾, 𝐾 ′ ) → 0 we have that 𝑟 𝛼-𝛿 𝜇 (𝐾) > 𝛼 + 𝜆 + 𝛿 implies 𝑟 𝛼 𝜇 (𝐾), 𝑟 𝛼 𝜇 (𝐾 ′ ) > 𝛼 + 𝜆 , see [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]Theorem 3.4] where also the dependencies of 𝛿 and 𝑑 𝐻 (𝐾, 𝐾 ′ ) are made precise. Lemma 10.9. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼 > 0, 𝜇 > 0 and 𝜆 > 0, such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆. where 𝑅 max = 𝑅 max (𝐾) < ∞, μ = μ𝛼,𝛼 𝜇,𝜆 (𝐾) > 0, and 𝐶 is defined by (76).

Proof. The proof is identical to the proof of Lemma 10.7, however this this time we combine Lemmas 10.2 and 9.3 to achieve the more symmetric statement. We note that we choose the same optimal value for 𝛿 from (81). □

GROMOV-HAUSDORFF STABILITY OF THE (𝜆, 𝛼)-MEDIAL AXIS UNDER HAUSDORFF PERTURBATION OF 𝐾

In this section, we bound the Gromov-Hausdorff distance between the (𝜆, 𝛼)-medial axis of a set 𝐾 and the medial axis of perturbation of the set, where the perturbation is small in the Hausdorff sense. Gromov-Hausdorff distance is understood to be with respect to the intrinsic distance on the medial axis, that is the metric on the space 𝐾 that realizes a path in ax 𝛼 𝜆 (𝐾) between 𝑎 and 𝑏.

ax 𝛼 𝜆 (𝐾) is the metric induced by the geodesic distance on the set. As we have seen in Section 9.4 this metric is well defined.

We assume that we are in the symmetric setting, that is the conditions of Lemma 10.7 are satisfied. We assume moreover that 𝐾 𝑐 and (𝐾 ′ ) 𝑐 are connected.

Figure 11 illustrates the idea of the proof of Theorem 11.1. Consider the pairs (𝑎, 𝑎 ′ ), (𝑏, 𝑏 ′ ) ∈ R = (𝑥, 𝑥 ′ ) ∈ ax 𝛼 𝜆 (𝐾) × ax 𝛼 𝜆 (𝐾 ′ ), ∥𝑥 -𝑥 ′ ∥ < 𝐶𝜖 .

In order to compare the length of a geodesic 𝛾 from 𝑎 to 𝑏 to the length of a geodesic 𝛾 ′ from 𝑎 ′ to 𝑏 ′ (left), we first create a path Γ (middle), concatenation of 𝛾 with two straight segments 𝜎 𝑎𝑎 ′ and 𝜎 𝑏 ′ 𝑏 . Then Γ is "pushed" (right) along the flow Φ 𝐾 , which, after a "time" 𝑡 = O 𝜖 1 4 , belongs to ax 𝛼 𝜆 (𝐾). The pushed path can then be shown to be not much longer than the path 𝛾 ′ . Theorem 11.1. Let 𝐾, 𝐾 ′ ⊂ R 𝑛 be complements of bounded open sets 𝐾 𝑐 , (𝐾 ′ ) 𝑐 , 𝛼 > 0, 𝜇 > 0 and 𝜆 > 0, such that, for some 𝛼 ′ < 𝛼 one has 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆 and 𝑟 𝛼 ′ 𝜇 (𝐾 ′ ) > 𝛼 + 𝜆, and 𝐾 ⊕𝛼 𝑐 and 𝐾 ′⊕𝛼 𝑐 are connected. Denote 𝑅 max = max (𝑅 max (𝐾), 𝑅 max (𝐾 ′ )), and μ = min μ𝛼,𝛼 Proof. In order to lower bound the Gromov-Hausdorff distance between ax 𝛼 𝜆 (𝐾) and ax 𝛼 𝜆 (𝐾 ′ ) under the assumptions of Lemma 10.7 we use Definition 8.7.

Consider the relation R ⊂ ax 𝛼 𝜆 (𝐾) × ax 𝛼 𝜆 (𝐾 ′ ) defined by: R = (𝑥, 𝑥 ′ ) ∈ ax 𝛼 𝜆 (𝐾) × ax 𝛼 𝜆 (𝐾 ′ ), ∥𝑥 -

𝑥 ′ ∥ < 𝐶𝜖 1 2 , ( 82
)
where 𝐶 is defined by (76). We know from Lemma 10.7 that this relation is surjective, which means that for any 𝑥 ∈ ax 𝛼 𝜆 (𝐾) there is 𝑥 ′ ∈ ax 𝛼 𝜆 (𝐾 ′ ) such that (𝑥, 𝑥 ′ ) ∈ R and, reciprocally, if 𝑥 ′ ∈ ax 𝛼 𝜆 (𝐾 ′ ) there is 𝑥 ∈ ax 𝛼 𝜆 (𝐾) such that (𝑥, 𝑥 ′ ) ∈ R.

Consider (𝑎, 𝑎 ′ ), (𝑏, 𝑏 ′ ) ∈ R. Since 𝐾 𝑐 and (𝐾 ′ ) 𝑐 are connected, Theorem 9.12 yields that there are paths 𝛾 : [0, 𝐿] → ax 𝛼 𝜆 (𝐾) and 𝛾 ′ : [0, 𝐿 ′ ] → ax 𝛼 𝜆 (𝐾 ′ ), parametrized by arc length such that: 𝛾 (0) = 𝑎, 𝛾 (𝐿) = 𝑏, 𝛾 ′ (0) = 𝑎 ′ , 𝛾 ′ (𝐿 ′ ) = 𝑏 ′ and where 𝐿 and 𝐿 ′ are the respective geodesic distances in ax 𝛼 𝜆 (𝐾) and ax 𝛼 𝜆 (𝐾 ′ ) between 𝑎, 𝑏 and 𝑎 ′ , 𝑏 ′ , that is, 𝐿 = 𝑑 ax 𝛼 𝜆 (𝐾) (𝑎, 𝑏) and 𝐿 ′ = 𝑑 ax 𝛼 𝜆 (𝐾 ′ ) (𝑎 ′ , 𝑏 ′ ). Denote by 𝜎 𝑎𝑎 ′ and 𝜎 𝑏 ′ 𝑏 the linear path from 𝑎 to 𝑎 ′ and from 𝑏 ′ to 𝑏, respectively. By definition of the relation R, we have that their lengths are upper bounded by 𝐶𝜖 1 2 and, since 𝑅 𝐾 (𝑎), 𝑅 𝐾 (𝑏) ≥ 𝜆 +𝛼, we have the inclusions im(𝜎 𝑎𝑎 ′ ), im(𝜎 𝑏 ′ 𝑏 ) ⊂ 𝐾 ⊕𝜆+𝛼-𝐶𝜖 and 𝑎, 𝑏 ∈ ax 𝛼 𝜆 (𝐾) with (𝑎, 𝑎 ′ ), (𝑏, 𝑏 ′ ) ∈ R gives as well im(𝜎 𝑎𝑎 ′ ), im(𝜎 𝑏 ′ 𝑏 ) ⊂ ax 𝛼 𝜆 (𝐾) ⊕𝐶𝜖 . Now consider the path Γ from 𝑎 to 𝑏, which we define as the concatenation of 𝜎 𝑎𝑎 ′ , 𝛾 ′ and 𝜎 𝑏 ′ 𝑏 . One has, length (im(Γ)) < 𝐿 ′ + 2𝐶𝜖 .

(85)

For 𝑇 ≥ 0, we consider now the path Γ [𝑇 ] 𝐾 , connecting 𝑎 to 𝑏 according to Definition 9.8. Intuitively, the path Γ [𝑇 ] 𝐾 can be visualized as the path Γ "pushed" during a time 𝑇 by the flow Φ 𝐾 while "holding" the end points 𝑎 and 𝑏 as shown in Figure 11

𝐾

≥ 𝐿 = 𝑑 ax 𝛼 𝜆 (𝐾) (𝑎, 𝑏).

Because by (85) Γ lies in 𝐾 ⊕𝛼 𝑐 , Lemma 9.9 can be applied which gives, using (84): Because we make, symmetrically, the same assumptions on 𝐾 and 𝐾 ′ one has, (𝑎, 𝑎 ′ ), (𝑏, 𝑏 ′ ) ∈ R ⇒ 𝑑 ax 𝛼 𝜆 (𝐾) (𝑎, 𝑏) -𝑑 ax 𝛼 𝜆 (𝐾 ′ ) (𝑎 ′ , 𝑏 ′ ) ≤ 2𝐶 By Corollary 9.13 (using the assumptions 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 + 𝜆 and 𝑟 𝛼 ′ 𝜇 (𝐾 ′ ) > 𝛼 + 𝜆), we know that 𝐷 < ∞. □

Figure 1 :

 1 Figure 1: Comparison between Fréchet (𝑑 𝐹 ) and Gromov-Hausdorff (𝑑 𝐺𝐻 ) stability. On the two examples below, the shapes are (𝜆, 𝛼)-filtered medial axes of nearby sets (in dotted lines), and as asserted by Theorem 11.1, the Gromov-Hausdorff distance between them is small.

Figure 2 :

 2 Figure2: Comparison between 𝜆-medial axis and (𝜆,𝛼)medial axis evolutions for increasing 𝜆, in the particular case where 𝐾 consists of two points in the plane. The 𝜆medial axis would be either the whole bisector line of the two points, for 𝜆 smaller or equal to half the distance between the points, either the empty set for larger value of 𝜆. By contrast, the evolution, for increasing 𝜆, of the (𝜆, 𝛼)medial axis, which is also the 𝜆-medial axis of the union of two disks of radius 𝛼, evolves continuously, in Hausdorff distance, as 𝜆 increases.

Figure 4 :

 4 Figure 4: Further evolution of the (𝜆,𝛼)-medial axis, after the steps of the bottom row of figure 3. For some small interval of values of 𝜆, the Voronoi vertex is an isolated point on ax 𝛼 𝜆 (𝐾), as illustrated on the middle, When 𝛼 + 𝜆 equals the Delaunay triangle circumradius, this points disappears from ax 𝛼 𝜆 (𝐾), which corresponds to a discontinuity of 𝜆 → ax 𝛼 𝜆 (𝐾) for the Hausdorff distance.

1 2 )

 2 bound on the ambient Euclidean distance between points pairs in relation that upper bounds the O (𝜖 1 4

  [START_REF] Blanc-Beyne | A salience measure for 3D shape decomposition and sub-parts classification[END_REF] where ♯𝑋 denotes the cardinality of the set 𝑋 .When 𝑥 ∈ 𝐾, one has Θ 𝐾 (𝑥) = {𝑥 } and F 𝐾 (𝑥) = 0. It follows that ax(𝐾) ⊂ 𝐾 𝑐 .When 𝑥 ∉ 𝐾 ∪ ax(𝐾), ∇ 𝐾 (𝑥) coincides with the gradient of the Lipschitz function 𝑥 ↦ → 𝑅 𝐾 (𝑥).

1 Figure 5 :

 15 Figure 5: Pictorial overview of the definitions and notation. The set 𝐾 is indicated in black and the medial axis in green.

1 ≤ 1 Figure 6 :

 116 Figure 6: The blue path follows the flow. The orange vectors indicate the vectors (∇ 𝐾 (𝑥)) whose flow Φ 𝐾 follows. They have been shifted slightly for visibility and lengths have been indicated.

Lemma 4 .

 4 13 of [42] immediately yields: Corollary 8.5.

  def.inf 𝑦 ∈𝐾 𝑑 (𝑥, 𝑦) = min 𝑦 ∈𝐾 𝑑 (𝑥, 𝑦). Alternatively, 𝐾 ⊕𝛼 can be defined as the Minkowski sum of 𝐾 with a ball of radius 𝛼 centered at 0, which motivates the ⊕ notation.The Hausdorff distance between two compact subsets 𝐴, 𝐵 of the Euclidean space is defined as ([15, Section 5.30]): Definition 8.6 (Hausdorff distance). The Hausdorff distance between closed sets 𝐴 and 𝐵 is defined as𝑑 𝐻 (𝐴, 𝐵) = inf 𝜀, 𝐴 ⊂ 𝐵 ⊕𝜀 and 𝐵 ⊂ 𝐴 ⊕𝜀 .(21)One trivially has, 𝐴 ⊂ 𝐵 and 𝐵 ⊂ 𝐴 ⊕𝜀 ⇒ 𝑑 𝐻 (𝐴, 𝐵) ≤ 𝜀.

  and 𝜆>0 ax 𝜆 (𝐾) = ax(𝐾).

( a )

 a 𝑓 is absolutely continuous. (b) 𝑓 is differentiable almost everywhere on [𝑎, 𝑏], 𝑓 ′ ∈ 𝐿 1 [𝑎, 𝑏],and𝑓 (𝑥) -𝑓 (𝑎) = ∫ 𝑥 𝑎 𝑓 ′ (𝑡)𝑑𝑡8.7 Volterra integral inequalities Apart from a generalized fundamental theorem of calculus we'll also need a estimates on Volterra integrals. These are related to the solution of differential equations of Čaplygin type. The simplest version of the result we recall first, see for example [46, Theorem 2, Section 2, Chapter XI], Theorem 8.11 (Čaplygin). Let 𝐹 (𝑥, 𝑡) be a Lipschitz function and 𝑥 = 𝑥 (𝑡) a differentiable function such that 𝑥 (0) = 𝑥 0 , and 𝑑 𝑑𝑡 𝑥 (𝑡) ≤ 𝐹 (𝑡, 𝑥 (𝑡)), then 𝑥 (𝑡) ≤ 𝑦 (𝑡), where 𝑦 (𝑡) is the solution of the initial value problem 𝑦 (0) = 𝑥 0 and 𝑑 𝑑𝑡 𝑦 (𝑡) = 𝐹 (𝑡, 𝑦 (𝑡)

•

  If 𝑅 𝐾 (𝑥) ≥ 𝑟 𝛼 ′ 𝜇 (𝐾) then 𝑅 𝐾 ⊕𝛼 (𝑥) ≥ 𝑟 𝛼 ′ 𝜇 (𝐾) -𝛼. Since 𝑥 ∉ ax 𝛼 𝜆 , one has F 𝐾 ⊕𝛼 (𝑥) = F 𝛼 𝜆 (𝑥) < 𝜆. Combining this with (12) we get, ∥∇ 𝐾 (𝑥) ∥ = ∥∇ 𝐾 ⊕𝛼 (𝑥) ∥ = √ 1 -F 𝐾 ⊕𝛼 (𝑥)

Figure 9 :

 9 Figure 9: 𝜆 ↦ → ax 𝜆 (𝐾) is not continuous, because 𝐾 is nonsmooth at the points 𝑎 and 𝑏.

Figure 10 : 2 2 max 𝛼𝜆μ 2

 10222 Figure 10: 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is continuous.

𝑛 2 Γ

 2 ( 𝑛 2 +1) , where Γ is the Euler Gamma function, see for example [25, page 622]. Remark 9.10. Thanks to Theorem 9.7, connected components of ax 𝛼 𝜆 (𝐾) are in one to one correspondance with connected components of 𝐾 ⊕𝛼 𝑐

  bounded, open subset of R 2 with infinite geodesic diameter. Moreover, for some 𝛼 > 1, taking 𝐾 = (𝑥, 𝑦, 𝑧) ∈ R 3 (𝑥, 𝑦) ∉ 𝑆 and 𝑑 (𝑥, 𝑦, 𝑧), 𝑆 × {0} ≥ 𝛼 , we get that the open bounded set 𝐾 ⊕𝛼 𝑐 deform retracts by vertical projection on 𝑆 × {0} along trajectories of small length ℎ < 1. Thanks to this vertical deformation retract we have that 𝑑 𝐺𝐻 ( 𝐾 ⊕𝛼 𝑐 , 𝑆) ≤ 2ℎ. More precisely the argument goes as follows: We have that 𝐾 ⊕𝛼 𝑐 = (𝑥, 𝑦, 𝑧) (𝑥, 𝑦) ∈ 𝑆 and |𝑧| < h(𝑥, 𝑦) , with h(𝑥, 𝑦) ≤ ℎ ≤ 1. It follows by concatenating a geodesic 𝑆 with vertical line segments, that

2

  and thus we have the Volterra integral inequality, 𝑅 0 (𝑠) = 𝑅 0 (0) + ∫ 𝑠 0 𝑘 (𝑅 0 (𝜏))d𝜏,

  𝛿)𝛿 μ 𝜖.

10. 3

 3 Flow to the medial axis after a perturbation of the set 𝐾.

Figure 11 :

 11 Figure 11: Illustration of the proof of Theorem 11.1. The path Γ, concatenation of 𝜎 𝑎𝑎 ′ , 𝛾 ′ and 𝜎 𝑏 ′ 𝑏 , is pushed through the flow Φ 𝐾 into a path Γ 𝐶

2𝐶

  𝐷 = max GeoDiameter(ax 𝛼 𝜆 (𝐾)), GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ )) < ∞.

𝛼 - 1 .

 1 Since, by Theorem 9.12, 𝐿 ′ ≤ GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ )) < ∞, one has𝐿 ≤ 𝐿 ′ +2𝐶

4 𝛼 - 1

 41 , where 𝐷 = max GeoDiameter(ax 𝛼 𝜆 (𝐾)), GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ )) .

  1) When 𝜒 𝐾 does not vanish on (0, 𝜆], the 𝜆-medial axis preserves the homotopy type of the complement 𝐾 𝑐 of 𝐾 [20, Theorem 2], (2) Taking the Hausdorff distance on the input 𝐾 and the one sided Hausdorff distance on the output ax 𝜆 (𝐾) we get a kind of modulus of continuity. If 𝑑 ℎ (𝐾, 𝐾 ′ ) is small, the points in ax 𝜆 (𝐾) are "near", in a quantified way, ax 𝜆 ′ (𝐾 ′ ), for some 𝜆 ′ < 𝜆 close to 𝜆 [20, Theorem 3]. (3) For "regular values of 𝜆" the map 𝐾 ↦ → ax 𝜆 (𝐾) is continuous for the Hausfdorff distance [20, Theorem 5]. However, the modulus of continuity can be arbitrarily large in general.

  𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) -𝛼 𝑅 𝐾 (Φ 𝐾 (𝑡, 𝑥)) 𝐾 (𝑡, 𝑥)) 2 ∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) 2 . (42) Consider now𝑇 such that Φ 𝐾 (𝑇 , 𝑥) ∉ ax 𝛼 𝜆+𝛿 (𝐾), and then F 𝛼 𝐾 (Φ 𝐾 (𝑇 , 𝑥)) < 𝜆 + 𝛿. From (30) this gives: ∀𝑡 ∈ [0,𝑇 ], F 𝛼 𝐾 (Φ 𝐾 (𝑡, 𝑥)) < 𝜆 + 𝛿. Lemma 9.2 gives a lower bound on ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥))∥, that is, ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥))∥ ≥ μ = μ𝛼,𝛼

		again,
	𝑑 𝑑𝑡 +	=	𝛼 𝑅 𝐾 (Φ 𝜇,𝜆+𝛿 (𝐾) > 0
	and (42) then gives,

  Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼, 𝜆 max > 0, 𝜇 ∈ (0, 1] such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆 max . 𝛼𝜆 min μ2 -Lipschitz in the interval [𝜆 min , 𝜆 max ] for Hausdorff distance, where 𝑅 max = 𝑅 max (𝐾) < ∞ and μ = μ𝛼,𝛼 The (𝜆, 𝛼)-medial axis is Hausdorff-stable under 𝛼 perturbation In this subsection we complete the proof of the stability of the (𝜆, 𝛼)medial axis under perturbations of 𝜆 and 𝛼. It is not difficult to see Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼, 𝜆 > 0, 𝜇 ∈ (0, 1] if 𝑟 𝛼 min 𝜇 (𝐾) > 𝛼 max + 𝜆. The map 𝛼 ↦ → ax 𝛼 𝜆 (𝐾) is 𝑅 max 𝛼 min μ2 -Lipschitz in the interval [𝛼 min , 𝛼 max ] for Hausdorff distance, where μ = μ𝛼 max ,𝛼 min

						9.3 that ax 𝛼+𝛿 𝜆 (𝐾) ⊂ ax 𝛼 𝜆 (𝐾) for 𝛿 ≥ 0. We establish that ax 𝛼 𝜆 (𝐾)
						is not very far from ax 𝛼+𝛿 𝜆 (𝐾) by proving that ax 𝛼 𝜆 (𝐾) flows (fast
						enough) into ax 𝛼+𝛿 𝜆 (𝐾). This is done by determining that the radius
						of the enclosing ball of the closest points on 𝐾 increases sufficiently
						fast.
						Lemma 9.5. 𝜇,𝜆	> 0.
		⇒	𝜆 +	𝜆𝛼 μ2 𝑅 2 max	𝑇 < 𝜆 + 𝛿 ⇒ 𝑇 <	𝛿𝑅 2 max 𝜆𝛼 μ2 .
	By contraposition we have:
		𝑥 ∈ ax 𝛼 𝜆 (𝐾) and 𝑇 ≥	𝛿𝑅 2
						𝛿𝑅 2 max 𝜆𝛼 μ2 .
	Since the Euclidean distance between 𝑥 ∈ ax 𝛼 𝜆 (𝐾) and Φ 𝐾 (𝑇 , 𝑥) ∈
	ax 𝛼 𝜆+𝛿 (𝐾) cannot be larger than the length of the path connecting
	them we get (40).
						□
	Since for 𝛿 ≥ 0 one has ax 𝛼 𝜆+𝛿 (𝐾) ⊂ ax 𝛼 𝜆 (𝐾), (40) and the upper
	bound (22) immediately give us:
	Lemma 9.4. The
	map
				𝜆 ↦ → ax 𝛼 𝜆 (𝐾)
	is	𝑅 2 max
						𝜇,𝜆 max	> 0.

ax 𝛼 𝜆 (𝐾) and Φ 𝐾 (𝑇 , 𝑥) ∉ ax 𝛼 𝜆+𝛿 (𝐾)

max 𝜆𝛼 μ2 ⇒ Φ 𝐾 (𝑇 , 𝑥) ∈ ax 𝛼 𝜆+𝛿 (𝐾).

Since ∀𝑦, ∥∇ 𝐾 (𝑦)∥ ≤ 1, one has

𝑆 = length (Φ 𝐾 ( [0,𝑇 ], 𝑥) = ∫ 𝑇 0 ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑥)) ∥𝑑𝑡 ≤ 𝑇 ≤

  𝑥).Theorem 9.7. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 , 𝛼 ≥ 0, 𝜆 > 0 and 𝛼 ′ such that 0 < 𝛼 ′ ≤ 𝛼 and 𝑟 𝛼 ′ 𝜇 (𝐾) > 𝛼 +𝜆 then ax 𝛼 𝜆 (𝐾) has the same homotopy type as 𝐾 ⊕𝛼 ′ 𝑐 .

	Lemma 9.6, (31), and the natural inclusion ax 𝛼 𝜆 (𝐾) ⊂ 𝐾 ⊕𝛼 ′ 𝑐
	together imply that 𝐻 gives a homotopy equivalence between
	𝐾 ⊕𝛼 ′ 𝑐	and ax 𝛼

𝜆 (𝐾), as it satisfies Definition 8.1. Since, by

[START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF]

, 𝑟 < wfs(𝐾) ⇒ ∃𝜇 > 0, such that 𝑟 𝛼 𝜇 (𝐾) ≥ 𝑟, one sees that:

  . Consider 𝑥, 𝑥 ′ ∈ ax 𝛼 𝜆 (𝐾) ⊂ 𝐾 ⊕𝛼 𝑐 and Γ a path in 𝐾 ⊕𝛼 𝑐 from 𝑥 to 𝑥 ′ with length upper bounded by GeoDiameter 𝐾 ⊕𝛼 𝑐 . As in Lemma 9.3 we set μ = μ𝛼,𝛼

	is included in 𝐾 ⊕𝛼 𝑐	, Lemma 9.9 gives:
	𝐿 Γ	𝑅max μ2	𝐾	≤ 2	𝑅 max μ2 + 𝐿(Γ)𝑒	𝑅max 𝛼 μ2	(52)
	𝑅max					𝑅max
	Due to (31), Γ	μ2	𝐾 ( [0, 1/3]) and Γ	μ2	𝐾 ( [2/3, 1]) are in-
								𝑅max
	side ax 𝛼 𝜆 (𝐾). As a consequence of Lemma 9.6, Γ	μ2

𝜇,𝜆 . Using Definition 9.8 we consider now the path Γ 𝑅max μ2 𝐾 with end points 𝑥 and 𝑥 ′ . Because Γ

  by 𝑑 1 and 𝑑 2 the respective intrinsic distances in ax 𝛼 𝜆 (𝐾) and ax 𝛼 𝜆+𝛿 (𝐾). By Theorem 9.7, since 𝐾 ⊕𝛼 𝑐 is connected (which is equivalent to be path-wise connected for an open set), ax 𝛼 𝜆 (𝐾) is path-wise connected and 𝑥 1 and 𝑥 ′ 1 are in the same connected component of ax 𝛼 𝜆 (𝐾). Thanks to Theorem 9.12, 𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) < ∞ and there is a path 𝛾 1 : [0, 1] → ax 𝛼 𝜆 (𝐾) such that 𝑑 1 (𝑥 1 , 𝑥 ′ 1 ) = 𝐿(𝛾 1 ). Thanks to Lemma 9.9, the path 𝛾 1 [𝑇 ] 𝐾 has length upper bounded by 2𝑇 + 𝐿(𝛾 1 )𝑒

	𝑇
	𝛼 .
	By Definition 9.8, one has 𝛾 1

  𝐾) > 𝛼 + 𝜆 + 𝛿 and 𝐾 ⊕𝛼 𝑐 is connected. Then, the map 𝛼 ↦ → ax 𝛼 𝜆 (𝐾) is locally Lipschitz for the Gromov-Hausdorff distance with respect to the intrinsic metric.

	More precisely, one has
	𝑑 GH (ax 𝛼+𝛿 𝜆 (𝐾), ax 𝛼 𝜆 (𝐾)) ≤ 2𝑇 + 𝐷 𝑒	𝑇 𝛼 -1 = 𝑂 (𝛿) ,
	with
	𝑇 =	𝑅 max 𝛼 μ2 𝛿,
	and 𝐷 < ∞ is the geodesic diameter of ax 𝛼 𝜆 (𝐾).

  12. □ 10.2 Points close to ax 𝛼 𝜆 (𝐾) flow inside it after a short time Lemma 10.2. Let 𝐾 ⊂ R 𝑛 be the complement of a bounded open set 𝐾 𝑐 and 𝛼 > 0, 𝜇 > 0 and 𝜆 > 0, such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆. Then, if 𝛿 𝜆 and 𝜖 < min 2𝛼,where 𝑅 max = 𝑅 max (𝐾) < ∞ and μ = μ𝛼,𝛼 𝜇,𝜆 > 0. Moreover, for 𝑦 ∈ ax 𝛼 𝜆 (𝐾) ⊕𝜖 , the length of the trajectory Φ 𝐾 0,

			(2𝜆-𝛿)𝛿 8𝑅 max	one has
	Φ 𝐾	8𝑅 2 max (2𝜆 -𝛿) 𝛿	μ 𝜖 , ax 𝛼 𝜆 (𝐾) ⊕𝜖 ⊂ ax 𝛼 𝜆-𝛿 (𝐾),
				8𝑅 2 max (2𝜆-𝛿)𝛿 μ 𝜖 , 𝑦
	is upper bounded by
			8𝑅 2 max (2𝜆 -𝛿) 𝛿	𝜖.

  2 + ∥𝑦 (𝑠) -𝑎∥2 . Using[START_REF] Yan | Erosion Thickness on Medial Axes of 3D Shapes[END_REF] we have:(𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≤ 𝜆 2 + 𝑆 2 𝑎 + 2∥𝑦 (𝑠) -𝑎∥ √ (𝑅 𝐾 (𝑎) -𝛼) 2 -F 𝛼 𝐾 (𝑎)2 + ∥𝑦 (𝑠) -𝑎∥ 2 . and since F 𝛼 𝐾 (𝑎) ≥ 𝜆 one has, using (58) again, √ (𝑅 𝐾 (𝑎) -𝛼) 2 -F 𝛼 𝐾 (𝑎) 2 ≤ 𝑆 𝑎 and (𝑅 𝐾 (𝑦 (𝑠)) -𝛼) 2 ≤ (𝑆 𝑎 + ∥𝑦 (𝑠) -𝑎∥) 2 + 𝜆 2 .

  We have from 𝜖 < 2𝛼 and (58) that 2𝑆 𝑎 +𝜖 < 2(𝑆 𝑎 +𝛼) ≤ 2𝑅 max . Therefore (60) together with (62) gives us2(𝑆 0 -𝑆 𝑎 -𝜖)𝑠 < 2𝑅 max 𝜖 + (2𝑆 𝑎 + 𝜖) 𝜖Remark 10.3. Note that the assumption 𝜖 < 2𝛼 is not really necessary as, here, we could merely upper bound 𝜖 by 𝑅 max , so that 2𝑆 𝑎 + 𝜖 < 3𝑅 max and we would get 5𝑅 max 𝜖 instead of 4𝑅 max 𝜖 as upper bound in (66).

								(2𝜆 -𝛿) 𝛿
								4	𝑆 0 + 𝑆 𝑎	.
	Combining (58) and (57) one has 𝑆 0 + 𝑆 𝑎 < 2𝑅 max and using again
	𝜖 <	(2𝜆-𝛿)𝛿 8𝑅 max we get
		𝑆 0 -𝑆 𝑎 -𝜖 >	3 8	(2𝜆 -𝛿) 𝛿 𝑅 max	-𝜖 >	(2𝜆 -𝛿) 𝛿 4𝑅 max	.	(65)
						≤ 4𝑅 max 𝜖.	(66)
	Equations (65) and (66) gives us
				𝑠 <	8𝑅 2 max (2𝜆 -𝛿) 𝛿	𝜖
	We have obtained this inequality by assuming 𝑦 (𝑠) ∉ ax 𝛼 𝜆-𝛿 . By
	contraposition we get
		𝑦	8𝑅 2 max (2𝜆 -𝛿) 𝛿	𝜖 ∈ ax 𝛼 𝜆-𝛿 .

This proves the last statement of the lemma that upper bounds the length of the trajectory. Since by Lemma 9.2, as long as 𝑦 (𝑠) ∉ ax 𝛼 𝜆-𝛿 the modulus of the right derivative of 𝑡 ↦ → Φ 𝐾 (𝑡, 𝑦), which is 𝑑𝑠 𝑑𝑡 = ∥∇ 𝐾 (Φ 𝐾 (𝑡, 𝑦)) ∥, is lower bounded by μ we get, still using Theorem 8.10, the first statement of the lemma. □

  We write 𝑑 𝐻 (𝐶 1 , 𝐶 2 ) for the Hausdorff distance between two compact sets 𝐶 1 , 𝐶 2 ⊂ R 𝑛 . Lemma 10.5. Let 𝐾, 𝐾 ′ ⊂ R 𝑛 be complements of bounded open sets 𝐾 𝑐 and 𝐾 ′𝑐 and 𝛼 ≥ 0 ,𝜇 > 0, 𝜆 > 0, such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆. If 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖 then, if 𝛿 < 𝜆 and 𝜖 < Moreover, for 𝑦 ∈ ax 𝛼 𝜆 (𝐾 ′ ), the length of the trajectory Φ 𝐾 0,

		8𝑅 2 max (2𝜆-𝛿)𝛿 μ 𝜖 , 𝑦 is upper bounded by
		8𝑅 2 max (2𝜆 -𝛿) 𝛿	𝜖.
		(2𝜆-𝛿)𝛿 8𝑅 max one has:
	Φ 𝐾	8𝑅 2

max (2𝜆 -𝛿) 𝛿 μ 𝜖 , ax 𝛼 𝜆 (𝐾 ′ ) ⊂ ax 𝛼 𝜆-𝛿 (𝐾),

where 𝑅 max = max{𝑅 max (𝐾), 𝑅 max (𝐾 ′ )} < ∞ and μ = μ𝛼,𝛼 𝜇,𝜆 > 0.

  Let 𝐾, 𝐾 ′ ⊂ R 𝑛 be complements of a bounded open sets 𝐾 𝑐 and 𝐾 ′𝑐 and 𝛼 > 0, 𝜇 > 0, 𝜆 > 0, such that 𝑟 𝛼 where 𝑅 max = max{𝑅 max (𝐾), 𝑅 max (𝐾 ′ )} < ∞ , μ = μ𝛼,𝛼 𝜇,𝜆 (𝐾) > 0, and 𝐶 is defined as 𝑟 𝛼 𝜇 (𝐾 ′ ) > 𝛼 +𝜆 and 𝑅 max = max (𝑅 max (𝐾), 𝑅 max (𝐾 ′ )), and μ = min μ𝛼,𝛼 Indeed these Lemmas 10.5 and 9.3 give that if 𝐾, 𝐾 ′ ⊂ R 𝑛 are complements of a bounded open sets 𝐾 𝑐 and 𝐾 ′𝑐 and 𝛼 > 0, 𝜇 > 0, 𝜆 > 0, are such that 𝑟 𝛼 𝜇 (𝐾) > 𝛼 + 𝜆 and 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖 then for 0 < 𝛿 < 𝜆 and 𝜖 <

	10.4 Hausdorff distance between ax 𝛼 𝜆 (𝐾 ′ ) and ax 𝛼 𝜆 (𝐾) Combining Lemmas 10.5 and 9.3 allows to give a more symmetric statement. Lemma 10.7. (2𝜆-𝛿)𝛿 8𝑅 max , 𝜆 2 16𝛼 μ then, Φ 𝐾 𝐶𝜖 1 2 , ax 𝛼 𝜆 (𝐾 ′ ) ⊂ ax 𝛼 𝜆 (𝐾), 𝐶 = 22 3 𝑅 2 max 𝛼 1 2 μ 3 2 𝜆 . (76) Moreover, if one has also symmetrically 𝑟 𝛼 𝜇 (𝐾), 𝜇,𝜆 (𝐾), μ𝛼,𝛼 𝜇,𝜆 (𝐾 ′ ) we have 𝑑 𝐻 ax 𝛼 𝜆 (𝐾), ax 𝛼 𝜆 (𝐾 ′ ) < 𝐶𝜖 1 2 . (77) Proof. We first flow ax 𝛼 𝜆 (𝐾 (2𝜆-𝛿)𝛿 8𝑅 max one has, Φ 𝐾 𝑅 2 max 𝛼 (𝜆 -𝛿) μ2 𝛿 + 8𝑅 2 max (2𝜆 -𝛿) 𝛿 μ 𝜖 , ax 𝛼 𝜆 (𝐾 ′ ) ⊂ ax 𝛼 𝜆 (𝐾), (78)

𝜇 (𝐾) > 𝛼 + 𝜆. If 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖, and, if 𝛿 = 2 √ 𝛼 μ𝜖 < 𝜆, and 𝜖 < min ′ ) into ax 𝛼 𝜆-𝛿 (𝐾), and then we flow from ax 𝛼 𝜆-𝛿 (𝐾) to ax 𝛼 𝜆 (𝐾).

  Then, if 𝛿 = 2 √ 𝛼 μ𝜖 < 𝜆 and 𝜖 < min 2𝛼,

		(2𝜆-𝛿)𝛿 8𝑅 max , 𝜆 2 16𝛼 μ one has
	Φ 𝐾 𝐶𝜖	1 2 , ax 𝛼 𝜆 (𝐾)

⊕𝜖

⊂ ax 𝛼 𝜆 (𝐾),

,

  𝜇,𝜆 (𝐾), μ𝛼,𝛼 𝜇,𝜆 (𝐾 ′ ) . Assume that 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖. If then the Gromov-Hausdorff distance between ax 𝛼 𝜆 (𝐾) and ax 𝛼 𝜆 (𝐾 ′ ) with respect to the intrinsic metric is upper bounded by

	𝜖 < min	16𝑅 2 max 𝜆 2 𝛼 μ	,	16𝛼 𝜆 2	μ ,	400𝑅 4 max 9𝜆 4 𝛼 μ3	,	𝐶 2𝛼	2	,	16𝑅 2 max 𝐶 𝜆 2 𝛼 μ	2	,	16𝛼 μ𝐶 𝜆 2	2

  𝜆 and it follows that im(𝜎 𝑎𝑎 ′ ), im(𝜎 𝑏 ′ 𝑏 ) ⊂ 𝐾 ⊕𝛼 𝑐 . Also im(𝛾 ′ ) ⊂ ax 𝛼 𝜆 (𝐾 ′ ) ⊂ 𝐾 ′⊕𝜆+𝛼 𝑐 . Because 𝛼, 𝜆 < 𝑅 max and μ ≤ 1, (83) implies 𝜖 < 𝜆, and 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖 gives 𝐾 ′⊕𝜆+𝛼 𝑐 ⊂ 𝐾 ⊕𝛼 𝑐 and we get im(𝛾 ′ ) ⊂ 𝐾 ⊕𝛼 𝑐 . From (77) one has as well im(𝛾 ′ ) ⊂ ax 𝛼 𝜆 (𝐾 ′ ) ⊂ ax 𝛼 𝜆 (𝐾)

				1	𝑐
				2	.
	From now on we assume:
		𝜖 <	𝜆 2 𝐶 2 =	9𝜆 4 𝛼 μ3 max 400𝑅 4	(83)
		1
	then 𝐶𝜖	2 < ⊕𝐶𝜖	1 2

  im(Γ) ⊂ 𝐾 ⊕𝛼 𝑐 ∩ ax 𝛼 𝜆 (𝐾)

	Γ is included in 𝐾 ⊕𝛼 𝑐	and ax 𝛼 𝜆 (𝐾)	⊕𝐶𝜖	1 2	, that is,
					⊕𝐶𝜖	1 2
						1
						2 .	(84)

  .Using (85), if 𝛿 ′ = 2

									√ 𝛼 μ𝐶𝜖	1 2 < 𝜆 and
						𝐶𝜖	1 2 < min 2𝛼,	(2𝜆 -𝛿 ′ ) 𝛿 ′ 8𝑅 max	,	𝜆 2 16𝛼 μ
												1
	we can apply Lemma 10.9 with 𝜖 replaced by 𝐶𝜖	2 .
		Note that the condition: 𝛿 ′ = 2	√ 𝛼 μ𝐶𝜖	1 2 < 𝜆 and
	𝐶𝜖	1 2 < min 2𝛼,	(2𝜆-𝛿 ′ )𝛿 ′ 8𝑅 max , 𝜆 2 16𝛼 μ is implied by
				𝜖 < min	2𝛼 𝐶	2	,	𝜆 2 𝛼 16𝑅 2 max 𝐶 μ	2	,	𝜆 2 16𝛼 μ𝐶	2	,	(86)
	so that Lemma 10.9 gives us:
						Φ 𝐾 𝐶 𝐶𝜖	1 2	1 2	, im(Γ) ⊂ ax 𝛼 𝜆 (𝐾),
	that is, together with (31),
												3	1
								im Γ	𝐶	2 𝜖	4
				3	1
	Since Γ	𝐶	2 𝜖	4	𝐾 is a path from 𝑎 ∈ ax 𝛼 𝜆 (𝐾) to 𝑏 ∈ ax 𝛼 𝜆 (𝐾) inside
	ax 𝛼 𝜆 (𝐾), one has
										3		1
				length Γ	𝐶	2 𝜖	4

𝐾

⊂ ax 𝛼 𝜆 (𝐾).

Unfortunately,[START_REF] Tagliasacchi | 3D Skeletons: A state-of-the-art report[END_REF] mixes up the 𝜃 -medial and 𝜆-medial axis in Figure11of that paper.

The nomenclature was introduced by Amenta et al.[START_REF] Amenta | The power crust[END_REF] in order to state conditions under which the topology of a set can be determined from a sampling of it, however the concept was known to Federer[START_REF] Federer | Curvature measures[END_REF].

The 𝛼-offset is denoted by 𝐾 ⊕𝛼 , see[START_REF] Chazal | The 𝜆-medial axis[END_REF] and the text following that equation for an explanation of the notation.

Recall that the Fréchet distance between two subsets 𝑆 1 , 𝑆 2 of a same metric space is the infimum of sup 𝑥 ∈𝑆 1 𝑑 (𝑥, ℎ (𝑥)) among all possible homeomorphisms ℎ : 𝑆 1 → 𝑆 2 . It is therefore infinite when shapes are not homeomorphic. Note that we do not consider the orientation of the sets 𝑆 1 and 𝑆 2 .

As only countable sets can have each of its elements representable by a finite word.

The dense set has, formally, to be recursively enumerable.

In fact computability of the function requires moreover the modulus of continuity of the map to be computable, in particular should not tend to 0 slower than any recursive function.

It is possible, following[START_REF] Edalat | A computational model for metric spaces[END_REF], to topologically embed our input and output metric spaces as maximal elements of some Scott domains. Our bounded modulus of continuity would then allow to provide effective structures for them.

The reach and medial axis can be defined for closed subsets of Riemannian manifolds[START_REF] Bangert | Sets with positive reach[END_REF][START_REF] Boissonnat | The reach of subsets of manifolds[END_REF][START_REF] Kleinjohann | Convexity and the unique footpoint property in Riemannian geometry[END_REF][START_REF] Kleinjohann | Nächste Punkte in der Riemannschen Geometrie[END_REF].

ACKNOWLEDGMENTS

We are greatly indebted to Erin Chambers for posing a number of questions that eventually led to this paper. We would also like to thank the other organizers of the workshop on 'Algorithms for the medial axis'. We are also indebted to Tatiana Ezubova for helping with the search for and translation of Russian literature. The second author thanks all members of the Edelsbrunner and Datashape groups for the atmosphere in which the research was conducted.

The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). 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) M-3073.