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

In this paper we introduce a pruning of the medial axis called the (𝜆, 𝛼)-medial axis (ax 𝛼 𝜆 ). We prove that the (𝜆, 𝛼)-medial axis of a set 𝐾 is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if 𝐾 and 𝐾 ′ are close in the Hausdorff (𝑑 𝐻 ) sense then the (𝜆, 𝛼)-medial axes of 𝐾 and 𝐾 ′ are close as metric spaces, that is the Gromov-Hausdorff distance (𝑑 𝐺𝐻 ) between the two is 1 4 -Hölder in the sense that 𝑑 𝐺𝐻 (ax 𝛼 𝜆 (𝐾), ax 𝛼 𝜆 (𝐾 ′ )) ≲ 𝑑 𝐻 (𝐾, 𝐾 ′ ) 1/4 . The Hausdorff distance between the two medial axes is also bounded, by 𝑑 𝐻 (ax 𝛼 𝜆 (𝐾), ax 𝛼 𝜆 (𝐾 ′ )) ≲ 𝑑 𝐻 (𝐾, 𝐾 ′ ) 1/2 . These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.

INTRODUCTION

Given a closed subset 𝐾 of Euclidean space R 𝑛 , its medial axis, denoted ax(𝐾), is the set of points in the complement 𝐾 𝑐 of 𝐾 for which there are at least two closest points in 𝐾, or, equivalently, 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 the full version of this paper [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]Section 8.2] for details. The critical function 𝜒 𝐾 of 𝐾 is then defined as:

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

) 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 (see also the full version [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]), 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(𝐾). (3)
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 𝛼 ([37, Lemma 9.4 and Lemma 9.5]). The map is 1 2 -Hölder with respect to 𝐾 ([37, Lemma 10.7]).

Secondly, we extend the stability results to the Gromov-Hausdorff distance, see [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]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 ([37, 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 𝛼 ([37, Lemmas 9.14 and 9.15]) and 1 4 -Hölder with respect to 𝐾 ([37, 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 distance4 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 ( [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]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 [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]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 5 As only countable sets can have each of its elements representable by a finite word.

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], [2, 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(𝐾)?

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:

(1) When 𝜒 𝐾 does not vanish on (0, 𝜆], the 𝜆-medial axis preserves the homotopy type of the complement 𝐾 𝑐 of 𝐾 [18, 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 𝜆 [18, Theorem 3]. (3) For "regular values of 𝜆" the map 𝐾 ↦ → ax 𝜆 (𝐾) is continuous for the Hausfdorff distance [START_REF] Chazal | The 𝜆-medial axis[END_REF]Theorem 5]. However, the modulus of continuity can be arbitrarily large in general. 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 𝐾 contains 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 5 (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. In Part II of the full version of this paper [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF] we consider the general situation of sets whose 𝛼-offsets have positive 𝜇-reach. In particular, [37, 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 μ. 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 6. In other words, there is 𝜖 > 0 such that:

𝑑 𝐻 (𝐾 ′ , 𝐾) < 𝜖 ⇒ 𝑟 𝛼 𝜇 ′ (𝐾 ′ ) > 𝑟 𝜇 (𝐾) -𝛼 . (4)
Then, [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]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 . ( 5
)
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 [37, Theorem 9.7].

6.1.2 Gromov-Hausdorff Stability. Lemma 9.11 and Theorem 9.12 of the full version [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF] 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 (6)
Thanks to (4), 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. 10Lemmas 9.14 and 9.15 of the full version [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF] give: . This value is indeed strictly smaller than 1 as the reach of the square is 0. 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 ( 6) 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, [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]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: where 𝐷 = max(GeoDiameter(ax 𝛼 𝜆 (𝐾)), GeoDiameter(ax 𝛼 𝜆 (𝐾 ′ ))). Again, taking for 𝐷 the upper bound (6) allows a uniform bound which is enough in theory.

𝑑 𝐺𝐻 ax 𝛼 𝜆 (𝐾 ′ ), ax 𝛼 𝜆 (𝐾) < 2
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 [37, 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 ([37, 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 [START_REF] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF]Theorem 11.1], when 𝑑 𝐻 (𝐾, 𝐾 ′ ) < 𝜖, [37, equation (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.

Figure 1 :

 1 Figure 1: Comparison between Frechet (𝑑 𝐹 ) 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 [37, 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 𝐾 contains 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.

Figure 5 :

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

6. 1 . 1

 11 Hausdorff Stability. As a consequence of [37, 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.

Figure 6 : 2 .

 62 Figure 6: (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

1 2

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

  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[START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] 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, 𝑡 𝑐𝑟𝑖𝑡 . ). For any 𝜆 min > 0, the map 𝜆 ↦ → ax 𝛼 𝜆 (𝐾) is Lipschitz in the interval [𝛼 min , 𝛼 max ] for Gromov-Hausdorff distance, where 𝐷 = max 𝜆∈ [𝛼 min ,𝛼 max ]

	Proposition 6.4. 𝑅 2 (2𝛼 min 𝜆 min +𝐷 𝛼 2 μ2 -Lipschitz in the interval [𝜆 min , 𝜆 max ] for Gromov-
	min
	Hausdorff distance, where
	𝐷 =	max 𝜆∈ [𝜆 min ,𝜆 max ]	GeoDiameter(ax 𝛼 𝜆 (𝐾)).
	Similarly, for 𝛼 min > 0, the map 𝛼 ↦ → ax 𝛼 𝜆 (𝐾) is	𝑅 (2𝛼 min +𝐷 𝛼 2 μ2	-
				min

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] Lieutier | Hausdorff and Gromov-Hausdorff stable subsets of the medial axis[END_REF] Section 8.4] 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 .

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].

But it is seems likely to be pessimistic in practical situations.

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.