Rémi Prébet

Mohab Safey

El Din

Éric Schost

Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results

Answering connectivity queries in real algebraic sets is a fundamental problem in effective real algebraic geometry that finds many applications in e.g. robotics where motion planning issues are topical. This computational problem is tackled through the computation of so-called roadmaps which are real algebraic subsets of the set V under study, of dimension at most one, and which have a connected intersection with all semi-algebraically connected components of V . Algorithms for computing roadmaps rely on statements establishing connectivity properties of some well-chosen subsets of V , assuming that V is bounded.

In this paper, we extend such connectivity statements by dropping the boundedness assumption on V . This exploits properties of so-called generalized polar varieties, which are critical loci of V for some well-chosen polynomial maps.

Introduction

Let Q be a real field of real closure R and let C be its algebraic closure (one can think about Q, R and C instead, for the sake of understanding) and let n ≥ 0 be an integer. An algebraic set V ⊂ C n defined over Q is the solution set in C n to a system of polynomial equations in n variables with coefficients in Q. A real algebraic set defined over Q is the set of solutions in R n to a system of polynomial equations in n variables with coefficients in Q. It is also the real trace V ∩ R n of an algebraic set V ⊂ C n . Real algebraic sets have finitely many connected components [START_REF] Bochnak | Real algebraic geometry[END_REF]Theorem 2.4.4.]. Counting these connected components [START_REF] Grigoryev | Counting connected components of a semialgebraic set in subexponential time[END_REF][START_REF] Vorobjov | Determination of the number of connected components of a semi-algebraic set in subexponential time[END_REF] or answering connectivity queries over V ∩ R n [START_REF] Schwartz | On the "piano movers" problem. ii. general techniques for computing topological properties of real algebraic manifolds[END_REF] finds many applications in e.g. robotics [START_REF] Canny | The complexity of robot motion planning[END_REF][START_REF] Capco | Robots, computer algebra and eight connected components[END_REF][START_REF] Wenger | Cuspidal and noncuspidal robot manipulators[END_REF][START_REF] Nawratil | Self-motions of pentapods with linear platform[END_REF][START_REF] Chablat | Deciding cuspidality of manipulators through computer algebra and algorithms in real algebraic geometry[END_REF].

Following [START_REF] Canny | The complexity of robot motion planning[END_REF][START_REF] Canny | Computing roadmaps of general semi-algebraic sets[END_REF], such computational issues are tackled by computing a real algebraic subset of V ∩R n , defined over Q, which has dimension at most one and a connected intersection with all connected components of V and contains the input query points. In [START_REF] Canny | The complexity of robot motion planning[END_REF], Canny called such a subset a roadmap of V .

The effective construction of roadmaps, given a defining system for V , relies on connectivity statements which allow one to define real algebraic subsets of V ∩ R n , of smaller dimension than that of V ∩ R n , and that have a connected intersection with the connected components of V ∩ R n . Such existing statements in the literature make the assumption that V has finitely many singular points and V ∩ R n is bounded. In this paper, we focus on the problem of obtaining similar statements by dropping the boundedness assumption. We prove a new connectivity statement which generalizes the one of [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] to the unbounded case and will be used in a separate paper to obtain asymptotically faster algorithms for computing roadmaps. We start by recalling the state-of-the-art connectivity statement, which allows us to introduce some material we need to state our main result.

State-of-the-art overview

We start by introducing some terminology. Recall that an algebraic set V ⊂ C n is the set of solutions of a finite system of polynomials equations. It can be uniquely decomposed into finitely many irreducible components. When all these components have the same dimension d, we say that V is d-equidimensional. Those points y ∈ V at which the Jacobian matrix of a finite set of generators of its associated ideal has rank n -d are called regular points and the set of those points is denoted by reg(V ). The others are called singular points; the set of singular points of V (its singular locus) is denoted by sing(V ) and is an algebraic subset of V . We refer to [START_REF] Shafarevich | Basic Algebraic Geometry[END_REF] for definitions and propositions about algebraic sets.

A semi-algebraic set S ⊂ R n is the set of solutions of a finite system of polynomial equations and inequalities. We say that S is semi-algebraically connected if for any y, y ∈ S, y and y can be connected by a semi-algebraic path in S, that is a continuous semi-algebraic function γ : [0, 1] → S such that γ(0) = y and γ(1) = y . A semi-algebraic set S can be decomposed into finitely many semi-algebraically connected components which are semi-algebraically connected semi-algebraic sets that are both closed and open in S. Finally, for a semi-algebraic set S ⊂ R n , we denote by S its closure for the Euclidean topology on R n . We refer to [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] and [START_REF] Bochnak | Real algebraic geometry[END_REF] for definitions and propositions about semi-algebraic sets and functions.

Let 0 ≤ d ≤ n and V ⊂ C n be a d-equidimensional algebraic set such that sing(V ) is finite. For 1 ≤ i ≤ n, let π i be the canonical projection: π i : (y 1 , . . . , y n ) -→ (y 1 , . . . , y i ) For a polynomial map ϕ : C n → C m a point y ∈ V is a critical point of ϕ if y ∈ reg(V ) and the differential of the restriction of ϕ to V at y, denoted by d y ϕ, is not surjective, that is

d y ϕ(T y V ) C m ,
where T y V denoted the tangent space to V at y. We will denote by W • (ϕ, V ) the set of the critical points of ϕ on V . A critical value is the image of a critical point. We put K(ϕ, V ) = W • (ϕ, V )∪sing(V ). The points of K(ϕ, V ) are called the singular points of ϕ on V . Figure 1 show examples of such critical loci.

x 1 x 2 Z W • (π 1 , Z) x 1 x 2 Z W • (x 2 1 + x 2 2 , Z)
Figure 1: Real trace of the critical locus on a sphere Z for: the projection on the first coordinate π 1 (left); the polynomial map ϕ associated to x 2 1 + x 2 2 ∈ R[x 1 , x 2 , x 3 ] (right). Let x = (x 1 , x 2 , x 3 ) ∈ Z. The differential of the restriction of π 1 to Z at x is the restriction of π 1 to T x Z. The image is not C if, and only if, T x Z is orthogonal to the x 1 -axis, so that critical points of the restriction of π to Z occur at (±1, 0, 0). Besides, the differential of the restriction of ϕ to Z at x is the restriction of -2x 3 • π 3 to T x Z. Hence, x is a critical point of the restriction of ϕ to Z if, and only if, either x 3 = 0 or T x Z is orthogonal the x 3 -axis.

For 1 ≤ i ≤ d we denote by W (π i , V ) the i-th polar variety defined as the Zariski closure of the critical locus W • (π i , V ) of the restriction of π i to V . Further, we extend this definition by considering ϕ = (ϕ 1 , . . . , ϕ n ) ⊂ Q[x 1 , . . . , x n ] and, for 1 ≤ i ≤ n, the map

ϕ i : C n -→ C i y → (ϕ 1 (y), . . . , ϕ i (y)) (1)
Following the ideas of [START_REF] Bank | Generalized polar varieties and an efficient real elimination[END_REF][START_REF] Bank | Generalized polar varieties: Geometry and algorithms[END_REF][START_REF] Bank | On the geometry of polar varieties[END_REF] we denote similarly W (ϕ i , V ) the i-th generalized polar variety defined as the Zariski closure of the critical locus W • (ϕ i , V ) of the restriction of ϕ i to V . We recall below [23, Theorem 14] (see also [START_REF] Basu | A baby step-giant step roadmap algorithm for general algebraic sets[END_REF]Proposition 3.3] for a slight variant of it), making use of polar varieties to establish connectivity statements.

For 2 ≤ i ≤ d, assume that the following holds:

• V ∩ R n is bounded; • W (π i , V
) is either empty or (i -1)-equidimensional and smooth outside sing(V );

• W (π 1 , W (π i , V )) is finite; • for any y ∈ C i-1 , π -1 i-1 (y) ∩ V is either empty or (d -i + 1)-equidimensional. Let K i = W (π 1 , W (π i , V )) ∪ sing(V ) and F i = π -1 i-1 (π i-1 (K i )) ∩ V.
Then, the real trace of W (π i , V )∪F i has a non-empty and semi-algebraically connected intersection with each semialgebraically connected component of V ∩ R n .

For the special case i = 2, this result was originally proved by Canny in [START_REF] Canny | The complexity of robot motion planning[END_REF][START_REF] Canny | Constructing roadmaps of semi-algebraic sets i: Completeness[END_REF]. A variant of it, again assuming i = 2, is given for general semi-algebraic sets in [START_REF] Canny | Computing roadmaps of general semi-algebraic sets[END_REF][START_REF] Canny | Computing roadmaps of general semi-algebraic sets[END_REF]. By dropping the restriction i = 2, the result in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14] allows one more freedom in the choice of i, and then, in the design of roadmap algorithms to obtain a better complexity. The rationale is as follows.

Restricting to i = 2, one expects (up to some linear change of variables or other technical manipulations) a situation where W (π 2 , V ) has dimension at most 1 and F 2 has dimension d -1 (see e.g. [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Lemma 31]). To obtain a roadmap for V ∩ R n one is led to call recursively roadmap algorithms with input systems defining the fibers F i 's. Hence, the depth of the recursion is n. Besides, letting D be the maximum degree of input equations defining V , roughly speaking each recursive call requires (nD) O(n) arithmetic operations in Q while the size of the input data grows by (nD) O(n) according to [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Proposition 33]. Consequently, one obtains roadmap algorithms using (nD) O(n 2 ) arithmetic operations in Q.

In [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF], using a baby steps/giant steps strategy, it is showed that one can take i √ d and then have a depth of the recursion √ d. It is also proved that each recursive step needed to compute systems encoding K i and F i requires at most (nD) O(n) arithmetic operations in Q, while the size of the input data grows by (nD) O(n) . All in all, up to technical details that we skip, one obtains roadmap algorithms using (nD) O(n √ n) arithmetic operations in Q. Finally, in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF], it is shown how to apply [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14] with i d 2 so that the depth of the recursion becomes log 2 (d). Hence, proceeding as in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF], an algorithm using (nD) 6n log 2 (d) arithmetic operations in Q is obtained in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF].

Such connectivity results and the algorithms that derive from them are at the foundation of many implementations for answering connectivity queries in real algebraic sets. As far as we know, the first one was reported in [START_REF] Mezzarobba | Computing roadmaps in smooth real algebraic sets[END_REF], showing that, at that time, basic computer algebra tools were mature enough to implement rather easily roadmap algorithms. More recently, practical results were reported applications of roadmap algorithms to kinematic singularity analysis in [START_REF] Capco | Robots, computer algebra and eight connected components[END_REF][START_REF] Capco | Positive dimensional parametric polynomial systems, connectivity queries and applications robotics[END_REF], showing the interest of developing roadmap algorithms beyond applications to motion planning. In parallel, the interest in roadmap algorithms keeps growing as they have also been adapted to the numerical side [START_REF] Iraji | Nuroa: A numerical roadmap algorithm[END_REF][START_REF] Chen | A numerical roadmap algorithm for smooth bounded real algebraic surface[END_REF]. This illustrates the interest of improving roadmap algorithms and the connectivity results they rely on.

Dropping the boundedness assumption in this scheme was done in [START_REF] Basu | Divide and conquer roadmap for algebraic sets[END_REF][START_REF] Basu | A baby step-giant step roadmap algorithm for general algebraic sets[END_REF] using infinitesimal deformation techniques. The algorithms proposed use respectively (nD) O(n √ n) and (nD) O(n log 2 (n)) arithmetic operations in Q. This induces a growth of intermediate data; the algorithm is not polynomial in its output size, which is (nD) O(n log(n)) .

In non-compact cases, one could also study the intersection of V with either [-c, c] n or a ball of radius c, for c large enough, but we would then have to deal with semi-algebraic sets instead of real algebraic sets, in which case [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14] is still not sufficient.

In order to ultimately obtain an algorithm dealing with unbounded smooth real algebraic sets with a complexity similar to that of [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF], the goal of this paper is instead to provide a new connectivity statement with no boundedness assumption and the same freedom brought by the one of [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF].

Main result Let V ⊂ C n be an algebraic set defined over Q and d > 0 be an integer. We say that V satisfies assumption (A) when (A) V is d-equidimensional and its singular locus sing(V ) is finite.

Recall that we say that a map ψ : Y ⊂ R n → Z ⊂ R m is a proper map if, for every closed (for Euclidean topology) and bounded subset Z ⊂ Z, ψ -1 (Z ) is a closed and bounded subset of Y . For ϕ = (ϕ 1 , . . . , ϕ n ) ⊂ Q[x 1 , . . . , x n ], and with ϕ i the induced map defined in (1), for 1 ≤ i ≤ n, we say that ϕ satisfies assumption (P) when (P) the restriction of the map ϕ 1 to V ∩ R n is proper and bounded from below.

We denote by W i = W (ϕ i , V ) the Zariski closure of the set of critical points of the restriction of ϕ i to V . For 2 ≤ i ≤ d and ϕ as above, we say that (ϕ, i) satisfies assumption (B) when (B 1 ) W i is either empty or (i -1)-equidimensional and smooth outside sing(V );

(B 2 ) for any y = (y 1 , . . . , y i ) ∈ C i , V ∩ ϕ -1 i-1 (y) is either empty or (d -i + 1)-equidimensional.
Note that when B 1 holds, sing(W i ) and critical loci of polynomial maps restricted to W i are welldefined. For S i a finite subset of V , we say that S i satisfies assumption (C) when

(C 1 ) S i is finite; (C 2 ) S i has a non-empty intersection with every semi-algebraically connected component of W (ϕ 1 , W i )∩ R n .
Finally, using a construction similar to the one used in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14], we let

K i = W (ϕ 1 , V ) ∪ S i ∪ sing(V )
and

F i = ϕ -1 i-1 (ϕ i-1 (K i )) ∩ V.
Theorem 1.1. For V, d, i in {1, . . . , d}, ϕ and S i as above, and under assumptions (A), (B), (C) and (P), the subset W i ∪ F i has a non-empty and semi-algebraically connected intersection with each semialgebraically connected component of V ∩ R n .

The proof structure of the above result follows a pattern similar to the one of [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]. Its foundations rely on the following basic idea, sweeping the ambient space with level sets of ϕ 1 , having a look at the connectivity of

V ∩ ϕ 1 -1 (] -∞, a]) and (W i ∪ F i ) ∩ ϕ 1 -1 (] -∞, a]
). The bulk of the proof consists in showing that these connectivities are the same. When one does not assume that i = 2 but does assume boundedness, one can take for ϕ 1 a linear projection, so that its level sets are hyperplanes. In this context, the proof in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF] also introduces ingredients such as Thom's isotopy lemma, which can be used thanks to the boundedness assumption. Dropping the boundedness assumption makes these steps more difficult and requires us to use a quadratic form for ϕ 1 to ensure a properness property. This in turn makes the geometric analysis more involved since now, the level sets of ϕ 1 are not hyperplanes anymore.

Structure of the paper Section 2 provides the necessary background on algebraic sets and polar varieties needed to follow the proof of Theorem 1.1. Section 3 proves two auxiliary results which analyze the connectivity of fibers of some polynomial maps. These are used in the proof of Theorem 1.1, which is given in Section 4. Finally, in Section 5, we sketch how Theorem 1.1 will be used to design new roadmap algorithms in upcoming work.

Preliminaries

Basic properties of algebraic sets Recall that given a finite set of polynomials g ⊂ C[x 1 , . . . , x n ] we denote by V (g) ⊂ C n the algebraic set defined as the vanishing locus of g. For y ∈ C n , we denote by Jac y (g) the Jacobian matrix of g evaluated at y. Conversely, given an algebraic set V ⊂ C n , we denote by I(V ) the ideal of V , that is the ideal of C[x 1 , . . . , x n ] of polynomials vanishing on V . Such an ideal is finitely generated by the Hilbert basis theorem.

Let X ⊂ C n and Y ⊂ C m be algebraic sets and K ⊂ C be a subfield. A map α : X → Y is a regular map defined over K if there exists (f 1 , . . . , f m ) ⊂ K[x 1 , . . . , x n ] such that α(y) = (f 1 (y), . . . , f m (y)) for all y ∈ X. A regular map α : X → Y is an isomorphism defined over K if there exists a regular map β : Y → X, defined over K, such that α • β = id Y and β • α = id X , where id Z : Z → Z is the identity map on Z. We refer to [START_REF] Shafarevich | Basic Algebraic Geometry[END_REF] for further details on these notions. The following result is straightforward. Critical points of a polynomial map The following lemma from [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Lemma A.2] provides an algebraic characterization of critical points. Lemma 2.2 (Rank characterization). Let Z ⊂ C n be a d-equidimensional algebraic set and g = (g 1 , . . . , g p ) be generators of I(Z). Let ϕ : Z → C m be a polynomial map, then the following holds.

W • (ϕ, Z) = y ∈ Z | rank(Jac y (g)) = n -d and rank(Jac y ([g, ϕ])) < n -d + m ; K(ϕ, Z) = {y ∈ Z | rank(Jac y ([g, ϕ])) < n -d + m}.
Let us present a direct consequence of this result, which gives a more effective criterion for the singular points of a polynomial map. Let ϕ = (ϕ 1 , . . . , ϕ n ) ⊂ C[x 1 , . . . , x n ] and ϕ i be the deduced map defined as in (1) for 1 ≤ i ≤ n. Lemma 2.3. Let Z ⊂ C n be a d-equidimensional variety and g be a finite set of generators of I(Z).

Then for 1 ≤ i ≤ n, K(ϕ i , Z) is the algebraic subset of Z defined by the vanishing of g and the (p + i)-minors of Jac([g, ϕ i ]), where p = n -d.

Proof. One directly deduces from Lemma 2.2 that K(ϕ i , Z) is exactly the intersection of Z, the zero-set of g, with the set of points y ∈ C n where rank(Jac y ([g, ϕ i ])) < p + i. The latter set is the zero-set of the (p + i)-minors of Jac([g, ϕ i ]). Definition 2.4 (Polar variety). Let Z ⊂ C n be a d-equidimensional algebraic set, and let 1 ≤ i ≤ n. As above, let ϕ = (ϕ 1 , . . . , ϕ n ) ⊂ C[x 1 , . . . , x n ] and ϕ i be the induced map, defined by (ϕ 1 , . . . , ϕ i ). We denote by W (ϕ i , Z) the Zariski closure of W • (ϕ i , Z). It is called a generalized polar variety of Z.

Remark that W • (ϕ i , Z) ⊂ W (ϕ i , Z) ⊂ K(ϕ i , Z) ⊂ Z
by minimality of the Zariski closure. Hence K(ϕ i , Z) = W (ϕ i , Z) ∪ sing(Z) but the union is not necessarily disjoint.

Connectivity and critical values

In this section we consider for n ≥ 1 an equidimensional algebraic set Z ⊂ C n of dimension d > 0.

We are going to prove two main connectivity results on the semi-algebraically connected components of Z ∩ R n through some polynomial map. These results, along with ingredients of Morse theory such as critical loci and critical values of polynomial maps, will be essential in the proof of Theorem 1.1. Most of the results presented here are generalizations of those given in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Section 3] in the unbounded case, replacing projections by suitable polynomial maps.

Connectivity changes at critical values

The main result of this subsection is to prove the following proposition, which deals with the connectivity changes of semi-algebraically connected components in the neighbourhood of singular values of a polynomial map. Let X be a subset of C n , U ⊂ R and f ∈ R[x 1 , . . . , x n ]. With a slight abuse of notation, we still denote by f the polynomial map y ∈ C n → f (y) ∈ C, and we write

X |f ∈U = X ∩ f -1 (U ) ∩ R n . In particular if u ∈ R we note X |f <u = X |f ∈]-∞,u[ , X |f ≤u = X |f ∈]-∞,u] and X |f =u = X |f ∈{u} .
Proposition 3.1. Let ϕ : C n → C be a regular map defined over R. Let A ⊂ R k be a semi-algebraically connected semi-algebraic set, and u ∈ R and

γ : A → Z |ϕ≤u -Z |ϕ=u ∩ K(ϕ, Z)
be a continuous semi-algebraic map. Then there exists a unique semi-algebraically connected component

B of Z |ϕ<u such that γ(A) ⊂ B.
Let us start by recalling a definition from [4, Section 3.5]. Let U ⊂ R k a semi-algebraic open set and V ⊂ R l a semi-algebraic set. The set of semi-algebraic functions from U to V which admit partial derivatives up to order m ≥ 0 is denoted by S m (U, V ). The set S ∞ (U, V ) is the intersection of all the sets S m (U, V ) for m ≥ 0. The ring S ∞ (U, R) is called the ring of Nash functions.

Notation. In this subsection we fix a regular (polynomial) map ϕ : C n → C defined over R. With a slight abuse of notation, the underlying polynomial in R[x 1 , . . . , x n ] will be denoted in the same manner.

We start by proving an extended version of [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Lemma 6]. This can be seen as the founding stone of all the connectivity results presented in this paper. For any y ∈ Z ∩ R n -K(ϕ, Z), it shows the existence of a regular map α : Z → C n+1 such that Z and α(Z) are isomorphic, with

π 1 • α = ϕ on α(Z)
α(Z) ∩ N = (z , f (z )) | z ∈ N ; b) α : Z → α(Z) is an isomorphism of algebraic sets defined over R; c) ϕ • α -1 = π 1 on α(Z). Proof. Let O y ⊂ R n be an open Euclidean neighborhood of y and let g = (g 1 , . . . , g n-d ) be an (n -d)- tuple of polynomials in C[x 1 , . . . , x n ], such that Z ∩ O y = V (g) ∩ O y and Jac y (g) has full rank n -d.
Such a O y and g are given by [7, Proposition 3.3.10] since y is in reg(Z). Also, since y / ∈ W (ϕ, Z), there exists a non-zero (n -d + 1)-minor of Jac y ([g, ϕ]) by Lemma 2.3. Therefore, there exists a permutation σ of {1, . . . , n} such that the matrix

∂g ∂x σ(i) (y) ∂ϕ ∂x σ(i) (y)
d≤j≤n is invertible. Let x 0 be a new variable and define h as the following finite subset of polynomials of

R[x 0 , x 1 , . . . , x n ], h = ( g, ϕ) = g(σ -1 • (x 1 , . . . , x n )), ϕ(σ -1 • (x 1 , . . . , x n )) -x 0 where τ • (x 1 , . . . , x n ) = (x τ (1) , . . . , x τ (n) )
for any permutation τ of {1, . . . , n}. Hence,

V (h) ∩ (R × O y ) = (ϕ(z), σ • z) | z ∈ Z ∩ O y ⊂ R n+1 .

By the chain rule, for any

1 ≤ j ≤ n and z ∈ R n , ∂ g ∂x j (ϕ(z), z) = ∂g ∂x σ(j) (σ -1 • z) and ∂ ϕ ∂x j (ϕ(z), z) = ∂ϕ ∂x σ(j) (σ -1 • z).
Hence, for Jac(f , i) the Jacobian matrix of f with respect to (x i+1 , . . . , x n ), and y = (ϕ(y), σ • y),

Jac y (h, d -1) = Jac y ( g, d -1) Jac y ( ϕ, d -1) = ∂g ∂x σ(i) (y) ∂ϕ ∂x σ(i) (y) d≤j≤n ,
which is invertible by assumption on σ.

Therefore, applying the semi-algebraic implicit function theorem [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Th 3.30

] to h, there is an open Euclidean neighborhoods N ⊂ R d of (ϕ(y), y ) where y = (y σ( ) , 1 ≤ ≤ d -1), an open Euclidean neighborhood N ⊂ R n-d+1 of y = (y σ( ) , d ≤ ≤ n) and a map f = (f 1 , . . . , f n-d+1 ) ∈ S ∞ (N , N )
(since ϕ and the g i 's are polynomials) such that:

∀ z = (z , z ) ∈ N × N , h(z) = 0 ⇐⇒ z = f (z ) Then, let N = (N × N ) ∩ (R × σ • O y ) ⊂ R n+1
, the previous assertion becomes:

(ϕ(z), σ • z) | z ∈ Z ∩ N = (z , f (z )) | z ∈ N (2)
Finally, we claim that taking α : z ∈ Z → (ϕ(z), σ • z) ends the proof. Indeed, by equation ( 2), assertion a) immediately holds since N and N are Euclidean open neighborhood of π d (α(y)) and α(y) respectively. Further, one checks that α is a Zariski isomorphism, of inverse σ -1 after projecting on the last n coordinates, which proves b). Finally, one sees that π 1 • α = ϕ so that c) holds as well.

Remark. The previous lemma shows in particular that

Z ∩ R n -K(ϕ, Z) is a Nash manifold (see [4, Section 3.4]) of dimension d, i.e. locally S ∞ -diffeomorphic to R d . Lemma 3.3. Let y be in Z ∩ R n -K(ϕ, Z
) and u = ϕ(y). Then there exists an open Euclidean neighborhood N (y) of y such that the following holds:

a) N (y) is semi-algebraically connected; b) (Z ∩ N (y)) |ϕ<u is non-empty and semi-algebraically connected; c) (Z ∩ N (y)) |ϕ=u is contained in (Z ∩ N (y)) |ϕ<u .
This result is illustrated by Figure 2.

Proof. Let α, N , N and f be obtained by applying Lemma 3.

2. Let F : z ∈ N → (z , f (z )) ∈ N . Let ε > 0 be such that B = B (π d (α(y)), ε) ⊂ N ⊂ R d where B (π d (α(y)), ε)
is the open ball of R d with radius ε and center π d (α(y)). We claim that taking Besides, remark that F (B) ⊂ α(Z), so that

N (y) = α -1 (F (B)) is enough to prove the result. First, F (
(α(Z) ∩ F (B)) |π1<u = F (B) |π1<u = F (B |π1<u ) x 1 π -1 1 (y 1 ) Z ∩ R n y (Z ∩ N (y)) π 1 <y 1 N (y) Z π 1 <y 1 x 1 π -1 1 (y 1 ) Z ∩ R n y (Z ∩ N (y)) π 1 <y 1 N (y) Z π 1 <y 1 Figure 2: Illustration of Lemma 3.3 where ϕ = π 1 , u = y 1 and Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2
2 ). On the left, y is not critical and one sees that it satisfies all the statements. On the right y is critical, and (Z ∩ N (y)) |π1<y1 is disconnected. Note that in both cases, y 1 is a critical value.

as π 1 (F (z )) = π 1 (z ) for z ∈ N . Since π 1 (α(y)) = ϕ(y) = u,
the semi-algebraic set B |π1<u is nonempty and semi-algebraically connected (since B is convex), and so is its image through F by [4, Section 3.2]. But remark that for all X ⊂ R,

(Z ∩ N (y)) |ϕ∈X = α -1 (α(Z) ∩ F (B)) |π1∈X = α -1 • F (B |π1∈X ), (3)
since ϕ • α -1 = π 1 . Therefore, by Lemma 2.1, (Z ∩ N (y)) |ϕ<u is non-empty and semi-algebraically connected, as claimed in statement b).

To prove assertion c),

remark that B |π1=u is contained in B |π1<u , so that α -1 •F (B |π1=u ) is contained in α -1 • F (B |π1<u ). Since F and α -1 are continuous, α -1 • F B |π1<u ⊂ α -1 • F B |π1<u .
Finally, by (3), we get

(Z ∩ N (y)) |ϕ=u ⊂ (Z ∩ N (y) |ϕ<u . Lemma 3.4. Let y be in Z ∩ R n -K(ϕ, Z), let u = ϕ(y)
and let N (y) as in Lemma 3.3. Then, there exists a unique semi-algebraically connected component B y of Z |ϕ<u such that y ∈ B y . Moreover,

(Z ∩ N (y)) |ϕ<u ⊂ B y .
This lemma is illustrated in Figure 3.

Proof. By the second item of Lemma 3.3, (Z ∩ N (y)) |ϕ<u is non-empty and semi-algebraically connected. Thus, it is contained in a semi-algebraically connected component B y of Z |ϕ<u . Since the semi-algebraically connected components of Z |ϕ<u are pairwise disjoint, B y is well defined and unique.

Moreover by Lemma 3.3,

y ∈ (Z ∩ N (y)) |ϕ<u ⊂ B y .
Finally, suppose that there exists another connected component B of Z |ϕ<u such that y ∈ B . Then y belongs to the closure of B , so that N (y)∩B = ∅, since N (y) is a neighborhood of y. Thus B ∩B y is not empty, and since they are both semi-algebraically connected components of the same set, B = B y .

x 1 π -1 1 (y 1 ) Z ∩ R n y (Z ∩ N (y)) <y 1 N (y) B y x 1 π -1 1 (y 1 ) Z ∩ R n y (Z ∩ N (y)) <y 1 N (y) B y B y Figure 3: Illustration of Lemma 3.4 where ϕ = π 1 , u = y 1 and Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2
2 ). On the left y is not critical and one sees that y ∈ B y and (Z ∩ N (y)) |π1<y1 ⊂ B y . However on the right, y is critical, and one observes that y belongs to both B y and B y , and, in addition, that (Z ∩ N (y)) |π1<y1 is not contained in any of these components. Note that in both cases, y 1 is a critical value.

Let us see a geometric consequence of this result. The following lemma shows that if u is the least element of R such that the hypersurface ϕ -1 ({u}) intersects a semi-algebraically connected component C of Z ∩ R n , then this intersection consists entirely of singular points of ϕ on Z. It is illustrated by We prove now an important consequence of the previous lemma. It is a fundamental property of generalized polar varieties and motivates their introduction among the ingredients of a roadmap.

Proposition 3.6. Let u ∈ R and let B be a bounded semi-algebraically connected component of Z |ϕ<u . Then B ∩ K(ϕ, Z) = ∅.
Proof. Since ϕ is a semi-algebraic continuous map and B is semi-algebraic, then ϕ(B) is a closed and bounded semi-algebraic set by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Theorem 3.23]. In particular, ϕ reaches its minimum ϕ(z) on B and since

∅ = B ⊂ Z |ϕ<u ,then ϕ(z) < u. But B is a semi-algebraically connected component of Z |ϕ<u , so in particular it is closed in Z |ϕ<u , so that B -B ⊂ Z |ϕ=u .
Therefore z ∈ B and as B |ϕ<ϕ(z) is empty (z is a minimizer), B |ϕ=ϕ(z) and z is in K(ϕ, Z) by Lemma 3.5. Finally z ∈ B ∩ K(ϕ, Z), and the latter is non-empty. On the right, ϕ is the square of the Euclidean norm, and Z is a cylinder of radius r. Remark first that C |ϕ<r = ∅. Moreover, for x = (x 1 , x 2 , 0) ∈ Z, the differential at x of restriction of ϕ to Z is the restriction of the projection on the (x 1 , x 2 )-plane to T x Z. Since these two latter planes are orthogonal, x is indeed a critical point.

x 1 x 2 x 3 T y Z Z |π 1 ≤u π 1 (T y Z) Z ∩ R 3 T y Z = π -1 1 (-r) ϕ -1 (ϕ(y)) Z ∩ R 3 C |ϕ=ϕ(y) y = (-r, 0, 0) 0 d y ϕ = -2rπ 1 r x 1 x 2 x 3
We are now able to prove a weaker version of Proposition 3.1, which is illustrated in Figure 5. It deals with the particular case when the map has values in some fiber Z |ϕ=u , where u ∈ R.

a 0 such that γ(N (a 0 )) ⊂ (Z ∩ N (y)) |ϕ=u -K(ϕ, Z).
Hence the map a → B γ(a) is constant on N (a 0 ). Let

B : a ∈ A → B γ(a) ∈ P(Z |ϕ<u )
be the map given by Lemma 3.4, where P(Z |ϕ<u ) denote the power set of Z |ϕ<u . We proved that B is locally constant on A and then, equivalently, continuous for the discrete topology on P(Z |ϕ<u ). But since A is semi-algebraically connected, B(A) is connected for the discrete topology, that is B is constant A.

Let then B be the constant value that B takes on A. By Lemma 3.4, for all a ∈ A, γ(a)

∈ B γ(a) = B, that is γ(A) ⊂ B. Besides, if B is another semi-algebraically connected component of Z |ϕ<u such that γ(A) ⊂ B , then for all a ∈ A, γ(a) ∈ B ∩ B ∩ Z |ϕ=u -K(ϕ, Z), x 1 Z ∩ R n γ(A) B Z |π 1 =u Z |π 1 =u ∩ K(π 1 , Z) x 1 Z ∩ R n γ(A) Z |π 1 =u ∩ K(π 1 , Z) B B Z |π 1 =u
= π 1 and Z is isomorphic to V (x 2 1 + x 2 2 - 1) × V (x 1 + x 2
2 ) in two cases. On the left the γ(A) ∩ (Z |π1=u ∩ K(π 1 , Z)) = ∅ and on the right, this intersection is non-empty. so that B = B by uniqueness in Lemma 3.4.

We can now prove the main proposition by sticking together all the pieces. The points of the map that belong to the fiber Z |ϕ=u are managed by Lemma 3.7, while the remaining ones, in Z |ϕ<u , are more convenient to deal with. This proof is illustrated by Figure 6.

Proof of Proposition 3.1. Since γ is semi-algebraic and continuous, γ(A) is semi-algebraically connected. Hence, if γ(A) ⊂ Z |ϕ<u , it is contained in a unique semi-algebraically connected component B of Z |ϕ<u and we are done.

We assume now that γ(A) We define a map B : A → P(Z |ϕ<u ), where P(Z |ϕ<u ) is the power set of Z |ϕ<u . The family formed by both G 1 , . . . , G N and H 1 , . . . H M is a partition of A; hence, we can define B by defining it on this partition.

⊂ Z |ϕ<u . Let G = γ -1 (Z |ϕ=u ). It is a closed subset of A since Z |ϕ=u is closed in Z |ϕ≤u
H i : Since H i ⊂ A -G, γ(H i ) ⊂ Z |ϕ<u and γ(H i ) is semi-algebraically connected as γ is continuous.
Then, there exists a unique semi-algebraically connected component

B i of Z |ϕ<u such that γ(H i ) ⊂ B i ⊂ B i . G i : Since G i is semi-algebraically connected and γ(G i ) ⊂ Z |ϕ=u -K(ϕ, Z), Lemma 3.7 with A = G i states that there is a unique semi-algebraically connected component B i of Z |ϕ<u such that γ(G i ) ⊂ B i .
Therefore, for all a ∈ A, let B such that

B(a) = B i if a ∈ H i B i if a ∈ G i so that γ(a) ∈ B(a).
Let us show that B is locally constant, that is, for every a ∈ A, there exists an open Euclidean neighborhood N (a) ⊂ A of a, such that for all a ∈ N (a), B(a ) = B(a). Then, we will conclude by connectedness as above. Let a ∈ A and 1 ≤ i ≤ max(M, N ).

• If a ∈ H i , since H i is open in A,
there exists an open Euclidean neighborhood N (a) of a contained in H i . By construction, for all a ∈ N (a), B(a ) = B(a). Moreover, since H i is semi-algebraically connected, this also proves that B is actually constant on H i , and we let B(H i ) be the unique value it assumes on H i .

• Else a ∈ G i , since the G j 's are closed in A, then a does not belong to the closure of any other G j , j = i. However, the set

J = 1 ≤ j ≤ M | a ∈ H j
is not empty. By construction, γ(a) ∈ B(a) and by definition of J, for every j ∈ J, γ(a) ∈ B(H j ). But, by Lemma 3.4 applied with y = γ(a), such a semi-algebraically connected component is unique. Hence for all j ∈ J, B(H j ) = B(a). One can then take N (a) = B(a, r) with r > 0 such that this open ball intersects either the H j 's for j ∈ J or G i , and only them.

Finally, we proved that B is locally constant and then, equivalently, continuous for the discrete topology on P(Z |ϕ<u ). Since A is semi-algebraically connected, B(A) is connected for the discrete topology and B is constant on A. Denoting by B ⊂ Z |ϕ<u the unique value it assumes, we have

γ(A) ⊂ B as claimed. Besides if B is another semi-algebraically connected component of Z |ϕ<u such that γ(A) ⊂ B , then in particular B ∩ B contains γ(G 1 ) ⊂ Z |ϕ=u -K(ϕ, Z), so that B = B by Lemma 3.7. x 1 Z ∩ R n G 1 H 1 H 2 B Z |π 1 =u Z |π 1 =u ∩ K(π 1 , Z) x 1 Z ∩ R n Z |π 1 =u ∩ K(π 1 , Z) G 1 H 1 H 2 B B Z |π 1 =u
is isomorphic to V (x 2 1 + x 2 2 - 1) × V (x 1 + x 2 2 ) in two cases. The intersection γ(A) ∩ (Z |π1=u ∩ K(π 1 , Z)
) is empty on the left while, on the right, it is not.

We then deduce the following consequence on the semi-algebraically connected components of Z with respect to ϕ. This result is illustrated in Figure 7.

x 1 π -1 1 (u) Z ∩ R n C π 1 <u C x 1 π -1 1 (u) Z ∩ R n C π 1 <u C Figure 7: Illustration of Corollary 3.8 where ϕ = π 1 and Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2 2
). On the left Z |π1=u ∩ K(π 1 , Z) = ∅ and one sees that C |π1<u is still a semi-algebraically connected component of Z |π1<u . On the right Z |π1=u ∩ K(π 1 , Z) = ∅ and one sees that C |π1<u is disconnected.

Fibration and critical values

As in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Section 3.2] we are going to use a Nash version of Thom's isotopy lemma, stated in [START_REF] Coste | Nash triviality in families of nash manifolds[END_REF], which, again, is an ingredient of Morse theory. We refer to [4, Section 3.5] for the definitions of Nash diffeomorphisms, manifolds and submersions together with their properties. Proposition 3.9. Let ϕ : C n → C be a regular map defined over R and A ⊂ ϕ -1 ((-∞, w)) ∩ R n be a semi-algebraically connected semi-algebraic set. Let v < w such that A |ϕ∈(v,w) is a non-empty Nash manifold, bounded, closed in ϕ -1 ((v, w)) ∩ R n and such that ϕ is a submersion on A |ϕ∈(v,w) . Then for all u ∈ [v, w), A |ϕ≤u is non-empty and semi-algebraically connected.

Proof. We first prove that ϕ : A |ϕ∈(v,w) → (v, w) is a proper surjective submersion. Since A |ϕ∈(v,w) is bounded and ϕ is semi-algebraic and continuous, ϕ : A |ϕ∈(v,w) → (v, w) is a proper map. Let us prove that ϕ is also surjective on A |ϕ∈(v,w) that is

ϕ(A |ϕ∈(v,w) ) = (v, w).
By assumption, ϕ is a submersion from A |ϕ∈(v,w) to (v, w). Then by the semi-algebraic inverse function theorem [4, Proposition 3.29], ϕ is an open map. Besides, as A |ϕ∈(v,w) is closed and bounded, there exists a closed and bounded semi-algebraic set

X ⊂ R n such that A |ϕ∈(v,w) = X ∩ ϕ -1 ((v, w)) = X |ϕ∈(v,w) . Then ϕ(A |ϕ∈(v,w) ) = ϕ(X |ϕ∈(v,w) ) = ϕ(X) ∩ (v, w).
Ψ : A |ϕ∈(v,w) -→ (v, w) × A |ϕ=ζ y -→ ( ϕ(y) , ψ(y)
) .

We now proceed to prove the main statement of the proposition. There are, at first sight, two different situations to consider: whether u > v or u = v (see Figure 8). Using Puiseux series, we actually prove them simultaneously. Take u ∈ [v, w); we prove that A |ϕ≤u is non-empty and semi-algebraically connected. To prove that A |ϕ=u is non-empty, we consider z ∈ A |ϕ=ζ and the map

γ : [0, 1) → A |ϕ∈(v,w) t → Ψ -1 (tu + (1 -t)ζ, z).
This map is well defined and continuous, since We prove now that A |ϕ≤u is semi-algebraically connected. Consider two points y and y in A |ϕ≤u . Since A is semi-algebraically connected by assumption, there exists a continuous path γ : [0, 1] → A such that γ(0) = y and γ(1) = y . Let us construct, from γ, another path that lies in A |ϕ≤u .

Ψ
Let ε be an infinitesimal, and let R = R ε be the field of algebraic Puiseux series in ε (see [4, Section 2.6]). We denote by A , (v, w) , Ψ , ψ , ϕ and γ the extensions of respectively A, (v, w), Ψ, ψ, ϕ and γ to R in the sense of [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 2.108]. According to [4, Exercise 2.110], Ψ :

A |ϕ∈(v,w) → (v, w) ×A |ϕ=ζ is a bijective map. Then let g : [0, 1] ⊂ R → A be such that g (t) = γ (t) if ϕ (γ (t)) ≤ u + ε, g (t) = Ψ -1 (u + ε, ψ (γ (t))) if u + ε ≤ ϕ (γ (t)) < w.
This map is well defined since u

+ ε ∈ (v, w) and if ϕ (γ (t)) = u + ε, then Ψ -1 (u + ε, ψ (γ (t))) = γ (t).
Moreover g is a continuous semi-algebraic map since by [4, Exercise 3.4], Ψ -1 , ψ and γ are continuous semi-algebraic maps. Finally one observes that g is bounded over R. Indeed if ϕ (γ (t)) ≤ u + ε, then g (t) = γ(t), which is continuous on [0, 1] and then bounded over R. Else ϕ (γ (t)) ∈ (v, w) and g (t) ∈ A |ϕ∈(v,w) , which is bounded over R by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 3.19] since A |ϕ∈(v,w) is. Hence, its image G = g ([0, 1] ) is a semialgebraically connected semi-algebraic set, bounded over R and contained in A |ϕ≤u+ε .

Let G = lim ε G . By [4, Proposition 12.49], G is a closed and bounded semi-algebraic set. Then, since ϕ is a continuous semi-algebraic map defined over G, by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Lemma 3.24] for all z ∈ G ,

ϕ(lim ε z ) = lim ε ϕ(z ) ≤ lim ε (u + ε) = u
So that G is contained in A |ϕ≤u . In addition, since G is semi-algebraically connected and bounded over R, then by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 12.49], G is semi-algebraically connected and contains y = lim ε g(0) and y = lim ε g [START_REF] Bank | Generalized polar varieties and an efficient real elimination[END_REF]. We deduce that there exists, inside G, a semi-algebraic path connecting y to y in A |ϕ≤u , which ends the proof.

The following result is a consequence of Proposition 3.9 as it deals with a particular case. An illustration of this statement can be found in Figure 9. First we need to prove that C |ϕ<w is a non-empty semi-algebraically connected semi-algebraic set. Since Z |ϕ=w ∩ K(ϕ, Z) = ∅, by Corollary 3.8 C |ϕ<w is a semi-algebraically connected component of Z |ϕ<w . Hence it is non-empty and semi-algebraically connected.

Then, we need to prove that C |ϕ∈(v,w) is a non-empty Nash manifold, bounded and closed in

ϕ -1 ((v, w)) ∩ R n . Suppose first that C |ϕ∈(v,w) = ∅. Then C |ϕ≤v ∪ C |ϕ=w = C and C |ϕ≤v ∩ C |ϕ=w = ∅. x 1 Z ∩ R n Z w Z u Z v Ψ y y γ g K(π 1 , Z) x 1 Z ∩ R n Z w Z v+ε Z v Ψ y y' g K(π 1 , Z)
A = Z |π1<w , where Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2 2
). The two cases are quite similar; we consider here the one where v is a critical value. One sees that Ψ connects all the slices A |π1=u for u ∈ (v, w) . This diffeomorphism allows to transform the problematic parts (not in A |π1≤u ) of the initial path γ (in green), into another path g (in red), that lies in

A |π1=u ⊂ A |π1≤u .
Since C is semi-algebraically connected, either C |ϕ≤v or C |ϕ=w is empty (as they are both closed in C). In both cases our conclusion follows. It remains to tackle the case where C |ϕ∈(v,w) is not empty, which we assume to hold from now on.

We prove that

C |ϕ∈(v,w) is bounded. Observe that C |ϕ∈(v,w) ⊂ C |ϕ∈[v,w] = C ∩ R n ∩ ϕ -1 ([v, w]).
Recall that ϕ is proper on Z ∩ R n by assumption, and thus on C ∩ R n . Hence,

C |ϕ∈[v,w] is bounded. Besides C |ϕ∈(v,w) is closed in ϕ -1 ((v, w)) ∩ R n as C |ϕ∈(v,w) = C ∩ ϕ -1 ((v, w)) ∩ R n ,
and C is closed in R n as it is closed in the closed set Z |ϕ≤w . Since C |ϕ∈(v,w) ∩ K(ϕ, Z) = ∅ then by [START_REF] Bochnak | Real algebraic geometry[END_REF]Proposition 3.3.11], C |ϕ∈(v,w) is a Nash manifold of dimension dim(Z).

To apply Proposition 3.1, it remains to prove that ϕ is a Nash submersion on

C |ϕ∈(v,w) . Let y ∈ C |ϕ∈(v,w) . Since y / ∈ sing(Z), then T y C |ϕ∈(v,w) = T y Z ∩ R n according to [7, Proposition 3.3.11]. Since C |ϕ∈(v,w) ∩ K(ϕ, Z) = ∅, d y ϕ is onto on T y Z and since dim Z > 0, the image d y ϕ(T y Z) is C. Hence d y ϕ(T y C |ϕ∈(v,w) ) = R.
We just established that all the assumptions of Proposition 3.9 are satisfied. One can then apply it to C |ϕ<w and conclude that C |ϕ≤v is non-empty and semi-algebraically connected. Finally, since C is a semi-algebraically connected component of Z |ϕ≤w , any semi-algebraically connected component of

Z |ϕ≤v contained in C is contained in C |ϕ≤v . Thus C |ϕ≤v is a semi-algebraically connected component of Z |ϕ≤v .

Proof of the main connectivity result

Recall that ϕ = (ϕ 1 , . . . , ϕ n ) ⊂ R[x 1 , . . . , x n ] and for 1 ≤ i ≤ n, ϕ i : y → (ϕ 1 (y), . . . , ϕ i (y)). We denote by W i = W (ϕ i , V ) the Zariski closure of the set of critical points of the restriction of ϕ i to V and recall that

K i = W (ϕ 1 , V ) ∪ S i ∪ sing(V )
and

F i = ϕ -1 i-1 (ϕ i-1 (K i )) ∩ V,
where S i is a given subset of V . We suppose that the following assumptions hold:

x 1 π -1 1 (w) Z ∩ R n π -1 1 (v) C C π 1 ≤v x 1 π -1 1 (w) Z ∩ R n π -1 1 (v) C C π 1 ≤v
Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2
2 ) in two cases. On the left Z |π1∈(v,w) ∩ K(π 1 , Z) = ∅ and we see that C |π1≤v is still a semi-algebraically connected component of Z |π1≤v . On the right Z |π1∈(v,w) ∩ K(π 1 , Z) contains a point and we see that C |π1≤v is semi-algebraically disconnected.

(A) V is d-equidimensional and its singular locus sing(V ) is finite;

(P) the restriction of the map ϕ 1 to V ∩ R n is proper and bounded from below; (B 1 ) W i is either empty or (i -1)-equidimensional and smooth outside sing(V ); (B 2 ) for any y = (y 1 , . . . ,

y i ) ∈ C i , V ∩ ϕ -1 i-1 (y) is either empty or (d -i + 1)-equidimensional; (C 1 ) S i is finite; (C 2 ) S i has a non-empty intersection with every semi-algebraically connected component of W (ϕ 1 , W i )∩ R n .
Then the goal of this section is to prove that W i ∪ F i intersects each semi-algebraically connected component of V ∩ R n and that their intersection is semi-algebraically connected.

Let R = F i ∪ W i . We prove that the following so-called roadmap property holds: Proof. Let C be a semi-algebraically connected component of V ∩ R n . Since C is non-empty and semialgebraically connected, there exist y and y in C, and a semi-algebraic path γ :

RM: "For any semi-algebraically connected component C of V ∩ R n , the set C ∩ R
[0, 1] → C connecting them. Let u = max{ϕ 1 (γ(t)), t ∈ [0, 1]} ∈ R.
Such a maximum u exists by continuity of γ and ϕ 1 , since [0, 1] is closed and bounded, and it follows that γ([0, 1]) ⊂ V |ϕ 1 ≤u . Since γ([0, 1]) is semi-algebraically connected, there exists a (unique) semi-algebraically connected component B of V |ϕ 1 ≤u containing γ([0, 1]). In particular, B contains y and y . Since RM(u) holds by assumption, then B ∩ R is non-empty. But as y ∈ B ∩ C and B is semialgebraically connected, C contains B. Finally, C ∩ R contains B ∩ R and the former is non-empty. We can suppose now, in addition, that y and y are in C ∩ R, and let B be defined as above. Then, y and y are in B ∩ R, which is semi-algebraically connected by RM(u). Therefore y and y are connected by a semi-algebraic path in B ∩ R. Since B ⊂ C, y and y are semi-algebraically connected in C ∩ R. In conclusion, C ∩ R is semi-algebraically connected and RM holds.

Remark. The previous lemma trivially holds in the case of [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14], since V ∩ R n is assumed to be bounded. Indeed, in this case, considering u = max y∈V ∩R n ϕ 1 (y), one has

V |ϕ 1 ≤u = V ∩ R n .

Restoring connectivity

Before proving RM(u) for all u ∈ R, we need to prove the following result, which constitutes the core of the proof of Theorem 1.1. This proposition shows that the connectivity property of our roadmap candidate is satisfied when u is increasing towards singular points of ϕ 1 on V . This is ensured by the addition of the fibers F i . Proposition 4.2. Let u ∈ R and C be a semi-algebraically connected component of V |ϕ 1 ≤u such that C |ϕ 1 <u is non-empty. Let B be a semi-algebraically connected component of C |ϕ 1 <u , then:

1. B ∩ (F i ∪ W i ) is non-empty; 2. Any point y ∈ B ∩ (F i ∪ W i ) can be connected to a point z ∈ B ∩ (F i ∪ W i ) by a semi-algebraic path in B ∩ (F i ∪ W i ).
Let us begin with a technical lemma:

Lemma 4.3. Let K be a real closed field containing R and K be its algebraic closure. Let Z ⊂ K n be a d-equidimensional algebraic set, where d > 0. Assume that for any z

∈ K i-1 , Z ∩ ϕ -1 i-1 (z) is either empty or (d -i + 1)-equidimensional.
Let B be a bounded semi-algebraically connected component of Z ∩ K n and let y ∈ B. Let H be the semi-algebraically connected component of B ∩ ϕ -1 i-1 (ϕ i-1 (y)) containing y. Then, the intersection

H ∩ K(ϕ i , Z) is not empty. Proof. Let Y = Z ∩ ϕ -1 i-1 (ϕ i-1 (y)).
By assumption, Y is an equidimensional algebraic set of dimension

d -i + 1. Besides, H is a bounded semi-algebraically connected component of Y ∩ K n , since B is a bounded semi-algebraically connected component of Z ∩ K n .
Recall that ϕ = (ϕ 1 , . . . , ϕ n ). Then ϕ i (H) ⊂ R is a closed and bounded semi-algebraic set by [4, Theorem 3.23]. In particular, ϕ i reaches its minimum on H. Let z ∈ H be such that ϕ i (z) = min ϕ i (H), so that H |ϕi<ϕi(z) is empty. Then, by Lemma 3.5,

z ∈ H ∩ K(ϕ i , Y ). Let g ⊂ K[x 1 , . . . , x n ] be a sequence of generators of I(Z), so that Y = V (g, ϕ i-1 -ϕ i-1 (y)). Since Y is (d -i + 1)-equidimensional, Lemma 2.2 establishes that z is such that rank   Jac z (g) Jac z (ϕ i-1 ) Jac z (ϕ i )   < n -(d -(i -1)) + 1. Since ϕ i = (ϕ i-1 , ϕ i ), one deduces that rank Jac z (g) Jac z (ϕ i ) < n -d + i,
which means that z ∈ H ∩K(ϕ i , Z). Finally, the latter set is non-empty and the statement is proved.

Notation. For the rest of the subsection let u, C and B as defined in Proposition 4.2.

Let us deal with one particular case of the second item of Proposition 4.2.

Lemma 4.4. Let y be in B ∩ F i . Then, there exists a point z ∈ B ∩ (F i ∪ W i ) and a semi-algebraic path in B ∩ (F i ∪ W i ) connecting y to z.

Proof. Let y be in ∈ B ∩ F i . We assume that y / ∈ B so that ϕ 1 (y) = u, otherwise taking z = y would end the proof. Since y ∈ B, by the curve selection lemma [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Th. 3.22], there exists a semi-algebraic path γ : [0, 1] → R n such that γ(0) = y and γ(t) ∈ B for all t ∈ (0, 1]. Let ε be an infinitesimal, R = R ε be the field of algebraic Puiseux series and ψ = (ψ 1 , . . . , ψ n ) be the semi-algebraic germ of γ at the right of the origin (see [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Section 3.3]). According to [4, Theorem 3.17], we can identify ψ with an element of (R ) n (by a slight abuse of notation, we will denote them in the same manner). Hence by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 3.21], lim ε ψ = y. Let finally

H = ext(B, R ) ∩ ϕ -1 i-1 (ϕ i-1 (ψ)) ⊂ (R ) n
where ext(B, R ) is the extension of B to R and ϕ j for 1 ≤ j ≤ n, with some notation abuse, still denote the extension of ϕ j to R . Since γ((0, 1)) ⊂ B, by [4, Proposition 3.19], ψ is in ext(B, R ). Hence, ψ in H and H is non-empty. Moreover B is bounded since ϕ 1 : V ∩ R n → R is a proper map bounded below by assumption (P). Then [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 3.19] states that ext(B, R ) and then H are bounded over R. Hence the map lim ε is well defined on H and

y ∈ lim ε H = {lim ε y , y ∈ H} ⊂ R n .
Finally, as ϕ i-1 is semi-algebraic and continuous,

lim ε H is contained in B ∩ϕ -1 i-1 (ϕ i-1 (y)) by [4, Lemma 3.24]. But y ∈ F i , so that ϕ -1 i-1 (ϕ i-1 (y)) ⊂ ϕ -1 i-1 (ϕ i-1 (K i )), and finally lim ε H is actually in B ∩ F i .
Let H 1 be the semi-algebraically connected component of H containing ψ. By [4, Proposition 5.24], lim ε H 1 is the semi-algebraically connected component of lim ε H containing y. Actually, we just proved that every w in lim ε H 1 can be semi-algebraically connected to y into B ∩ F i . We find now some w ∈ lim ε H 1 that can be connected to a point z ∈ B ∩ (F i ∪ W i ) to end the proof. Such a w must be the origin of a germ of semi-algebraic functions that lies in B ∩ (W i ∪ F i ).

By assumption (A), V is d-equidimensional. By assumption (B 2 ), for all z ∈ V , the algebraic set

V ∩ ϕ -1 i-1 (ϕ i-1 (z)) is (d -i + 1)-equidimensional.
Then, if we denote by C the algebraic closure of R , it is an algebraic closed extension of C, so that the algebraic sets of (C ) n

Z = z ∈ (C ) n | ∀h ∈ I(V ), h(z) = 0 and Z ∩ ϕ -1 i-1 (ϕ i-1 (ψ)))
are equidimensional of dimension respectively d and (d -i + 1). Since B is a semi-algebraically connected component of V |ϕ 1 <u , then, by [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Proposition 5.24], ext(B, R ) is a semi-algebraically connected component of

ext(V |ϕ 1 <u , R ) = ext(V ∩ R n , R ) |ϕ 1 <u = Z |ϕ 1 <u , by [4, Transfer Principle, Th. 2.98]. Then, since H 1 is a semi-algebraically connected component of H = ext(B, R ) ∩ ϕ -1 i-1 (ϕ i-1 (ψ))
, one can apply Lemma 4.3 on Z with K = R . Hence

H 1 ∩ K(ϕ i , Z) = ∅.
By Lemma 2.3, K(ϕ i , Z) is defined over R as V and ϕ i are. Then, by [4, Transfer Principle, Th. 2.98],

K(ϕ i , Z) ∩ (R ) n = ext(K(ϕ i , V ) ∩ R n , R ), so that ∅ H 1 ∩ ext(K(ϕ i , V ) ∩ R n , R ) ⊂ ext(B ∩ K(ϕ i , V ), R ).
Therefore let ζ ∈ ext(B ∩ K(ϕ i , V ), R ), let w = lim ε ζ and τ be a representative of ζ on (0, t 0 ), where t 0 > 0. By [4, Proposition 3.21], we can continuously extend τ to 0 such that τ (0) = w. Besides for all t ∈ (0, t 0 ),

τ (t) ∈ B ∩ K(ϕ i , V ) ⊂ B ∩ (W i ∪ F i ). Then τ ([0, t 0 )) ⊂ B ∩ (F i ∪ W i ) so that w ∈ B ∩ (F i ∪ W i ) and z = τ (t 0 /2) ∈ B ∩ (F i ∪ W i ).
Besides, since w ∈ lim ε H 1 we have seen that it can be connected to y a semi-algebraic path in B ∩ (F i ∪ W i ). In the end, there exist two consecutive paths into B ∩ (F i ∪ W i ), connecting y to w, and w to z ∈ B ∩ R (namely τ ).

x

x 1 Z ∩ R n B F i W i lim ε H 1 ψ γ y g ζ z w H 1
ϕ 1 = π 1 and V is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 -x 2
2 ). Elements of H 1 can be seen as curves of infinitesimal lengths, starting from a point of lim ε H 1 , and lying in B. Here, lim ε H 1 is the set of points that share the same first coordinate than y. Hence, the above proof consisted in choosing a ζ in H 1 , that lives "inside" W i ∪ sing(V ) (actually in ext(W i ∪ sing(V ), R ε )).

We can now prove Proposition 4.2. This proof is illustrated by Figure 10.

Proof of Proposition 4.2. Let B be a semi-algebraically connected component of C |ϕ 1 <u . Since ϕ 1 is a proper map bounded from below on V ∩ R n by assumption P, C |ϕ 1 <u , and then B, are bounded. Then applying Proposition 3.6 shows that:

∅ B ∩ K(ϕ 1 , V ) ⊂ B ∩ F i ⊂ B ∩ (F i ∪ W i ).
The first item is then proved. Let y ∈ B ∩ (F i ∪ W i ). To prove the second item, one only needs to consider the case where y ∈ B ∩ (W i -F i ) according to Lemma 4.4. Moreover one can assume that y / ∈ B and then ϕ 1 (y) = u, otherwise, taking z = y, would end the proof.

Let D be the semi-algebraically connected component of (W i ) |ϕ 1 ≤u containing y. We consider two disjoint cases.

u = max ϕ 1 (γ(t)) | t ∈ [0, 1] ,
so that γ([0, 1]) ⊂ V |ϕ 1 ≤u . Such a u exists by continuity of γ, and satisfies u < u, as [0, 1] is closed and bounded.

Let B be the semi-algebraically connected component of B |ϕ 1 ≤u that contains γ([0, 1]). Since B is also a semi-algebraically connected component of V |ϕ 1 ≤u , property RM(u ) states that B ∩ R is nonempty and semi-algebraically connected. Then, as z and z are in B ∩ R, they can be connected by a semi-algebraic path in B ∩ R, and then, in B ∩ R. Thus y and y are connected by a semi-algebraic path in B ∩ R and we are done.

Recursive proof of the truncated roadmap property

In order to prove that RM(u) holds for all u ∈ R, one can consider two disjoint cases: whether u is a real singular value of ϕ 1 , that is u ∈ ϕ 1 (K i ), or not. The following lemma allows us to proceed by induction.

Lemma 4.6. The set ϕ 1 (K i ) is non-empty and finite.

Proof. By the algebraic version of Sard's theorem [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Proposition B.2], the set of critical values of ϕ 1 on V is an algebraic set of C of dimension 0. Then, it is either empty or non-empty but finite. Hence, ϕ 1 (K i ) is either empty or non-empty but finite, as S i and sing(V ) are, by assumption. Moreover since ϕ 1 is a proper map bounded from below on V ∩ R n by assumption (P), for any u ∈ R, Z |ϕ<u is bounded. Then, since V is not empty, by Proposition 3.6 the sets K(ϕ 1 , V ) and then ϕ 1 (K i ) are not empty.

We denote by v 1 < . . . < v the points of ϕ 1 (K i ∩ R n ) and, in addition, let v +1 = +∞. We proceed by proving the two following steps.

Step 1: Let u ∈ R, if RM(u ) holds for all u < u, then RM(u) holds.

Step 2: Let j ∈ {1, . . . , }, if RM(v j ) holds, then for all u ∈ (v j , v j+1 ), RM(u) holds.

Remark that, by Lemma 3.5, v 1 = min V ∩R n ϕ 1 , since V ∩ R n is closed. Then for u < v 1 , V |ϕ≤u = ∅ and RM(u ) trivially holds. Hence, proving these two steps is enough to prove RM(u) for all u in R, by an immediate induction.

x 1 Z ∩ R n C F i W i γ(H 1 ) τ ([0, 1]) y y' Figure 11: Illustration of proof of 4.7 with ϕ = π 1 and V is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 -x 2
2 ). Here, only y belongs to C |π1=u ∩ K(π 1 , V ). Then we replace the path γ = γ |H1 by a path τ 1 that lies in the intersection of the roadmap and the semi-algebraically connected component C.

Then using Corollary 3.10, one deduces that C |ϕ 1 ≤vj is a semi-algebraically connected component of V |ϕ 1 ≤vj . Hence, by property RM(v j ), the set C |ϕ 1 ≤vj ∩R is non-empty and semi-algebraically connected. In particular, C ∩ R is non-empty.

Let us now prove that C ∩ R is semi-algebraically connected. Let y be in C ∩ R. According to the previous paragraph, one just need to be able to connect y to a point z of C |ϕ 1 ≤vj ∩ R by a semi-algebraic path in C ∩ R and then apply RM(v j ). First, if y ∈ C |ϕ 1 ≤vj ∩ R, there is nothing to do. Suppose now that y ∈ C |ϕ 1 ∈(vj ,u] ∩ R. We claim that actually

y ∈ C ∩ W i .
Indeed, if y ∈ C ∩ F i , then ϕ i-1 (y) ∈ ϕ i-1 (K i ) and ϕ 1 (y) would be one of the v 1 , . . . , v .

Let D be the semi-algebraically connected component of (C ∩ W i ) |ϕ 1 ≤u containing y. Remark that D is a semi-algebraically connected component of (W i ) |ϕ 1 ≤u , as it contains y and is contained in C. Since ϕ 1 (W (ϕ 1 , W i )) is finite by Sard's lemma, we get that ϕ 1 (W (ϕ 1 , W i )) ⊂ ϕ 1 (S i ), by assumption (C 2 ), so that

(v j , u) ∩ ϕ 1 (W (ϕ 1 , W i )) = ∅.
Since W i is equidimensional and smooth outside sing(V ), then by Corollary 3.10, D |ϕ 1 ≤vj is a semialgebraically connected component of (W i ) |ϕ 1 ≤vj . Therefore, let z ∈ D |ϕ 1 ≤vj . Since D is semialgebraically connected, there exists a semi-algebraic path, connecting y

∈ D ⊂ C ∩ R to z ∈ D |ϕ 1 ≤vj ⊂ C |ϕ 1 ≤vj ∩ R in D ⊂ C ∩ R.
We are done.

Conclusions and perspectives

We illustrate below two ways of using Theorem 1.1 in order to generalize the algorithms of [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] to the case of unbounded smooth real algebraic sets. Let V ⊂ C n be an equidimensional algebraic set of dimension d given as the solutions of some polynomials f 1 , . . . , f p in Q[x 1 , . . . , x n ]. Assume that sing(V ) is finite. Take

ϕ 1 = n k=1 (x k -a k ) 2 and for 2 ≤ j ≤ n ϕ j = n k=1 b j,k x k , x x 1 Z ∩ R n C π 1 ≤v j C W i D D y z y' z' Figure 12: Illustration of proof of 4.8 with ϕ 1 = π 1 and V is isomorphic to V (x 2 1 + x 2 2 - 1) × V (x 1 -x 2
2 ). We connect the points y and y in C ∩ W i to respectively z and z in C |π1≤vj . Then we are reduced to the case of Step 1.

where a = (a 1 , . . . , a n ) ∈ Q n and, for 2 ≤ j ≤ n, b j = (b j,1 , . . . , b j,n ) ∈ Q n . Then, assumption (P) holds. Also, according to [START_REF] Bank | Generalized polar varieties: Geometry and algorithms[END_REF][START_REF] Bank | On the geometry of polar varieties[END_REF], for a generic choice of a and b, the dimension properties of assumption (B) do hold.

For some chosen 2 ≤ i ≤ d, let W i and F i be respectively the polar variety and set of fibers as defined in the introduction. One can compute a set S ⊂ W (ϕ 1 , W i ) ⊂ V by using any algorithm such as [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Chap. 13] or [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF], returning sample points in all connected components of real algebraic sets.

Hence, one can apply Theorem 1.1 to V , ϕ and i. We deduce that W i ∪ F i has a non-empty and connected intersection with all connected components of V ∩R n , but it is in general an object of dimension greater than 1, so more work is needed.

Our first option is to recursively perform similar operations, using this time polynomials defining respectively W i and F i , eventually building a roadmap for V itself (this is justified by [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Prop. 2]). This requires that both W i and F i are equidimensional with finitely many singular points.

The cost of the whole procedure will depend on the degrees of W i and F i . Denote by D the degrees of the f i 's and by δ (resp. σ) the degree of V (resp. S); using [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Chap. 13] gives σ ∈ D O(n) . Assuming that d = n -p and that the ideal generated by f 1 , . . . , f p is radical, one can apply Heintz's version of the Bézout theorem [START_REF] Heintz | Definability and fast quantifier elimination in algebraically closed fields[END_REF] as in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF] to deduce that δ ≤ D p and that the degree of W i is bounded by δ(nD) n-p ∈ (nD) O(n) . Similarly, one can expect that the degree δ of W (ϕ 1 , W i ) lies in (nD) O(n) by applying similar arguments to those used in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]. Since the degree of F i is bounded by the product of δ and δ + σ, we deduce that its degree also lies in (nD) O(n) .

Hence, as explained in [START_REF] El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF], the overall complexity of such recursive algorithms is (nD) O(nr) , where r is the depth of the recursion, provided that the involved geometric sets do satisfy the properties needed by Theorem 1.1 and can be represented and computed with algebraic data within complexities which are polynomial in their degrees.

To understand the possible depth of recursion one could expect, one also needs to have a look at the dimensions of W i and F i . Observe that W i is expected to have dimension i -1. Similarly, F i is expected to have dimension d -(i -1). Taking i dim(V ) 2

will decrease the dimensions of W i and F i to dim(V ) 2

if they are not empty (this will require coordinates). Hence the depth r of this new recursive roadmap algorithm will be bounded by log 2 (n).

A second approach to design our new algorithm takes i = 2. Then, W 2 is expected to have dimension 1 (or be empty), so no further computation is needed. On the other hand, F 2 still has dimension d -1, but a key observation is that F 2 is now bounded. Then, one can directly apply a slight variant of the algorithm in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] taking F 2 as input: that algorithm already keeps the depth of recursion bounded by log 2 (n), but we should now handle the fact that we work in the hypersurface ϕ -1 1 (ϕ 1 (K 1 )). Again, all of this is under the assumption that one can make F 2 satisfy the assumptions of Theorem 1.1.

We will investigate that approach in a forthcoming paper. Thus, the next steps to obtain nearly optimal algorithms for computing roadmaps of smooth real algebraic sets, without compactness assumptions, are:

• to study how the constructions of generalized Lagrange systems introduced in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] for encoding polar varieties associated to linear projections can be reused in our context;

• to prove that assumption (B) holds for some generic choice of a and b for our polar varieties, which by contrast to those used in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] are no more associated to linear projections;

• to prove that the variant of the algorithm designed in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] discussed above still has a complexity similar to the one obtained in [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF].

The example below illustrates how this whole machinery might work and how Theorem 1.1 can already be used. Let ϕ = ((x 1 -1) 2 + x 2 2 + x 2 3 , x 1 , x 2 ) ⊂ Q[x 1 , x 2 , x 3 ]. As the restriction of ϕ 1 to R n is the square of the Euclidean distance to (1, 0, 0), (P) is satisfied. Since 2 ≤ i ≤ d, we must take i = 2. Then we see that one can write W 2 = V (f, (3x 1 x 3 + 1)(x 1 -x 3 ) + 3x 2 3 -1). One checks that W 2 is 1-equidimensional and has no singular point as well, so that (ϕ, 2) satisfies (B 1 ). Let K 2 = W • (ϕ 1 , W 2 ), which is a finite set of cardinality 45 (of which 5 are real). Besides, for any α ∈ C, V ∩ ϕ -1 1 (α) = V (f, (x 1 -1) 2 + x 2 2 + x 2 3 -α) is either empty or an equidimensional algebraic set of dimension 1. Therefore, (ϕ, 2) satisfies (B). Finally, since W • (ϕ 1 , W 2 ) ∩ R 3 is a finite set, assumption (C) holds vacuously. Recall that, by definition, F 2 = ϕ 1 -1 (ϕ 1 (K 2 )) ∩ V . In conclusion, by Theorem 1.1, W 2 ∪ F 2 is a 1-roadmap of (V, ∅). We expect that algorithmic progress on the computation of roadmaps for real algebraic and semialgebraic sets will lead to implementations that will automate the analysis of kinematic singularities for e.g. serial and parallel manipulators. In particular, there are many families of robots where these algorithms could be used if scale enough. This is the case for e.g. 6R manipulators (see e.g. the results on the number of aspects in [START_REF] Wenger | Cuspidal and noncuspidal robot manipulators[END_REF] which need to be extended) in the context of serial manipulators, for the study of self-motion spaces of parallel platforms such as Gough-Stewart ones (the case of such manipulators with 6 lengths still remains open, see e.g. [START_REF] Nawratil | Self-motions of pentapods with linear platform[END_REF]) and for the identification of cuspidality manipulators (see [START_REF] Chablat | Deciding cuspidality of manipulators through computer algebra and algorithms in real algebraic geometry[END_REF] for a general approach, relying on roadmap algorithms). For some of these applications, one needs to compute the number of connected components of semi-algebraic sets defined as the complement of a real hypersurface defined by f = 0 where f is a multivariate polynomial. Note that this can be done by computing a roadmap for the (non-bounded) real algebraic set defined by tf -1 = 0 where t is a new variable. This illustrates the potential interest of the algorithms that would be derived from the connectivity theorem of this paper.

Lemma 2 . 1 .

 21 Let Y ⊂ C n and Z ⊂ C m be two algebraic sets. Let α : Y → Z be an isomorphism of algebraic sets defined over R. Then the semi-algebraically connected subsets of Y ∩ R n and Z ∩ R m are in correspondence through α.

Lemma 3 . 2 .

 32 and that there is an open Euclidean neighborhood N of α(y) such that the implicit function theorem applies to α(Z) ∩ N . (Recall that an open Euclidean neighborhood of a point y ∈ R n is any subset of R n that contains y and is open for the Euclidean topology on R n .) Let y = (y 1 , . . . , y n ) be in Z ∩ R n -K(ϕ, Z). Then, there exists a regular map α : Z → C n+1 such that the following holds : a) there exist open Euclidean neighborhoods N ⊂ R d of π d (α(y)) and N ⊂ R n+1 of α(y), and a continuous semi-algebraic map f : N → R n+1-d such that:

  B) is open, semi-algebraic and semi-algebraically connected, since F is an open continuous map on B. Then, by assumptions on α, together with Lemma 2.1, α -1 (F (B)) is a semi-algebraically connected open neighborhood of y. Hence N (y) satisfies statement a).

Figure 4 .

 4 Lemma 3.5. Let y ∈ Z ∩ R n with u = ϕ(y) and let C be the semi-algebraically connected component of Z |ϕ≤u containing y. If C |ϕ<u = ∅ then C = C |ϕ=u ⊂ K(ϕ, Z). In particular, y ∈ K(ϕ, Z). Proof. If C |ϕ<u = ∅, since C ⊂ Z |ϕ≤u then C = C |ϕ=u holds. Let us prove the contrapositive of the rest of the lemma. Suppose that C |ϕ=u ⊂ K(ϕ, Z), and let z ∈ C |ϕ=u -K(ϕ, Z). Let B z be the semi-algebraically connected component of Z |ϕ<u obtained by applying Lemma 3.4. Since B z contains z and is a semi-algebraically connected set of Z |ϕ≤u , B z ⊂ C. Hence C |ϕ<u contains (B z ) |ϕ<u = B z , which is then not empty.

Figure 4 :

 4 Figure 4: Illustration of Lemma 3.5 in two cases. On the left, ϕ = π 1 and Z ∩ R 3 is a torus. The plane {x 1 = u} indicated satisfies C |ϕ<u = ∅. One sees that C |ϕ=u ⊂ K(ϕ, Z), and indeed C |ϕ=u = {y}.On the right, ϕ is the square of the Euclidean norm, and Z is a cylinder of radius r. Remark first that C |ϕ<r = ∅. Moreover, for x = (x 1 , x 2 , 0) ∈ Z, the differential at x of restriction of ϕ to Z is the restriction of the projection on the (x 1 , x 2 )-plane to T x Z. Since these two latter planes are orthogonal, x is indeed a critical point.

Lemma 3 . 7 .

 37 Let u ∈ R and A ⊂ R k be a semi-algebraically connected set. Let γ : A -→ Z |ϕ=u -K(ϕ, Z) be a continuous semi-algebraic map. Then there exists a unique semi-algebraically connected component B of Z |ϕ<u such that γ(A) ⊂ B. Proof. Let a 0 ∈ A and y = γ(a 0 ), by assumption, y ∈ Z |ϕ=u -K(ϕ, Z). Then by Lemmas 3.3 and 3.4, there exist an open neighborhood N (y) of y and a semi-algebraically connected component B y of Z |ϕ<u such that (Z ∩ N (y)) |ϕ=u ⊂ (Z ∩ N (y)) |ϕ<u ⊂ B y . Hence for every z ∈ (Z ∩ N (y)) |ϕ=u -K(ϕ, Z), z ∈ B y so that B z = B y by application of Lemma 3.4. Since γ is a continuous semi-algebraic map, there exists an open semi-algebraic neighborhood N (a 0 ) of

Figure 5 :

 5 Figure 5: Illustration of the proof of Proposition 3.1 where ϕ= π 1 and Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 22 ) in two cases. On the left the γ(A) ∩ (Z |π1=u ∩ K(π 1 , Z)) = ∅ and on the right, this intersection is non-empty.

  and γ is continuous. Then, let G 1 , . . . , G N be the semi-algebraically connected components of G; they are closed in A since they are closed in G, which is closed in A. Besides, let H 1 , . . . , H M be the semi-algebraically connected components of A -G. They are open in A since they are open in A -G , which is open in A.

Figure 6 :

 6 Figure 6: Illustration of the proof of Proposition 3.1 with ϕ = π and Zis isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2 2 ) in two cases. The intersection γ(A) ∩ (Z |π1=u ∩ K(π 1 , Z)) is empty on the left while, on the right, it is not.

Corollary 3 . 8 .

 38 Let ϕ : C n → C be a regular map defined over R and Z ⊂ C n be an equidimensional algebraic set of positive dimension. Let u ∈ R such that Z |ϕ=u ∩ K(ϕ, Z) = ∅ and let C be a semialgebraically connected component of Z |ϕ≤u . Then, C |ϕ<u is a semi-algebraically connected component of Z |ϕ<u . Proof. Let γ be the inclusion map γ : C → Z |ϕ≤u . Since Z |ϕ=u ∩K(ϕ, Z) = ∅, γ satisfies the assumptions of Proposition 3.1 with A = C. Then there exists a unique semi-algebraically connected component B of Z |ϕ<u such that C ⊂ B, so that C |ϕ<u ⊂ B |ϕ<u = B. First, since Z |ϕ=u ∩ K(ϕ, Z) = ∅ by assumption, then in particular C |ϕ=u ⊂ K(ϕ, Z). By the contrapositive of Lemma 3.5, C |ϕ<u is not empty. Hence, since B is a semi-algebraically connected set of Z |ϕ≤u , containing C |ϕ<u , B is contained in the semi-algebraically connected component C of Z |ϕ≤u . Finally B ⊂ Z |ϕ<u ∩ C = C |ϕ<u and C |ϕ<u = B, which is a semi-algebraically connected component of Z |ϕ<u .

Since X is bounded

  and closed, ϕ(X) is closed and bounded by[START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] Theorem 3.23]. Hence, ϕ(A |ϕ∈(v,w) ) is both open and closed in (v, w). Since (v, w) is semi-algebraically connected, ϕ(A |ϕ∈(v,w) ) = (v, w).By the Nash version of Thom's isotopy lemma [16, Theorem 2.4], since the map ϕ : A |ϕ∈(v,w) → (v, w) is a proper surjective submersion, it is a globally trivial fibration. Hence, for ζ ∈ (v, w), there exists a Nash diffeomorphism Ψ of the form

Corollary 3 . 10 .

 310 Let Z ⊂ C n be an equidimensional algebraic set of positive dimension and let ϕ : C n → C be a regular map defined over R and proper onZ ∩ R n . Let v < w be in R such that Z |ϕ∈(v,w] ∩ K(ϕ, Z) = ∅,and let C be a semi-algebraically connected component of Z |ϕ≤w . Then, C |ϕ≤v is a semialgebraically connected component of Z |ϕ≤v . Proof. As C |ϕ<w = C ∩ ϕ -1 ((-∞, w)) ∩ R n , we are going to use Proposition 3.1 with A = C |ϕ<w .

Figure 8 :

 8 Figure 8: Illustration of the two cases covered by the proof of Proposition 3.9 where ϕ = π 1 andA = Z |π1<w , where Z is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 2 2). The two cases are quite similar; we consider here the one where v is a critical value. One sees that Ψ connects all the slices A |π1=u for u ∈ (v, w) . This diffeomorphism allows to transform the problematic parts (not in A |π1≤u ) of the initial path γ (in green), into another path g (in red), that lies in A |π1=u ⊂ A |π1≤u .

Figure 9 :

 9 Figure 9: Illustration of Corollary 3.10 where ϕ = π 1 andZ is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 + x 22 ) in two cases. On the left Z |π1∈(v,w) ∩ K(π 1 , Z) = ∅ and we see that C |π1≤v is still a semi-algebraically connected component of Z |π1≤v . On the right Z |π1∈(v,w) ∩ K(π 1 , Z) contains a point and we see that C |π1≤v is semi-algebraically disconnected.

Lemma 4 . 1 .

 41 is non-empty and semi-algebraically connected", by proving a truncated version of RM and show that it is enough. For u ∈ R let RM(u): "For any semi-algebraically connected component C of V |ϕ 1 ≤u , the set C ∩ R is non-empty and semi-algebraically connected". If RM(u) holds for all u ∈ R, then RM holds.

Figure 10 :

 10 Figure 10: Illustration of proof of Lemma 4.4 withϕ 1 = π 1 and V is isomorphic to V (x 2 1 + x 2 2 -1) × V (x 1 -x 22 ). Elements of H 1 can be seen as curves of infinitesimal lengths, starting from a point of lim ε H 1 , and lying in B. Here, lim ε H 1 is the set of points that share the same first coordinate than y. Hence, the above proof consisted in choosing a ζ in H 1 , that lives "inside" W i ∪ sing(V ) (actually in ext(W i ∪ sing(V ), R ε )).

1 .

 1 If D ⊂ B, there exists y ∈ D such that y / ∈ B. Then let γ : [0, 1] → D such that γ(0) = y and γ(1) = y . Hence, if t 1 = max{t ∈ [0, 1) | γ(t) ∈ B}, then γ(t 1 ) ∈ K(ϕ 1 , V ) by the contrapositive of statement c) of Lemma 3.

Proposition 4 . 7 (

 47 Step 1). Let u ∈ R. Assume that for all u < u, RM(u ) holds. Then RM(u) holds.The proof of this proposition is illustrated byFigure 11.

  x

Example 1 .

 1 Let V = V (g) ⊂ C 3 be the hypersurface defined by the vanishing set of the polynomialg = x 3 1 + x 3 2 + x 3 3 -x 1 -x 2 -x 3 -1 ∈ Q[x 1 , x 2 , x 3 ].As a hypersurface, V is 2-equidimensional and since sing(V ) = ∅, V satisfies (A).

  Figure 13 illustrates this example.

Figure 13 :

 13 Figure 13: An illustration of Example 1.The real trace V ∩ R 3 is plotted twice as a grid. On the left, W 2 ∩R 3 is represented as red lines, and the crosses represent all the real points of K 2 . Then, on the right, we replaced the points of K 2 by the fibers of F 2 ∩ R 3 (black lines), to repair the connectivity failures of W 2 ∩ R 3 . In particular, F 2 ∩ R 3 connects the semi-algebraically connected components of W 2 ∩ R 3 that lie in the same semi-algebraically connected component of V ∩ R 3 .

  is a Nash diffeomorphism from A |ϕ∈(v,w) to (v, w) × A |ϕ=ζ , and satisfies ϕ(γ(t)) = tu+(1-t)ζ for every t ∈ [0, 1). Moreover γ is a bounded map as A |ϕ∈(v,w) is bounded by assumption. Then, by [4, Proposition 3.21], γ can be continuously extended to [0, 1], with ϕ(γ(t)) = tu + (1 -t)ζ continuous on [0, 1], and ϕ(γ(1)) = u. Finally γ(1) ∈ A |ϕ≤u and A |ϕ≤u is not empty.

  3. Since K(ϕ 1 , V ) ⊂ F i , we can apply Lemma 4.4 to γ(t 1 ) and find z ∈ B ∩ (F i ∪ W i ) that is connected to γ(t 1 ) and then to y by a semi-algebraic path in B ∩ (F i ∪ W i ).2. If D ⊂ B , we claim that there exists some z ∈ D ∩ F i . Indeed since D is a semi-algebraically connected component of (W i ) |ϕ 1 ≤u and ϕ 1 is a proper map, D is bounded. Then by Proposition 3.6 there exists y ∈ D ∩ K(ϕ 1 , W i ). If y ∈ sing(W i ) then y ∈ sing(V ) by assumption B 1 and taking z = y ∈ F i one concludes as in the first item.Else y is in W (ϕ 1 , W i ), and we let E be the semi-algebraically connected component ofW (ϕ 1 , W i ) containing y . Since ϕ 1 (W (ϕ 1 , W i )) is finite by Sard's lemma, ϕ 1 (E) = {ϕ 1 (y )}, so that E ⊂ (W i ) |ϕ 1 ≤u . Hence, since E is semi-algebraically connected, E ⊂ D.By assumption C 2 , there exists z ∈ E ∩ S i , so that z ∈ D ∩ S i ⊂ D ∩ F i and we are done.Then we can connect y to z inside D ⊂ B ∩ W i and since z is inD ∩ F i , which is contained in B ∩ F i , we can connect similarly z to some z ∈ B ∩ (F i ∪ W i ) inside B ∩ F i by Lemma 4.4.Putting things together, y is connected to some z ∈ B∩(F i ∪W i ) by a semi-algebraic path in B∩F i . Corollary 4.5. Let u ∈ R such that for all u < u, RM(u ) holds. Let C be a semi-algebraically connected component of V |ϕ 1 ≤u such that C |ϕ 1 <u is non-empty. If B is a semi-algebraically connected component of C |ϕ 1 <u , then B ∩ R is non-empty and semi-algebraically connected. Proof. Let y and y be in B ∩ R. According to Proposition 4.2, they can respectively be connected to some z and z in B ∩ R, by a semi-algebraic path in B ∩ R. As B is semi-algebraically connected, there exists a semi-algebraic path γ : [0, 1] → B connecting z to z . Let

Acknowledgments

The first and second authors are supported by ANR grants ANR-18-CE33-0011 Sesame, and ANR-19-CE40-0018 De Rerum Natura, the joint ANR-FWF ANR-19-CE48-0015 ECARP project, the European Union's Horizon 2020 research and innovative training network program under the Marie Skłodowska-Curie grant agreement N o 813211 (POEMA) and the Grant FA8665-20-1-7029 of the EOARD-AFOSR. The third author was supported by an NSERC Discovery Grant. We also thank the referees for their helpful remarks and suggestions.

Proof. Let u ∈ R be such that for all u < u, RM(u ) holds and let C be a semi-algebraically connected component of V |ϕ 1 ≤u . We have to prove that C ∩ R is non-empty and semi-algebraically connected.

If C |ϕ 1 <u is empty, then, by Lemma 3.5, C ⊂ K(ϕ 1 , V ). But the points of K(ϕ 1 , V ) are either in W i or in sing(V ) ⊂ F i . Hence K(ϕ 1 , V ) ⊂ R and C ∩ R = C, which is non-empty and semi-algebraically connected by definition.

From now on, C |ϕ 1 <u is supposed to be non-empty and let B 1 , . . . , B r be its semi-algebraically connected components. According to Corollary 4.5, for all 1 ≤ j ≤ r, B j ∩ R is non-empty and semialgebraically connected. Then, as B j ⊂ C,

for every 1 ≤ j ≤ r, and C ∩ R is non-empty.

Let us now prove that C ∩ R is semi-algebraically connected. Let y and y in C ∩ R. As C is semi-algebraically connected, there exists a semi-algebraically continuous map γ : [0, 1] → C such that γ(0) = y and γ(1) = y . Now let

We denote by G 1 , . . . , G N the connected components of G and H 1 , . . . , H M those of H. The sets H j for 1 ≤ j ≤ M are open intervals of [0, 1], and we note j = inf(H j ) and r j = sup(H j ). Since γ(G) already lies in C ∩ R, let us establish that for every 1 ≤ j ≤ M , γ( j ) and γ(r j ) can be connected by another semi-algebraic path

Hence, since H j is connected, there exists (by Proposition 3.1) a unique semi-algebraically connected component B of V |ϕ 1 <u such that γ(H j ) ⊂ B. But γ(H j ) ⊂ C, so that B and thus B are actually contained in C. Therefore, B is actually a semi-algebraically connected component of C |ϕ 1 <u and there exists

and both γ( j ) and γ(r j ) are in B k . Remark that both j and r j are in G, so that both γ( j ) and γ(r j ) are in K(ϕ 1 , V ) ⊂ F i ⊂ R. Thus, both γ( j ) and γ(r j ) are in B k ∩ R. According to Corollary 4.5, they can be connected by a semi-algebraic path

In conclusion, we have proved that for 1 ≤ j ≤ M , γ( j ) and γ(r j ) can be connected by a semialgebraic path τ j in C ∩ R. Therefore the semi-algebraic sub-paths γ |Hj can be replaced by the τ j 's, which lie in C ∩ R. Moreover, for all

Since the H j 's and G j 's form a partition of [0, 1], by putting together alternatively the τ j 's and the γ |Gj 's, one obtains a semi-algebraic path in C ∩ R connecting y = γ(0) to y = γ(1). And we are done. Proposition 4.8 (Step 2). Let j ∈ {1, . . . , }, if RM(v j ) holds, then for all u ∈ (v j , v j+1 ), RM(u) holds.

The proof of this proposition is illustrated by Figure 12.

Proof. Let j ∈ {0, . . . , } and u ∈ (v j , v j+1 ). Let C be a semi-algebraically connected component of V |ϕ 1 ≤u ; we have to prove that C ∩ R is non-empty and semi-algebraically connected.

Let us first prove that C |ϕ 1 ≤vj ∩ R is non-empty and semi-algebraically connected. By assumption (A), V is an equidimensional algebraic set of positive dimension, and by assumption (P), the restriction of ϕ 1 to V ∩ R n is a proper map bounded below. Moreover, as ϕ 1 (K(ϕ 1 , V ) ∩ R n ) ⊂ {v 1 , . . . , v }, then