S Basu
email: sbasu@math.purdue.edu

M-F Roy

M Safey

E L Din

É Schost
email: eschost@uwo.ca

A BABY STEP-GIANT STEP ROADMAP ALGORITHM FOR GENERAL ALGEBRAIC SETS

Keywords: 2010 Mathematics Subject Classification. Primary 14Q20; Secondary 14P05, 68W05 Roadmaps, Real algebraic variety, Baby step-giant step

Let R be a real closed field and D ⊂ R an ordered domain. We give an algorithm that takes as input a polynomial Q ∈ D[X 1 , . . . , X k ], and computes a description of a roadmap of the set of zeros,

The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain D, is bounded by

As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, Zer(Q, R k ), whose complexity is also bounded by d O(k √ k) , where d = deg(Q) ≥ 2. The best previously known algorithm for constructing a roadmap of a real algebraic subset of R k defined by a polynomial of degree d has complexity d O(k 2 ) .

Introduction

The problem of designing efficient algorithms for deciding whether two points belong to the same semi-algebraically connected component of a semi-algebraic set, as well as counting the number of semi-algebraically connected components of a given semi-algebraic set S ⊂ R k where R is a real closed field (for example the field of real numbers), is a very important problem in algorithmic semi-algebraic geometry.

The first algorithm for solving this problem [START_REF] Schwartz | On the piano movers' problem ii. general techniques for computing topological properties of real algebraic manifolds[END_REF] was based on the technique of cylindrical algebraic decomposition [6, 2], and consequently had doubly exponential complexity in k.

Algorithms with singly exponential complexity in k for solving this problem was first introduced by Canny in [START_REF] Canny | The Complexity of Robot Motion Planning[END_REF], and then successively completed and refined in [15,11,[START_REF] Heintz | Single exponential path finding in semialgebraic sets. I. The case of a regular bounded hypersurface[END_REF]12,[START_REF] Gournay | Construction of roadmaps of semi-algebraic sets[END_REF]10,[START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF]. They are all based on a geometric idea introduced by Canny, the construction of a one-dimensional s-a (i.e. semi-algebraic) subset of the given s-a set S, called a roadmap of S, which has the property that it is non-empty and s-a connected inside every s-a (i.e. semi-algebraically) connected component of S.

In the papers mentioned above, the construction of a roadmap of a s-a set S depends on recursive calls to itself on several (in fact, singly exponentially many) (k -1)-dimensional slices of S, each obtained by fixing the first coordinate. For constructing the roadmap of a real algebraic variety defined by a polynomial Q ∈ R[X 1 , . . . , X k ] with deg(Q) ≤ d, this technique gave an algorithm with complexity d O(k 2 ) . The exponent in the upper bound on the complexity, O(k 2 ), is due to the fact that the depth of the recursion in these algorithms could be as large as k. This exponent is not satisfactory since the total number of s-a connected components is (O(d)) k and so there is room for trying to improve it. However, this has turned out to be a rather difficult problem with no progress until very recently.

A new construction for computing roadmaps, with an improved recursive scheme of baby step -giant step type, has been proposed, and applied successfully in the case of smooth bounded real algebraic hypersurfaces in [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]. In this new recursive scheme, the dimension drops by √ k in each recursive call. As a result, the depth of the recursive calls in this new algorithm is at most √ k, and consequently the algorithm has a complexity of d O(k √ k) . The proof of correctness of the algorithm in [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF] depends on certain results from commutative algebra and complex algebraic geometry, in order to prove smoothness of polar varieties corresponding to generic projections of a non-singular hypersurface. Choosing generic coordinates in the algorithm is necessary since the non-singularity of polar varieties does not hold for all projections, but only for a Zariski-dense set of projections. This is an important restriction, since there is no known method for making such a choice of generic coordinates deterministically within this improved complexity bound. As a result, the authors obtain a randomized (rather than a deterministic) algorithm for computing roadmaps: there might be cases where the algorithm terminates and gives a wrong result.

In contrast to these techniques which depend on complex algebraic geometry, the algorithm for constructing roadmaps described in [2] depends mostly on arguments which are semi-algebraic in nature. The greater flexibility of semi-algebraic geometry (as opposed to complex geometry) makes it possible to avoid genericity requirements for coordinates. More precisely, we apply the technique used in [2] to make an infinitesimal deformation of the given variety so that the original coordinates are good. Since the infinitesimal deformation uses only one infinitesimal, it does not affect the asymptotic complexity class of the algorithm.

The goal of this paper is to obtain a deterministic algorithm for computing the roadmap of a general algebraic set, combining a baby step -giant step recursive scheme similar to that used in [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF] and extending techniques coming from [2].

We start by recalling the precise definition of what is meant by a roadmap. Definition 1.1. Let S ⊂ R k be a s-a set. A roadmap for S is a s-a set RM(S) of dimension at most one contained in S which satisfies the following roadmap conditions:

(1) RM 1 For every s-a connected component C of S, C∩RM(S) is s-a connected.

(2) RM 2 For every x ∈ R and for every s-a connected component C ′ of S x , C ′ ∩ RM(S) = ∅, where we denote by S x the set S ∩ π -1 1 (x) for x ∈ R, with π 1 : R k → R the projection map onto the first coordinate.

Let M ⊂ R k be a finite set of points. A roadmap for (S, M) is a s-a set RM(S, M) such that RM(S, M) is a roadmap of S and M ⊂ RM(S, M).

We illustrate this definition by the picture of a torus in R 3 and a roadmap of it. The main result of the paper is the following theorem. The notion of real univariate representations used in the following statements to represent finite sets of point in R k is explained in Section 4.

Theorem 1.2. Let Z ⊂ R k be an algebraic set defined as the set of zeros of a polynomial of degree at most d ≥ 2 in k variables with coefficients in an ordered domain D contained in a real closed field R. a) There exists an algorithm for constructing a roadmap for Z using d O(k

√ k)
arithmetic operations in D. b) Moreover, there exists an algorithm that given a finite set of points M 0 ⊂ Z, with cardinality δ, and described by real univariate representations of degree at most d O(k) , constructs a roadmap for (Z, M 0 )

using δ O(1) d O(k √ k)
arithmetic operations in D.

The following corollary is an immediate consequence of b).

Corollary 1.3. Let Z ⊂ R k be an algebraic set defined as the set of zeros of a polynomial of degree at most d ≥ 2 in k variables with coefficients in an ordered domain D contained in a real closed field R. a) There exists an algorithm for counting the number of s-a connected components of Z which uses d O(k √ k) arithmetic operations in D. Remark 1.4. We can always suppose without loss of generality that the zero set of a family of polynomials of degree at most d is defined by one single polynomial of degree at most 2d by replacing the input polynomials by their sum of squares.

Remark 1.5. Even if the input is a polynomial with coefficients in the field of real numbers, the deformation techniques by infinitesimal elements we use make it necessary to perform computations on polynomials with coefficients in some nonarchimedean real closed field. This is the reason why general real closed fields provide a natural framework for our work.

Outline

We outline below the classical construction of a roadmap RM(Zer(Q, R k )) for a bounded algebraic set Zer(Q, R k ), defined as the zero set of a polynomial Q contained in R k . The geometric ideas yielding this construction are due to Canny. The description below is similar to the one in [2, Chapter 15, Section 15.2].

A key ingredient of the algorithm is the construction of a particular finite set of points intersecting every s-a connected component of Zer(Q, R k ). In the case of a bounded and non-singular real algebraic set in R k , these points are nothing but the set of critical points of the projection to the X 1 -coordinate on Zer(Q, R k ). In more general situations, the points we consider are called X 1 -pseudo-critical points, since they are obtained as limits of the critical points of the projection to the X 1coordinate of a bounded nonsingular algebraic hypersurface defined by a particular infinitesimal deformation of the polynomial Q. Their projections on the X 1 -axis are called pseudo-critical values.

We first construct the "silhouette" which is the set of X 2 -pseudo-critical points on Zer(Q, R k ) along the X 1 -axis by following continuously, as x varies on the X 1axis, the X 2 -pseudo-critical points on Zer(Q, R k ) x . Note that in case Zer(Q, R k ) is a non-singular hypersurface, then the "silhouette" described above is the set of critical points of the projection map to the coordinates X 1 and X 2 . However, we are not assuming here that Zer(Q, R k ) is a non-singular hypersurface. This results in curves and their endpoints on Zer(Q, R k ). The curves are continuous s-a curves parametrized by open intervals on the X 1 -axis and their endpoints are points of Zer(Q, R k ) above the corresponding endpoints of the open intervals. Since these curves and their endpoints include for every x ∈ R the X 2 -pseudo-critical points of Zer(Q, R k ) x , they meet every s-a connected component of Zer(Q, R k ) x . Thus, the set consisting of these curves and their endpoints, already satisfy RM 2 . However, it is clear that this set might not be s-a connected in a s-a connected component and so RM 1 might not be satisfied.

In order to ensure property RM 1 we need to add more curves to the roadmap. For this purpose, we define the set of distinguished values D as the union of the X 1 -pseudo-critical values, and the first coordinates of the endpoints of the curves described in the previous paragraph. A distinguished hyperplane is a hyperplane defined by X 1 = v, where v is a distinguished value. The input points, the endpoints of the curves, and the intersections of the curves with the distinguished hyperplanes define the set of distinguished points, M.

Let the distinguished values be v 1 < . . . < v N . Note that amongst these are the X 1 -pseudo-critical values. Above each interval (v i , v i+1 ) we have constructed a collection of curves C i meeting every s-a connected component of Zer(Q, R k ) v for every v ∈ (v i , v i+1 ). Above each distinguished value v i we have a set of distinguished points M i . Each curve in C i has an endpoint in M i , and another one in M i+1 . Moreover, the union of the M i contains M. We denote by C the union of the C i .

The following key connectivity result is proved in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Lemma 15.9].

Proposition 2.1. Let R = C ∪ Zer(Q, R k ) D . If P is a s-a connected component of Zer(Q, R k ), then R ∩ P is s-a connected.
Thus, in order to construct a roadmap of Zer(Q, R k ) it suffices to repeat the same construction in each distinguished hyperplane H i defined by X 1 = v i with input Q(v i , X 2 , . . . , X k ) and the distinguished points in M vi by making recursive calls to the algorithm. The following proposition is proved in [2, Proposition 15.7].

Proposition 2.2. The s-a set RM(Zer(Q, R k ), M) obtained by this construction is a roadmap for Zer(Q, R k ) containing M.

To summarize, classical roadmap algorithms based on Canny's construction proceed by first considering the "silhouette", consisting of curves in the X 1 -direction, and then making recursive calls to the same algorithm at certain hyperplane sections of Zer(Q, R k ), so that the dimension of the ambient space drops by 1 at each recursive call.

The main difference between classical roadmap algorithms and the algorithms described in [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF] and in the current paper is that instead of considering curves in the X 1 -direction and making recursive calls to the same algorithm at certain hyperplane sections of Zer(Q, R k ) corresponding to special values of X 1 , so that the dimension of the ambient space drops by 1, we consider a p-dimensional subset W (p) of Zer(Q, R k ) where 1 ≤ p ≤ k, and make recursive calls at certain (kp)dimensional fibers of Zer(Q, R k ), so that the dimension of the ambient space drops by p.

The main topological result, analogous to Proposition 2.1, is that if the set Zer(Q, R k ) satisfies certain conditions, such as having only isolated singular points, then the s-a set which is the union of W and these fibers are s-a connected. This is proved in Section 3. It follows, though not immediately, that for a general real algebraic set, Zer(Q, R k ), in order to produce a roadmap of Zer(Q, R k ) it suffices to compute:

(1) a roadmap of a certain s-a subset W of an infinitesimal deformation of Zer(Q, R k ) passing through a carefully chosen set of points, and taking the limit of the curves so obtained by letting the perturbarion variable go to 0; (2) roadmaps of certain fibers in a (kp)-dimensional ambient space, using recursive calls. The fact that in the new algorithm we are fixing a whole block of p variables at a time necessitates introducing a new kind of algebraic representation which we call "real block representation". This notion is defined in Section 4, where we also explain how to represent curves over such blocks.

In Section 5, we consider the case when W is low-dimensional and described by equations having a special structure. Adapting an algorithm from [2, Algorithm 15.3] we show how to compute a roadmap of W in this case with complexity depending in a crucial way on the dimension of W . The general case, requiring the use of a deformation technique and a limit process, is described in Section 6.

Finally, we obtain in Section 7 a baby step -giant step roadmap algorithm for a general algebraic set. We prove its correctness, as well as the improved complexity bound.

The algorithm for computing efficiently limits of curve segments is quite technical. Since this technicality can obscure the ideas behind the main algorithm, for the sake of readability we have postponed the details behind taking limits of curves to a separate section (Section 8).

Throughout the paper, we use as a basic reference [2]. We cite [START_REF] Basu | Algorithms in real algebraic geometry[END_REF] instead when the precise statements needed are not included in [2].

Connectivity results

In this section we prove a topological result about connectivity which will be used in proving the correctness of our algorithm later. The statement of the result, as well as the main ideas of the proof, is influenced by [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14]. It is a direct generalization of Proposition 2.1 to the case of projection onto more than one variable.

We denote by R a real closed field.

Notation 3.1. For 1 ≤ p < k, we denote by π p the projection (x 1 , . . . , x k ) → x p .

For 1 ≤ q ≤ p < k, we denote by π [q,p] : R k → R p-q+1 the projection (x 1 , . . . , x k ) → (x q , . . . , x p ).

For any pair of s-a subsets S ⊂ R k , and T ⊂ R p , we denote by S T the s-a set π -1

[1,p] (T ) ∩ S, and S y rather than S {y} , for y ∈ R p . We also write S <a and S ≤a rather than S (-∞,a) and S (-∞,a] , for a ∈ R.

We denote as before by Zer(Q, R k ) the algebraic set of zeros of a polynomial

Q ∈ R[X 1 , . . . , X k ] contained in R k .
Note that for a non-constant polynomial Q, the real dimension of Zer(Q, R k ) is not necessarily equal to k -1, and indeed Zer(Q, R k ) might even be empty. In fact, over any real closed field, algebraic sets defined by one equation coincide with general algebraic sets since replacing several equations by their sum of squares does not modify the zero set.

A Q-singular point is a point x ∈ R k such that Q(x) = ∂Q ∂X 1 (x) = . . . = ∂Q ∂X k (x) = 0.
Note that this is an algebraic property related to the polynomial Q rather than a geometric property of the underlying set Zer(Q, R k ): two equations can define the same algebraic set but have different sets of singular points.

Similarly a Q-critical point of π 1 is a point x ∈ R k such that Q(x) = ∂Q ∂X 2 (x) = • • • = ∂Q ∂X k (x) = 0.
To simplify notation, when there will be no ambiguity regarding Q, we will simply refer to singular/critical points.

In this paper, we will be using constantly the notion of s-a connected components of a s-a set [2, Section 5.2]. Note that, in particular, a s-a connected component is always non-empty by definition (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Theorem 5.21] and the definition of sa connected components following it). In particular, the empty set has no s-a connected component. Property 3.2. We now consider for 1 ≤ p < k a tuple

V, M, W (p) , M (p) , D (p)
with the following properties:

(1) V ⊂ R k is the union of certain bounded s-a connected components of an algebraic set Zer(Q, R k ) ⊂ R k , such that the Q-critical points of the map π 1 on V (which contains in particular the Q-singular points contained in V ) form the finite set M ⊂ V ; (2) W (p) ⊂ V is a closed s-a set of dimension p, such that for each y ∈ R p , W (p) y (cf. Notation 3.1) is a finite set of points having non-empty intersection with every s-a connected component of V y ;

(3) M (p) ⊂ V is a finite subset such that the intersection of M (p) with every s-a connected component of

W (p) a is non-empty, for a ∈ D (p) = π 1 (M (p) ). Moreover, for every interval [a, b] and c ∈ [a, b] with {c} ⊃ D (p) ∩ [a, b], if C is a s-a connected component of W (p) [a,b] , then C c is a s-a connected component of W (p) c . A tuple V, M, W (p) , M (p) , D (p)
is said to satisfy Property 3.2 if it satisfies the above properties (1) to (3). Now we state the main result of this section. It generalizes Proposition 2.1 as well as [START_REF] Safey El Din | A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface[END_REF]Theorem 14], in the special case when Property 3.2 holds.

Proposition 3.3. Let V, M, W (p) , M (p) , D (p)
satisfy Property 3.2,

N = π [1,p] (M), N (p) = π [1,p] (M (p) ),
and

S = W (p) ∪ V N ∪N (p) .
For every s-a connected component C of V , C ∩ S is non-empty and s-a connected. Remark 3.4. In order to understand the situation, the following example of a tuple satisfying Property 3.2 can be useful:

(1) the torus V ⊂ R 3 defined as the set of zeros of the equation

Q = 36(X 2 1 + 12X 2 + 5X 3 13 2 ) -(X 2 1 + X 2 2 + X 2 3 + 8) 2 , ( [4]
, page 40, figure 2.5), p = 1, the four critical points M ⊂ V of the map π 1 restricted to V ; (2) the silhouette W (1) ⊂ V defined by

Q = ∂Q ∂X 3 = 0;
(3) the six critical values D (1) ⊂ R of the map π 1 restricted to the silhouette W , and the intersection M (1) of the corresponding six fibers with the silhouette W (1) . The tuple V, M, W (1) , M (1) , D (1) satisfies Property 3.2. Finally, S is the union of the silhouette and the intersection of the torus with the six curves which are the fibers of V at the distinguished values D (1) . The rest of this section is devoted to prove Proposition 3.3. We need preliminaries about non-archimedean extensions of the base real closed field R. Remark 3.5. A typical non-archimedean extension of R is the field R ε of algebraic Puiseux series with coefficients in R, which coincide with the germs of s-a continuous functions (see [2, Chapter 2, Section 6 and Chapter 3, Section 3]). An element x ∈ R ε is bounded over R if |x| ≤ r for some 0 ≤ r ∈ R. The subring R ε b of elements of R ε bounded over R consists of the Puiseux series with non-negative exponents. We denote by lim ε the ring homomorphism from R ε b to R which maps i∈N a i ε i/q to a 0 . So, the mapping lim ε simply replaces ε by 0 in a bounded Puiseux series. Given S ⊂ R ε k , we denote by lim ε (S) ⊂ R k the image by lim ε of the elements of S whose coordinates are bounded over R.

More generally, let R ′ be a real closed field extension of R. If S ⊂ R k is a s-a set, defined by a boolean formula Φ with coefficients in R, we denote by Ext(S, R ′ ) the extension of S to R ′ , i.e. the s-a subset of R ′k defined by Φ. The first property of Ext(S, R ′ ) is that it is well defined, i. Moreover, if Property 3.2 (2) holds for V, W , i.e. for every y ∈ R p , W y is a finite set of points having non-empty intersection with every s-a connected component of V y , then Property 3.2 (2) holds for Ext(V, R ′ ), Ext(W, R ′ ), i.e for each y ′ ∈ R ′p , Ext(W, R ′ ) y ′ is a finite set of points having non-empty intersection with every s-a connected component of Ext(V, R ′ ) y ′ . Indeed, by Hardt's s-a triviality theorem [2, Theorem 5.45], one can find a finite partition of R p into s-a sets T i , i = 1, . . . , r, a finite partition of V Ti into s-a sets S i,j and an integer n i > 0 such that S i,j is s-a homeomorphic to T i × (S i,j ) yi for some y i ∈ T i , and for all y ∈ T i , the s-a connected components of V y are (S i,j ) y and W y has n i points. By Tarski-Seidenberg's transfer principle [2, Theorem 2.80], Ext(S i,j , R ′ ) is s-a homeomorphic to Ext(T i , R ′ ) × Ext(S i,j , R ′ ) yi , and for all y ′ ∈ R ′p , there exists i such that y ′ ∈ Ext(T i , R ′ ), the sets Ext(S i,j , R ′ ) y ′ are the s-a connected components of Ext(V, R ′ ) y ′ and the intersection of Ext(W, R ′ ) y ′ and Ext(S i,j , R ′ ) y ′ has exactly n i points.

Let V be the union of a subset of the bounded s-a connected components of an algebraic set Zer(Q, R k ) ⊂ R k . Suppose also that the set M of points which are singular points of Zer(Q, R k ) or critical points of π 1 on Zer(Q, R k ) and which belong to V is finite. We now prove two preliminary results (Lemma 3.6 and Lemma 3.7 below) about the pair (V, M) which will be needed in the proof of Proposition 3.3.

In this paper a s-a path is a s-a continuous function γ from a closed interval [a, b] ⊂ R to R k . Note that a s-a set is s-a connected if and only if it is s-a path connected [2, Theorem 5.23]. Lemma 3.6. Let C be a s-a connected component of V ≤b such that C ∩ V b is not empty.

(

) If dim(C) = 0, C is a point contained in M. (2) If dim(C) = 0, C <b is non-empty. Let B 1 , . . . , B s be the s-a connected components of C <b . Then, (a) for each i, 1 ≤ i ≤ s, B i ∩ M = ∅; (b) if there exist i, j, 1 ≤ i < j ≤ s such that B i ∩ B j = ∅, then B i ∩ B j ⊂ M; (c) ∪ s i=1 B i = C 1
, and hence ∪ s i=1 B i is s-a connected. Proof. Part 1 follows immediately from [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Proposition 7.3]. We prove Part 2. Since M is finite, there is a non-singular point x ∈ C b which is non-critical for π 1 on V . Let T x V denote the tangent space to V at x. So T x V is not orthogonal to the X 1 axis, and the s-a implicit function theorem [2, Theorem 3.25] implies that C <b is non-empty.

Part 2) a) and 2 b) are immediate consequences of Proposition 7.3 in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF].

We prove 2) c). Clearly, ∪ s i=1 B i ⊂ C. Moreover since C <b is non-empty, ∪ s i=1 B i is also non-empty. Suppose that x ∈ A = C \ ∪ s i=1 B i . For r > 0 sufficiently small, B k (x, r) ∩ C <b = ∅ (where B k (x, r) is the k-dimensional open ball of center x and radius r). Note that π 1 (x) = b, since otherwise x belongs to C <b , and thus to one of the B i 's.

Applying [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Proposition 7.3], we deduce from the fact that B k (x, r) ∩ C <b = B k (x, r) <b ∩ C = ∅ that x is either a Q-singular point, or a Q-critical point of π 1 on V . In other words x ∈ M. But since by assumption M is finite, this implies that A is a finite set and is closed. Since C is s-a connected, and ∪ s i=1 B i closed and non-empty, A must be empty.

Lemma 3.7. Suppose that b ∈ π 1 (M). Let C be a s-a connected component of V ≤b . If a < b and (a, b] ∩ π 1 (M) is empty, then C ≤a is a s-a connected component of V ≤a .
Proof. We first prove that C ≤a is non-empty. Since C is non-empty because it is a s-a connected component of V ≤b , there must exist a ′ ∈ R, with a ′ ≤ b, such that C ≤a ′ is non-empty, but C ≤a ′′ is empty for all a ′′ < a ′ . In this case, using Lemma 3.6, a ′ ∈ π 1 (M), since (a, b] ∩ π 1 (M) is empty, a ′ ≤ a and C ≤a is non-empty.

We now show that C ≤a is s-a connected. This together with the fact shown above implies that C ≤a a s-a connected component of V ≤a . Let x and y be two points of C ≤a and γ : [0, 1] → C be a s-a path connecting x to y inside C. We want to prove that there is a s-a path connecting x to y inside C ≤a .

If Im(γ) ⊂ C ≤a , there is nothing to prove. If Im(γ) ⊂ C ≤a , then there exists c ∈ R such that for all d ∈ R such that a < d < c, Im(γ) ∩ Zer(Q) d = ∅.

Let ε be a positive infinitesimal. Then

Ext(γ([0, 1]), R ε ) ∩ Zer(Q, R ε k ) a+ε = ∅ using [2, Proposition 3.17] . Since {u ∈ [0, 1] ⊂ R ε | Ext(γ, R ε )(u) ∈ Zer(Q, R ε k ) <a+ε } and {u ∈ [0, 1] ⊂ R ε | Ext(γ, R ε )(u) ∈ Zer(Q, R ε k ) [a+ε,b] } are s-a subsets of [0, 1] ⊂ R ε , there exists by [2, Corollary 2.79] a finite partition P of [0, 1] ⊂ R ε such that for each open interval (u, v) of P, Ext(γ, R ε )(u, v) is either contained in the set Zer(Q, R ε k ) <a+ε , or in the set Zer(Q, R ε k ) [a+ε,b] , with γ(u) and γ(v) in Ext(C, R ε ) a+ε . If Ext(γ, R ε )(u, v) is contained in Zer(Q, R ε k ) [a+ε,b] , we can replace γ by a s-a path γ ′ [a,b] connecting γ(u) to γ(v) inside Ext(C, R ε ) a+ε . Note that there is no Q-critical point of π 1 in Ext(V, R ε ) [a+ε,b] and Ext(V, R ε ) [a+ε,b] contains no Q-singular point by [2, Proposition 3.17] while Ext(V, R ε ) ⊂ Zer(Q, R ε k ) by [2, Proposition 2.87] . By [3, Proposition 15.1 b], if C ′ is a s-a connected component of Ext(V, R ε ) [a+ε,b] , C ′ a+ε is a s-a connected component of Ext(V, R ε ) a+ε . Construct a s-a path γ ′ from x to x ′ inside Ext(C, R ε ) ≤a+ε , obtained by con- catenating pieces of γ inside Zer(Q, R ε k ) <a+ε and the paths γ ′ (u,v) connecting γ(u) to γ(v) for (u, v) such that Ext(γ, R ε )(u, v) ⊂ Ext(V, R ε ) [a+ε,b] .
Note that such a s-a connected path γ ′ is closed and bounded. Applying [2, Proposition 12.43], lim ε (γ ′ ([0, 1])) is s-a connected, contains x and x ′ and is contained in lim ε (Ext(C, R ε ) ≤a+ε ) = C ≤a . This proves the lemma. Notation 3.8. If S ⊂ R k is s-a set and x ∈ S, then we denote by C(S, x) the s-a connected component of S containing x.

We are now ready to prove Proposition 3.3.

Proof of Proposition 3.3. For every a ∈ R, we say that property P(a) holds if: for any s-a connected component C of V ≤a , C ∩ S is s-a connected.

We prove that for all a in R, the property P(a) holds. Since V is bounded, the proposition follows from the property P(a) for any a ≥ max x∈V π 1 (x).

Let

D = π 1 (M ∪ M (p) ).
The proof uses two intermediate results:

Step 1: For every a ∈ D, property P(a) implies property

P(b) if b ∈ R with (a, b] ∩ D = ∅.
Step 2: For every b ∈ D, if property P(a) holds for all a < b, then property P(b) holds.

Since for a < min x∈V π 1 (x), the property P(a) holds vacuously, and the combination of these two results gives by an easy induction the property P(a) for all a in R.

We now prove the two steps.

Step 1. We suppose that a ∈ D, and that the property P(a) holds. Take b ∈ R, a < b with (a, b] ∩ D = ∅ and prove that the property P(b) holds. Let C be a s-a connected component of V ≤b . We have to prove that C ∩ S is non-empty and s-a connected.

Since (a, b] ∩ D = ∅, it follows that M (a,b] = ∅, and C ≤a is a s-a connected component of V ≤a using Lemma 3.7. So, using property P(a), we see that C ≤a ∩ S is non-empty and s-a connected.

If C ≤a ∩ S = C ∩ S, there is nothing to prove. Otherwise, let x ∈ C ∩ S such that x ∈ C ≤a . We prove that x can be s-a connected to a point in C ≤a ∩ S by a s-a path in C ∩ S, which is enough to prove that C ∩ S is s-a connected.

Since π 1 (x) ∈ (a, b] and (a, b] ∩ D = ∅, we deduce that π 1 (x) ∈ D and x ∈ V N ∪N (p) . So, from x ∈ S, we get x ∈ W (p) . We note that C(W

(p) [a,b] , x) ⊂ C. By Property 3.2 (3) applied to C(W (p) [a,b] , x) (noting that (a, b] ∩ D 2 ⊂ (a, b] ∩ D = ∅) we have that a ∈ π 1 (C(W (p) [a,b] , x)) and C(W (p) [a,b] ,
x) a is non-empty. Hence there exists a s-a path connecting x to a point in C(W

(p) [a,b] , x) a inside C(W (p) [a,b] , x). Since C(W (p) [a,b] , x) ⊂ W (p) ⊂ S and C(W (p) [a,b] , x) ⊂ C, it follows that C(W (p) [a,b] , x) ⊂ C ∩ S
and we are done.

Step 2. We suppose that b ∈ D, and that the property P(a) holds for all a < b. We prove that the property P(b) holds.

Let C be a s-a connected component of V ≤b . If C b = ∅, there is nothing to prove. Suppose that C b is non-empty; we have to prove that C ∩ S is s-a connected.

If dim(C) = 0, C is a point, belonging to M ⊂ S by Lemma 3.6. So C ∩ S is s-a connected.

Hence, we can assume that dim(C) > 0, so that C <b is non-empty by Lemma 3.6.

Our aim is to prove that C ∩ S is s-a connected. We do this in two steps. We prove the following statements:

(a) If B is a s-a connected component of C <b , then B ∩ S is s-a connected, and, using (a), (b) C ∩ S is non-empty and s-a connected. Proof of (a) We prove that if B is a s-a connected component of C <b , then B ∩ S is s-a connected.

Since B contains a point of M it follows that B ∩ S is not empty. Note that if B ∩ S = B ∩ S, then there exists a with max({π

1 (x) | x ∈ B ∩ S}) < a < b,
with B ∩ S = (B ∩ S) ≤a and B ≤a s-a connected using Lemma 3.7. So B ∩ S is s-a connected since the property P(a) holds. We now suppose that (B \ B) ∩ S is non-empty. Taking x ∈ (B \ B) ∩ S, we are going to show that x can be connected to a point z in B ∩ S by a s-a path γ inside B ∩ S. Notice that π 1 (x) = b.

We first prove that we can assume without loss of generality that x ∈ W (p) . Otherwise, since x ∈ S and S = W (p) ∪ V N ∪N (p) , we must have that x ∈ V y with

y = π [1,p] (x), and V y ⊂ S. Let A = C(V y ∩ B, x). We now prove that A ∩ W (p) y = ∅. Using the Curve Selection Lemma [4, Theorem 2.5.5] choose a s-a path γ : [0, ε] → Ext(B, R ε ) such that γ(0) = x, lim ε γ(ε) = x and γ((0, ε]) ⊂ Ext(B, R ε ). Let y ε = π [1,p] (γ(ε)) and A(ε) = C(Ext(B, R ε ) y(ε) , γ(ε)). Note that x ∈ lim ε A(ε) ⊂ A. By Remark 3.5, Ext(B, R ε ) is a s-a connected component of Ext(V <b , R ε ) which implies that A(ε) is a s-a connected component of Ext(V, R ε ) y(ε) . By Property 3.2 (2) and Remark 3.5, Ext(W (p) , R ε ) y(ε) ∩ A(ε) = ∅. Then, since Ext(W (p) , R ε ) y(ε) ∩ A(ε) is bounded over R, we deduce that lim ε (Ext(W (p) , R ε ) y(ε) ∩ A(ε)) is a non-empty subset of W (p) y ∩ A. Now connect x to a point x ′ ∈ W (p) y by a s-a path whose image is contained in A ⊂ B y ⊂ (B \ B) ∩ S. Thus, replacing x by x ′ if necessary we can assume that x ∈ W (p) as claimed.
There are four cases, namely

(1) x ∈ M ∪ M (p) ; (2) x ∈ M ∪ M (p) and C(W (p) b , x) ⊂ B; (3) x ∈ M ∪ M (p) , C(W (p) b , x) ⊂ B and b ∈ D (p) ; (4) x ∈ M ∪ M (p) , C(W (p) b , x) ⊂ B and b ∈ D (p)
; that we consider now.

(

) x ∈ M ∪ M (p) : Define y = π [1,p] (x) ∈ R p , and note that V y ⊂ S. Since x ∈ B, and B is bounded, y ∈ π [1,p] (B) = π [1,p] (B) 1
. Now let ε > 0 be an infinitesimal. By applying the Curve Selection Lemma [4, Theorem 2.5.5] to the set B and x ∈ B, and then projecting to R p using π [1,p] we obtain that there exists y(ε) ∈ R ε p infinitesimally close to y with π 1 (y(ε)) < π 1 (y) = b, and

x ∈ lim ε Ext(V, R ε ) y(ε) . Let x(ε) ∈ Ext(V, R ε ) y(ε) be such that lim x(ε) = x.
Moreover, by Property 3.2 (2) and Remark 3.5 we have that Ext(W (p) , R ε ) y(ε) is non-empty and meets every s-

a connected component of Ext(V, R ε ) y(ε) . Note that Ext(V, R ε ) y(ε) = Ext(V ≤b , R ε ) y(ε) = Ext(V <b , R ε ) y(ε) . Let x ′ (ε) ∈ Ext(W (p) , R ε ) y(ε) ∩ C(Ext(B, R ε ) y(ε) , x(ε)),
and

x ′ = lim ε x ′ (ε). Since lim ε x(ε) = x and lim ε C(Ext(B, R ε ) y(ε) , x(ε)) is s-a connected, lim ε C(Ext(B, R ε ) y(ε) , x(ε)) ⊂ C(B y , x).
Now choose a s-a path γ 1 connecting x to x ′ inside C(B y , x) (and hence inside S since C(B y , x) ⊂ V y ⊂ S). Since x ′ (ε) has coordinates which are algebraic Puiseux series in ε, there exists a positive element t 0 ∈ R, and a s-a curve γ 2 : [0, t 0 ] → R k defined over R, such that x ′ = γ 2 (0), and

x ′ (ε) ∈ Ext(γ 2 , R ε )(ε) (see [2, Theorem 3.14]). The concatenation of Ext(γ 1 , R ε ), Ext(γ 2 , R ε )| [0,ε]
gives a s-a path γ having the required property, after replacing ε by a sufficiently small positive element of R.

(2) x ∈ M ∪ M (p) and C(W

(p) b , x) ⊂ B: There exists x ′ ∈ C(W (p) b , x), x ′ ∈ B and a s-a path γ : [0, 1] → C(W (p) b , x), with γ(0) = x, γ(1) = x ′ . Since x ′ ∈ B, it follows that for t 1 = max{0 ≤ t < 1 | γ(t) ∈ B}, γ(t 1 ) ∈ M.
To see this observe that by Lemma 3.6 (2c), it follows that γ(t 1 ) ∈ B ∩ B ′ , where B ′ is a s-a connected component of C <b distinct from B. It then follows from Lemma 3.6 (2b) that γ(t 1 ) ∈ M. We can now connect γ(t 1 ) to a point in B ∩ S by a s-a path inside B ∩ S using (1). (p) . Thus, there exists a s-a path connecting x to x ′ ∈ M (p) with image contained in B ∩ W (p) ⊂ B ∩ S. We can now connect x ′ to a point in B ∩ S by a s-a path inside B ∩ S using (1). ( 4)

(3) x ∈ M ∪ M (p) , C(W (p) b , x) ⊂ B and b ∈ D (p) : Since b ∈ D (p) by Property 3.2 (3) there exists x ′ ∈ C(W (p) b , x)∩M
x ∈ M ∪ M (p) , C(W (p) b , x) ⊂ B and b ∈ D (p) : Since b ∈ D (p) , for all a < b such that [a, b] ∩ D (p) = ∅, C(W (p) [a,b] , x) b = C(W (p) b , x) and C(W (p) [a,b] , x) a = ∅ by Property 3.2 (3). Let x ′ ∈ C(W (p) [a,b] , x) a . We can choose a s-a path γ : [0, 1] → C(W (p) [a,b] , x) with γ(0) = x, γ(1) = x ′ . Let t 1 = max{0 ≤ t < 1]; | γ(t) ∈ W (p)
b }. Then, either γ(t 1 ) ∈ M and we can connect γ(t 1 ) to a point in B ∩ S by a s-a path inside B ∩ S using [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF]. Otherwise, by Lemma 3.6 (2 b), for all small enough r > 0, B k (γ(t 1 ), r) ∩ C <b is non-empty and contained in B. Then, there exists t 2 ∈ (t 1 , 1] such that γ(t 2 ) ∈ B ∩ W (p) ⊂ B ∩ S, and the s-a path γ| [0,t2] gives us the required path in this case. Take x and x ′ in B ∩ S. They can be connected to points z and z ′ in B ∩ S by s-a paths γ and γ ′ inside B ∩ S such that, without loss of generality, π 1 (z) = π 1 (z ′ ) = a with a < b, and ba arbitrarily small. Since B is a s-a connected component of C <b , it follows from Hardt's s-a triviality theorem [2, Theorem 5.45] that for all a < b with ba sufficiently small, B ≤a is non-empty and connected, and hence B ≤a is a s-a connected component of C ≤a . Now, using property P(a), we conclude that property P(b) holds. Proof of (b) We have to prove that C ∩ S is non-empty and s-a connected.

Since we suppose that dim(C) > 0, C <b is non-empty by Lemma 3.6 (2). Let B be a s-a connected component of C <b . We have from (a) that B ∩ S is non-empty, and since B ⊂ C, it follows that C ∩ S is not empty.

We now prove that C ∩ S is s-a connected. Let x and x ′ be in C ∩ S. We prove that it is possible to connect them by a s-a path inside C ∩ S. Using Lemma 3.6 (2c), let B i (resp. B j ) be a s-a connected component of C <b such that x ∈ B i (resp.

x ′ ∈ B j ).

If i = j, x and x ′ both lie in B i ∩ S which is s-a connected by (a). Hence, they can be connected by a s-a connected path in

B i ∩ S ⊂ C ∩ S.
So let us suppose that i = j. Note that:

• by Lemma 3.6 (2a), B i ∩ M and B j ∩ M are not empty,

• by (a) B i ∩ S and B j ∩ S are s-a connected,

• by definition of S, M ⊂ S.

Then, one can connect x (resp. x ′ ) to a point in B i ∩M (resp. B j ∩M). This shows that one can suppose without loss of generality that x ∈ B i ∩ M and x ′ ∈ B j ∩ M. Let γ : [0, 1] → C be a s-a path that connects x to x ′ , and let

G = γ -1 (C ∩ M) and H = [0, 1] \ G.
Since M is finite, we can assume without loss of generality that G is a finite set of points, and H is a union of a finite number of open or half-open intervals.

Since γ(G) ⊂ M ⊂ S, it suffices to prove that if t and t ′ are the end points of an interval in H, then γ(t) and γ(t ′ ) are connected by a s-a path inside C ∩ S.

Notice that γ((t, t ′ )) ∩ M = ∅, so that γ(t) and γ(t ′ ) belong to the same B ℓ by Lemma 3.6 (2b). Recall now that γ(t) and γ(t ′ ) both lie in B ℓ ∩ S and that B ℓ ∩ S is s-a connected by (a). Consequently, γ(t) and γ(t ′ ) can be connected by a s-a path in B ℓ ∩ S ⊂ C ∩ S.

We are going to need the following corollary.

Corollary 3.9. Let V, M, W (p) , M (p) , D (p) satisfy Property 3.2, N = π [1,p] (M), N (p) = π [1,p] (M (p) ),
and

N ′ ⊂ R p a finite set containing N ∪ N (p) . For every s-a connected component C of V , C ∩ (W (p) ∪ V N ′ ) is s-a connected.
Proof. Follows immediately from Proposition 3.3 and Property 3.2 b).

Block representations and curve segments

We denote by D an ordered domain contained in a real closed field R and by C the algebraically closed field R[ √ -1]. All the polynomials in the input and output of our algorithms have coefficients in D and the complexity of our algorithms is measured by the number of arithmetic operations (addition, multiplication, sign determination) in D.

In this section, we first define certain representations of points, as well as of s-a curves, that are going to be used in the inputs and outputs of our algorithms. Several of these representations share the common property that a certain initial number of coordinates are fixed by a triangular system of equations, along with certain Thom encodings and the remaining coordinates are defined by rational functions to be evaluated at a fixed real root of another polynomial (see Definitions 4.1 and 4.8 below). The structure of these representations reflect the recursive structure of our main algorithms described in Section 7.

After defining these representations, we recall the input, output and an upper bound on the complexity of a key algorithm, Algorithm 1(Curve Segments), which is described in full detail in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]. Algorithm 1 accepts as input a polynomial defining a bounded real algebraic variety (with some coordinates fixed by a triangular system as mentioned above), and outputs a s-a partition of the first (non-fixed) coordinate, as well as descriptions of s-a curve segments (as well as points) parametrized by this coordinate satisfying certain properties -which are the key to the construction of the main roadmap algorithm. Indeed, the curve segments appearing in the output of the main roadmap algorithm (Algorithm 7) are limits of the curve segments output by the various calls to Algorithm 1.

We begin with a few definitions.

Definition 4.1. A Thom encoding f, σ representing an element α ∈ R consists of (1) a polynomial f ∈ D[T ] such that α is a root of f in R, (2)
a sign condition σ on the set Der(f ) of derivatives of f , such that σ is the sign condition satisfied by Der(f ) at α. If (f, σ) is a Thom encoding representing an element α ∈ R, we will sometimes abuse notation slightly and say that σ is the Thom encoding of the real root α of f .

Distinct roots of f in R correspond to distinct Thom encodings [2, Proposition 2.28].

A real univariate representation g, τ, G representing x ∈ R k consists of (1) a Thom encoding g, τ representing an element

β ∈ R, (2) G = (g 0 , g 1 , . . . , g k ) ∈ D[T ] k+1
where g and g 0 are co-prime and such that

x = g 1 (β) g 0 (β) , . . . , g k (β) g 0 (β) ∈ R k .
4.1. Block representations. In our algorithms, we make recursive calls, where we fix blocks of several coordinates. This makes necessary the following rather technical definitions.

Definition 4.2. A triangular Thom encoding F = (f [1] , . . . , f [m] ), σ representing t = (t 1 , . . . , t m ) in R m consists of (1) a triangular system F = (f [1] , . . . , f [m] ), i.e. f [i] ∈ D[T 1 , . . . , T i ] for i = 1, . . . , m, such that the zero set of F in C m is finite;
(2) a list, σ = (σ 1 , . . . , σ m ), where for i = 1, . . . , m, σ i is the Thom encoding of the root

t i of f [i] (t 1 , . . . , t i-1 , T i ). A triangular system F = (f [1] , . . . , f [m] ) is quasi-monic if the leading coefficient of f [i] ∈ D[T 1 , . . . , T i ] with respect to T i is a strictly positive element in D and deg Ti (f [j] ) < deg Ti (f [i] ), j > i. A triangular Thom encoding F = (f [1] , . . . , f [m] ), σ is quasi-monic if F = (f [1] , . . . , f [m] ) is quasi-monic. Let F = (f [1] , . . . , f [m]
) be a quasi-monic triangular system. Let c ∈ D, c strictly positive and g ∈ D[T 1 , . . . , T m ], we say that cg has a reduction in

D modulo F if there exists a polynomial ḡ ∈ D[T 1 , . . . , T m ] such that deg Ti (ḡ) < deg Ti (f [i] ) for i = 1, . . . , m and cg = ḡ mod I(F), where I(F) is the ideal of D[T 1 , . . . , T m ] generated by f [1] , . . . , f [m]
. The polynomials ḡ is unique with these properties since a quasi-monic triangular system is a Groebner basis with respect to the lexicographical ordering. We say that the couple (c, ḡ) is a pseudo-reduction of g.

Note that at the zeros of F the signs of g and ḡ coincide.

ℓ = ℓ 1 + • • • + ℓ m ;
(3) a list of polynomials F = (F [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF] , . . . , F [m] ), where

F [i] = (f [i]0 , . . . , f [i]ℓi ), f [i]j ∈ D[T 1 , . . . , T i ], 0 ≤ j ≤ ℓ i , with f [i] (t 1 , . . . , t i-1 , T i ), f [i]0 (t 1 , . . . , t i-1 , T i ) coprime (as polynomials in T i ), such that y = (y [1] , . . . , y [m] ) ∈ R ℓ , with y [i] = f [i]1 (t 1 , . . . , t i ) f [i]0 (t 1 , . . . , t i ) , . . . , f [i]ℓi (t 1 , . . . , t i ) f [i]0 (t 1 , . . . , t i ) , 1 ≤ i ≤ m.
In the case

ℓ 1 = • • • = ℓ m = p we will write L = [p m ]. (4.1)
Notation 4.5 (Substituting a real block representation in a polynomial). Let F, σ, L, F be a real block representation representing y ∈ R ℓ , and let t ∈ R m be represented by F, σ. Let

f[i] (T 1 , . . . , T i ) = f [i]1 (T 1 , . . . , T i ) f [i]0 (T 1 , . . . , T i ) , . . . , f [i]ℓi (T 1 , . . . , T i ) f [i]0 (T 1 , . . . , T i ) . Given Q ∈ D[X 1 , . . . , X k ] with ℓ ≤ k, we set T = (T 1 , . . . , T m ), and define Q F ∈ D[T, X ℓ+1 , . . . , X k ] by Q F := f0 (T )Q f[1] (T 1 ), . . . , f[m] (T 1 , . . . , T m ), X ℓ+1 , . . . , X k , (4.2) where f0 (T ) = m i=1 f [i]0 (T 1 , . . . , T i ) ei ,
and e i is the smallest even number ≥ deg

X [i] (Q), where X [i] is the block of variables X ℓ1+•••+ℓi-1+1 , . . . , X ℓ1+•••+ℓi . Note that Q F (t, X ℓ+1 , . . . , X k ) = f0 (t)Q(y, X ℓ+1 , . . . , X k ), with f0 (t) > 0. More generally , for any family of polynomials Q ⊂ D[X 1 , . . . , X k ] with ℓ ≤ k, we will denote Q F = {Q F | Q ∈ Q}.
Notation 4.6 (Substituting a real block representation in a parametrized univariate representation). Let F, σ, L, F be as above and let g, G with G = (g 0 , g ℓ+1 , . . . , g k ), be a parametrized univariate representation, i.e. g, g 0 , g ℓ+1 , . . . , g k ∈ D[X 1 , . . . , X ℓ , U ], where X 1 , . . . , X ℓ are the parameters, and U a single variable.

We denote by G F the tuple (g 0,F , . . . , g k,F ), where each g i,F ∈ D[T, U ] and is defined by

g i,F := f0 (T )g i f[1] (T 1 ), . . . , f[m] (T 1 , . . . , T m ), X ℓ+1 , . . . , X k , (4.3)
where

f0 (T ) = m i=1 f [i]0 (T 1 , . . . , T i ) ei ,
and e i is the smallest even number ≥ max j deg X [i] (g j ).

Definition 4.7. Let t ∈ R m be represented by a triangular Thom encoding F, σ.

A Thom encoding g, τ representing β over t consists of (using the same notation as above)

(1) a polynomial g ∈ D[T 1 , . . . , T m , T ] such that g(t, β) = 0, (2) a sign condition τ on Der T (g) such that τ is the sign condition satisfied by the set Der T (g(t, T )) at β. A real univariate representation representing x ∈ R k over t consists of (1) a Thom encoding g, τ representing β over t,

(2) G = (g 0 , g 1 , . . . , g k ) ∈ D[T 1 , . . . , T m , U ] k+1 such that g(t, U ), g 0 (t, U ) are coprime, and such that

x = g 1 (t, β) g 0 (t, β) , . . . , g k (t, β) g 0 (t, β) ∈ R k .
A real univariate representation over t is quasi-monic if the leading monomial of g with respect to U is in D.

A triangular Thom encoding representing z = (z 1 , . . . , z r ) over t with variables Z 1 , . . . , Z r consists of (1) a triangular system H = (h 1 , . . . , h r ), with

h i ∈ D[T 1 , . . . , T m , Z 1 , . . . , Z i ]
for i = 1, . . . , r, such that the zero set of H(t, Z 1 , . . . , Z r ) in C r is finite;

(2) a list, ρ = (ρ 1 , . . . , ρ r ), where for i = 1, . . . , r, ρ i is the Thom encoding of the root z i of h i (t, z 1 , . . . , z i-1 , Z i ).

4.2. Curve segments.

Definition 4.8. Let t ∈ R m be represented by a triangular Thom encoding F, σ.

A curve segment with parameter X j over t on (α

1 , α 2 ) in R k , f 1 , σ 1 , f 2 , σ 2 , g, τ, G
is given by (1) α 1 , α 2 ∈ R represented by Thom encodings f 1 , σ 1 and f 2 , σ 2 over t;

(2) a parametrized univariate representation with parameter X j , i.e.

g, G = (g 0 , g 1 , . . . , g k ),

with g j = X j g 0 and g, g 0 , . . . , g k in D[T 1 , . . . , T m , X j , U ]; (3) a sign condition τ on Der U (g) such that for every x j ∈ (α 1 , α 2 ) there exists a real root u(x j ) of g(t, x j , U ) with Thom encoding τ , and g 0 (t, x j , u(x j )) = 0. The curve represented by f 1 , σ 1 , f 2 , σ 2 , g, τ, G is the image of the smooth injective s-a function γ which maps a point x j of (α 1 , α 2 ) to the point of R k defined by

γ(x j ) = g 1 (t, x j , u(x j )) g 0 (t, x j , u(x j )) , . . . , g k (t, x j , u(x j )) g 0 (t, x j , u(x j )) . Let Q ∈ R[X 1 , . . . , X k ]. For 0 ≤ ℓ < k and y ∈ R ℓ , we write Q(y, -) def = Q(y 1 , . . . , y ℓ , X ℓ+1 , . . . , X k ). (4.4)
Remark 4.9. Abusing notation slightly, we will occasionally identify

Zer(Q(y, -), R k-ℓ ) ⊂ R k-ℓ with {y} × Zer(Q(y, -), R k-ℓ ) = Zer(Q, R k ) y ⊂ R k .
More generally, for a s-a set A ⊂ R k , we will occasionally identify

{x ∈ R k-ℓ | (y, x) ∈ A y } with A y ⊂ R k .
We now recall the input, output and complexity of [ (mk) . Moreover, the degree in T i of the polynomials appearing in the output is bounded by Dd O(k) .

Low dimensional roadmap in a special case

In this section we describe an algorithm for computing the roadmap of a variety described by equations having a special structure. Although, this algorithm is very similar to [2, Algorithm 15.3 (Bounded Algebraic Roadmap)], the complexity analysis differs because of the special structure assumed for the input.

Let

Q ∈ R[X 1 , . . . , X k ] and suppose that V = Zer(Q, R k ) is bounded. For 0 ≤ ℓ < k, 0 ≤ p ≤ k -ℓ, and y ∈ R ℓ , we write Cr ℓ+p (Q)(y, -) def = Q(y, -), ∂Q ∂X ℓ+p+2 (y, -), . . . , ∂Q ∂X k (y, -) . (5.1)
We assume that Q satisfies the following property.

Property 5.1. For every ℓ, 0 ≤ ℓ < k, 0 ≤ p < kℓ, and y ∈ R ℓ , the algebraic set

W (p) y = Zer(Cr ℓ+p (Q)(y, -), R k-ℓ )
is of dimension p or empty.

Remark 5.2. Note that for every y ∈ R ℓ , z ∈ R r , (W Step 0. If mp + r ≥ k then exit. Else do the following.

Step 1. Denote

P := A∈Cr (m+1)p (Q) F A 2 ∈ D[T 1 , . . . , T m , X mp+1 , . . . , X k ]
using Notation 4.5 and (5.1). Call Algorithm 1 (Curve Segments) with input (F, H), (σ, ρ), P, U 0 .

Compute a pseudo-reduction of the output of the call to Algorithm 1 (Curve Segments) in the previous step modulo F (using Proposition 8.4), and place the result in the description of RM(W

(p-r) (y,z) , M 0 ).
Step 2. Using the notation in the output of Algorithm 1, for every j = 1, . . . , N , define

z := (z, c j ), H := (H, g j (T 1 , . . . , T m , X 1 , . . . , X r+i )), ρ := (ρ, τ j ), U 0 := D j ,
and call Algorithm 2 (Roadmap for Lower Dimensional Special Algebraic Sets) recursively, with input (Q, (p, m, r + 1), (F, σ, [p m ], F ), (H, ρ), U 0 ). Include in the description of RM(W (p-r) (y,z) , M 0 ), the output of the call.

Proof of correctness. Notice that

W (p-r) (y,z) = Zer(P (t, z, -)), R k-(mp+r) ).
The correctness of the algorithm then follows from the correctness of Algorithm 1 (Curve Segments) and Proposition 2.2. The only additional fact that needs to be checked is that when the recursion ends with r = kmp ≤ p, the algebraic variety Zer(P ((t, z, z ′ ), -), R k-p(m+1) ) is finite, where z ′ = (c j1 , . . . , c jp-r ) ∈ R p-r and the various c ji ∈ R are associated to the Thom encodings computed in Step 1 of the algorithm. This is the case because Zer(P ((t, z, z ′ ), -), R k-p(m+1) ) = W

Complexity analysis.

The depth i of the recursion is bounded by pr, and the total number of recursive calls at depth i is bounded by d O(ik) . Thus, there are at most d O((p-r)k) calls to Algorithm 1 (Curve Segments).

In each of the calls to Algorithm 1 (Curve Segments), the number of arithmetic operations in D is bounded by D O(m+p) d O((m+p)k) using the complexity analysis of Algorithm 1 ( Curve Segments). Moreover the number of arithmetic operations needed for each pseudo-reduction is (Dd k ) O(m) since the degree in T i of the output of Algorithm 1 (Curve Segments) is Dd O(k) using Remark 4.3.

Thus, the total number of arithmetic operations in D for Algorithm 2 is bounded by D O(m+p) d O((m+p)k) .

Low dimensional roadmap in general

In this section, we first explain how to perform an infinitesimal deformation of any given polynomial Q ∈ R[X 1 , . . . , X k ] such that the deformed polynomial satisfies Property 5.1.

We then sketch how to compute the limit of a curve. We also describe how to compute the limits of roadmaps of certain algebraic sets which are the critical locus of dimension p of certain projection maps restricted to the algebraic hypersurfaces obtained after performing an infinitesimal deformation. 6.1. Deformation. We consider a bounded algebraic set defined by a non-negative polynomial Q. Our aim is to define an infinitesimal deformation of Q such that the deformed polynomial satisfies Property 5.1. Suppose that the polynomial Q ∈ R[X 1 , . . . , X k ] and the tuple (d 1 , . . . , d k ) satisfy the following additional conditions:

(1)

d 1 ≥ d 2 ≥ • • • ≥ d k , (2) deg(Q) ≤ d 1 , tDeg Xi (Q) ≤ d i , for i = 2, . . . , k
, where tDeg Xi (Q) is the maximum degree amongst all monomials in Q containing X i . Let di be an even number > d i , i = 1, . . . , k, and d = ( d1 , . . . , dk ). Let

G k ( d) = X d1 1 + • • • + X dk k + X 2 2 + • • • + X 2 k + X 2 k+1 + 2k, and note that for all x ∈ R k+1 G k ( d)(x) > 0.
We denote for ever ℓ, 0 ≤ ℓ ≤ k and every y ∈ R ℓ : Notation 6.1.

Def(Q, ε) = -εG k ( d) + Q, V (ε) y = Zer(Def(Q, ε)(y, -), R ε k+1-ℓ ), Cr ℓ+p (Q, ε)(y, •) = Def(Q, ε)(y, •), ∂Def(Q, ε) ∂X p+ℓ+1 (y, •), . . . , ∂Def(Q, ε) ∂X k+1 (y, •) , W (ε) (p) y = Zer(Cr ℓ+p (Q, ε)(y, -), R ε k+1-ℓ ).
Proposition 6.2. For every ℓ, 0 ≤ ℓ ≤ k and every y ∈ R ℓ : a) Def(Q, ε) satisfies Property 5.1; b) lim ε induces a 1-1 correspondence between the bounded s-a connected components of

V (ε) y = Zer(Def(Q, ε)(y, -), R ε k+1-ℓ )
and the s-a connected components of We are going to describe in Section 6.3 an algorithm for computing the limit of a roadmap of the critical locus of dimension p, W (ε) (p) y , of V (ε) y . In order to achieve this, we first need to compute limits of curves, which is the purpose of Section 6.2. 6.2. Limits of points and curve segments. The general problem of computing the image of a s-a set S ⊂ R ε k which is bounded over R under the lim ε map reduces to the problem of computing the closure of a one-parameter family of s-a sets, which can be done using quantifier elimination algorithms (see, for example, [2, p. 556]). However, the complexity of this general algorithm, d k O (1) , is not good enough for our purposes in this paper. Fortunately, we need efficient algorithms for computing limits only in two very special situations, where we can do better than in the general case.

V y = Zer(Q(y, -), R k-ℓ ).
These two special cases are the following:

(1) when the set consists of a point represented by a real univariate representation, (2) when the set consists of a curve represented by curve segments.

We now describe the input, output and give an upper bound on the complexity of Algorithm 3 (Limit of a Bounded Point) and Algorithm 4 (Limit of a Curve). A full description of these algorithms, their correctness and complexity analysis appear in Section 8.

(p) y , of the deformation V (ε) y = Zer(Def(Q, ε)(y, -), R ε k+1-ℓ ) of V y = Zer(Q(y, -), R k-ℓ ). (ε)
The algorithm proceeds by first calling Algorithm 2 (Roadmap for Lower Dimensional Special Algebraic Sets) in order to compute a roadmap for W (ε)

(p)
y , and then computes the image of the resulting roadmap under the lim ε map. Note that this limit is not necessarily a roadmap of V y , since a s-a connected component of V y might contain the limit of more than one s-a connected component of W (ε) (2) a polynomial

Q ∈ D[X 1 , . . . , X k ] for which Z = Zer(Q, R k ) ⊂ B k (0, 1/c) (with c ∈ R); (3
R = (π [1,k] • lim ε )(RM(W (ε) (p) y , A(ε)))
where W (ε)

(p) y is the zero set of Cr ℓ+p (Q, ε)(y, -), A(ε) = z(ε)∈N (ε) W (ε) (0) y,z(ε) , (6.1)
and RM(W (ε)

(p) y , A(ε))) is a roadmap for (W (ε) (p) y , A(ε))). Complexity. D O(m+p) d O((m+p)k where d = deg(Q) ≥ 2,
and D is a bound on the degrees of F, F and the number and degrees (including that in ε) of the elements in N (ε). Procedure.

Step 1. Let T = (T 1 , . . . , T m ), and using Notation 4.5 and Notation 6.1,

P = A∈Cr (m+1)p (Q,ε) F A 2 ∈ D[ε, T, X mp+1 , . . . , X k ].
Call [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] with input P and parameters ε, T, X mp+1 , . . . , X (m+1)p and output a set of parametrized univariate representations with variable U .

Compute a pseudo-reduction of the output modulo F (using Proposition 8.4) and place the result in U (ε).

For every (h(ε), H(ε)) ∈ U(ε), and every z(ε) ∈ N (ε) represented by a real univariate representation (g(ε), τ, G(ε)) ∈ V(ε), use [2, Algorithm 12.20 (Triangular Thom Encoding)] with input the triangular system (F, g(ε), h(ε)) to compute the Thom encodings of the real roots of h(ε)(y, z(ε), U ). Let U ′ (ε) z(ε) be the set of real univariate representations over y, z(ε) so obtained. Define

U ′ (ε) = z(ε)∈N (ε) U ′ (ε) z(ε) .
The set of points represented by U (ε) ′ is A(ε) (see (6.1)). Compute the limit of A(ε) using Algorithm 3 (Limit of a Bounded Point).

Step 2. Call Algorithm 2 (Roadmap for Lower Dimensional Special Algebraic Sets) with input Def(Q, ε) (cf. Notation 6.1), the triple (p, m, 0), the real block representation F, σ, [p m ], F , and U ′ (ε) (note that since r = 0 in the input there is no triangular Thom encoding H, ρ specified in the input to this call). The output of Algorithm 2 consists of a set of real univariate representations and curve segments over triangular Thom encodings. Each such curve segment, γ(ε) = (f 1 , σ 1 , f 2 , σ 2 , g, τ, G), is defined over some (t, z γ (ε)) with r γ < p and z γ (ε) ∈ R ε rγ , represented by a triangular system F, H γ (ε). Step 3. For each such curve segment γ(ε) over (t, z γ (ε)), output in the previous step, call Algorithm 4 (Limit of a Curve) with input the triangular system F, H γ (ε) and γ(ε). Finally, project to R k by forgetting the last coordinate.

Remark 6.4. The role played by the set of points A(ε) whose limit is computed by Algorithm 5 (Limit of Roadmaps of Special Low Dimensional Varieties), will become clear in the proof of correctness of Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) (see (7.2)).

Proof of correctness. First note that it follows from Proposition 6.2 that Def(Q, ε) F satisfies Property 5.1, and hence A(ε) is a finite set of points. The correctness of the algorithm now follows from the correctness of Algorithm 2 (Roadmap for Lower Dimensional Special Algebraic Sets) and Algorithm 4 (Limit of Curve). Thus the total complexity of the algorithm is D O(m+p) d O((m+p)k) .

Complexity analysis. The number of arithmetic operations performed in D[ε] in

Main result

We now describe our main result Algorithm 7 (Baby-giant Roadmap for General Algebraic Sets). It is based on Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets), computing a baby step -giant step roadmap algorithm for a bounded algebraic set. The algorithm for computing roadmaps of general (i.e. not necessarily bounded) algebraic sets, Algorithm 7 (Baby-giant Roadmap for General Algebraic Sets) is then obtained from Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) following a method similar to the one in [2] to go from the bounded case to the general case.

Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) proceeds roughly as follows. We denote by y the vector of coordinates which are fixed. If the number of non-fixed coordinates is too small (i.e. less than the number p which is prescribed in the input), then we compute the roadmap using [2, Algorithm 15.3 (Bounded Algebraic Roadmap)]. Otherwise, we compute representations of points in N y ⊂ R p defining the fibers at which we make recursive calls to the same algorithm; these are the giant steps.

For the baby steps, the algorithm uses Algorithm 5 (Limit of Roadmaps of Special Low Dimensional Varieties) to compute the limit (under the lim ε map) of the roadmap of the critical set W (p) y,ε going through a well chosen finite set of points. We are now ready to proceed to the description of Algorithm 6. We first introduce some notation to be used in the description of Algorithm 6 and the proof of its correctness.

Notation 7.1. The input of the algorithm involves [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF]

a polynomial Q ∈ D[X 1 , . . . , X k ] such that V = Zer(Q, R k ) ⊂ B k (0, 1/c) (where c ∈ R); (2) y ∈ R mp (3) a finite set of points M 0 ⊂ V y = Zer(Q(y, -), R k-mp ).
Let as in Notation 6.1

V (ε) y = Zer(Def(Q, ε)(y, -), R ε k-pm+1 ), W (ε) (p) y = Zer(Cr ℓ+p (Q, ε)(y, -), R ε k-pm+1 ),
and define

(1)

M(ε) = W (ε) (0) y ⊂ V (ε) y ; (2) D(ε) (p) ⊂ R ε the set of pseudo-critical values (see [2, Definition 12.41]) of π ℓ+1 on W (ε) (p)
y and M(ε) (p) a set of points such that for every c ∈ D(ε) (p) , M(ε) (p) intersects every s-a connected component D of (W (ε) (p) y ) c . It follows from Proposition 6.2 and Proposition 5.3 that

V (ε) y , M(ε), W (ε) (p) y , M(ε) (p) , D(ε) (p)
satisfies Property 3.2. We also define

N (ε) = π [mp+1,(m+1)p] (M(ε)), N = lim ε (N (ε)), N (ε) (p) = π [mp+1,(m+1)p] (M(ε) (p) ), N (p) = lim ε (N (ε) (p) ), N 0 = π [mp+1,(m+1)p] (M 0 ), N ′ = N 0 ∪ N ∪ N (p) , N ′ (ε) = N 0 ∪ N (ε) ∪ N (ε) (p) .
Algorithm 6. [Baby-giant Roadmap for Bounded Algebraic Sets]

Input. (1) a polynomial Q ∈ D[X 1 , . . . , X k ] such that V = Zer(Q, R k ) ⊂ B k (0, 1/c) (where c ∈ R); (2) y ∈ R mp represented by a real block representation F, σ, [p m ], F,
(see (4.1)) such that t ∈ R m is represented by a quasi-monic triangular Thom encoding F, σ;

(3) a finite set of points M 0 in V y = Zer(Q(y, -), R k-mp ) represented by quasi-monic real univariate representations U 0 over t. All the coefficients of the input polynomials are in D. Output. a representation of a roadmap, BGRM(V y , M 0 ), for (V y , M 0 ). Complexity. d O(k 2 /p+pk) operations in D where d = deg(Q) ≥ 2 and the degrees of the polynomials in F, F , as well as the degrees of the polynomials and the number of elements in U 0 are all bounded by d O(k) . Procedure.

Step 1. If (m + 1)p ≥ k call [2, Algorithm 15.3 (Bounded Algebraic Roadmap)] with input (1) the quasi-monic triangular Thom encoding F, σ representing t ∈ R m , (2) the polynomial Q F , using Notation 4.5, (3) the finite set of points M 0 in V y = Zer(Q F (t, -), R k-mp ) represented by real univariate representations U 0 over t. Otherwise, do the following.

Step 2. Determine the finite set of points N , and their representation U used in the recursive call as follows.

Let T = (T 1 , . . . , T m ), and using Notation 4.5 and 6.1),

P = A∈Cr (m+1)p (Q,ε) F A 2 ∈ D[ε, T, X mp+1 , . . . , X k ].
Step 2 a). Call [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] with input P and parameters ε, T , and output a set of parametrized univariate representations with variable U . Compute a pseudo-reduction of the output modulo F (using Proposition 8.4) and place the result in U (ε).

For every (h(ε), H(ε)) ∈ U(ε), use [2, Algorithm 12.20 (Triangular Thom Encoding)] with input the triangular system (F, h(ε)) to compute the Thom encodings of the real roots of h(ε)(y, U ). Let U ′ (ε) be the set of real univariate representations over y so obtained. Let M(ε) ⊂ V (ε) y be the set of points represented by U ′ (ε).

Projecting U ′ (ε), by forgetting its components corresponding to the last k -(m + 1)p coordinates obtain a set of quasi-monic real univariate representations V(ε) representing N (ε) over t. Then apply Algorithm 3 (Limit of a Bounded Point) with V(ε) y as input to obtain a set of quasi-monic real univariate representations V representing N over t.

Step 2 b). Perform Algorithm 1 (Curve Segment) with input P and the triangular Thom encoding F, σ and retain the set of univariate representations, U (ε) (p) , representing M(ε) (p) ⊂ V (ε) y , which are the distinguished points in the output.

Projecting U (ε) (p) , by forgetting its components corresponding to the last k -(m + 1)p coordinates obtain a set of real univariate representations V(ε) (p) representing N (ε) (p) . Then apply Algorithm 3 (Limit of a Bounded Point) with V(ε)

(p)
y as input to obtain a set of quasi-monic real univariate representations V (p) representing N (p) .

Step 2 c). Projecting U 0 , by its components corresponding to the last k -(m + 1)p coordinates obtain a set of quasi-monic real univariate representations V 0 representing N 0 over t. Let

V ′ = V 0 ∪ V ∪ V (p) ,
and

V ′ (ε) = V 0 ∪ V(ε) ∪ V(ε) (p) .
Step 3. Call Algorithm 5 (Limit of Roadmaps of Special Low Dimensional Varieties) with input p, Q, the real block representation F, σ, [p m ], F , and V ′ (ε) y and note that the one-dimensional s-a set described by the output contains the image under the (π [1,k] • lim ε ) map of the finite set

A(ε) = z(ε)∈N ′ (ε) W (ε) (0) y,z(ε) .
Place the result in the output. Recursive call. For every element u = ((F, h), (σ, τ ), (F, H)) ∈ V ′ , representing (y, z) ∈ N ′ ⊂ R (m+1)p , determine a set, U z , of quasi-monic univariate representations over u representing

M z = (π [1,k] • lim ε )   z(ε)∈N ′ (ε),limε(z(ε))=z W (ε) (0) y,z(ε)   (7.1)
using Algorithm 3 (Limit of a Bounded Point). Call Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) recursively with input Q, (F, h), (σ, τ ), [p m+1 ], (F, H), and U z ∪ (U 0 ) z , where (U 0 ) z is a set of quasi-monic real univariate representations representing (M 0 ) z . Remark 7.2. Algorithm 6 would have been much simpler if we could make recursive calls to Algorithm 6 at the fibers over the points in N ε , and thus obtain a roadmap first of V (ε) y , and finally take the image of the resulting roadmap under the lim ε map. In this case the proof of correctness of the algorithm would be an immediate consequence of the main connectivity result, Corollary 5.3, and the fact that the image under lim ε of a bounded, s-a connected set is also s-a connected.

However, we are unable to compute efficiently limits of s-a curves given by curve segments over a real block representation which depend on ε, if the number of blocks and their sizes are large. More precisely, if the number of blocks as well as the sizes of the blocks are proportional to √ k, then the procedure that we use to compute limits of curve segments could produce polynomials with degrees as large as d ck 2 in ε where c is some constant > 0. This is unacceptable since we are aiming for a roadmap algorithm having complexity d O(k √ k) . We overcome this difficulty by making recursive calls to Algorithm 6, not at the fibers over the points in N (ε), but at the fibers over N = lim ε (N (ε)), so that the algebraic sets specified in the input to the various recursive calls are then V (y,z) for z ∈ N . In this approach, the only limits of curve segments that are computed are those of the roadmap of W (ε)

(p)
y , and we can compute the limits of these curve segments without spoiling the complexity, as they are not defined over real block representations depending on ε. However, since the recursive calls are made with fibers of V y (instead of V (ε) y ), Corollary 5.3 is not directly applicable, and we need to be more careful about choosing the set of points in the input to the recursive calls. It also makes the proof of correctness more complicated.

Proof of correctness.

Base case.

If ⌈(kmp)/p⌉ = 1 then the correctness of the algorithm is a consequence of the correctness of [2, Algorithm 15.3 (Bounded Algebraic Roadmap)].

General case.

Suppose that ⌈(kmp)/p⌉ > 1.

Denote by BGRM(V y , M 0 ) the union of the curve segments output by Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets).

We have that

BGRM(V y , M 0 ) = R ∪ (y,z)∈N ′ BGRM(V (y,z) , M z ∪ (M 0 ) z ), with R = (π [1,k] • lim ε )(RM(W (ε) (p) y , A(ε))),
denoting as before by W (ε)

(p)
y the zero set of Cr (m+1)p (Q, ε) F and

A(ε) = z(ε)∈N ′ (ε) W (ε) (0) y,z(ε) (see Notation 7.1). Proof of M 0 ⊂ BGRM(V y , M 0 ).
The proof is by induction on ⌈(kmp)/p⌉. We suppose by induction that for every (y, z)

∈ N M z ∪ (M 0 ) z ⊂ BGRM(V (y,z) , M z ∪ (M 0 ) z ).
Since M 0 ⊂ (y,z)∈N (M 0 ) z , and by induction hypothesis we have that

(M 0 ) z ) ⊂ BGRM(V (y,z) , M z ∪ (M 0 ) z ), it is clear that BGRM(V y , M 0 ) contains M 0 . Proof of RM 1 .
The property RM 1 of BGRM(V y , M 0 ) is also proved by induction on ⌈(kmp)/p⌉.

Let C be a s-a connected component of V y , and

C ′ = BGRM(V y , M 0 ) ∩ C. We want to prove that C ′ is s-a connected.
Supposing that x, x ′ ∈ C ′ , we are going to prove that there exists a s-a path

γ : [0, 1] → C ′ with γ(0) = x, γ(1) = x ′ .
Without loss of generality we can suppose that x ∈ R:

Since BGRM(V y , M 0 ) = R ∪ (y,z)∈N ′ BGRM(V (y,z) , M z ∪ (M 0 ) z ),
we have that x (resp. x ′ ) belongs to R or to some BGRM(V (y,z) , 2), and hence we have that W (ε) (0) (y,z) meets every s-a connected component of V (ε) (y,z) . By [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Lemma 15.6] each s-a connected component of V (y,z) is the image under π [1,k] • lim ε of a unique s-a connected component of V (ε) (y,z) . It follows that each s-a connected component of V (y,z) meets

M z ∪ (M 0 ) z ) with (y, z) ∈ N ′ . If x ∈ BGRM(V (y,z) , M z ∪ (M 0 ) z ) we show that x can be connected to a point in M z inside BGRM(V (y,z) , M z ∪ (M 0 ) z ) by a s-a path. It follows from Proposition 5.3 that Def(Q, ε) F satisfies Property 3.2 (
π [1,k] • lim ε (W (ε) (0) (y,z) ) ⊂ M z , since W (ε) (0) (y,z) = (W (ε) (p) y ) z .
Finally, applying the induction hypothesis to BGRM(V (y,z) , M z ∪ (M 0 ) z ) we have that the intersection of BGRM(V (y,z) , M z ∪ (M 0 ) z ) with each s-a connected component of V (y,z) is non-empty and s-a connected, and meets M z . Thus, there exists a s-a path in BGRM(V (y,z) , M z ∪ (M 0 ) z ) joining x to a point in M z .

Since M z ⊂ R we can assume that x (and similarly x ′ ) is contained in R.

Connectivity when x and x

′ are contained in R. Since R = (π [1,k] • lim ε )(RM(W (ε) (p) y, , A(ε))), there exists x(ε) ∈ RM(W (ε) (p) y , A(ε)) (resp. x ′ (ε) ∈ RM(W (ε) (p) y , A(ε))) such that lim ε (x(ε)) = x (resp. lim ε (x ′ (ε)) = x ′ ). Let S(ε) = W (ε) (p) y ∪ (V (ε) y ) N ′ (ε) , and C(ε) the unique s-a connected component of V (ε) y such that (π [1,k] •lim ε )(C(ε)) = C.
By Corollary 3.9, since

N (ε) ∪ N (ε) (p) ⊂ N ′ (ε), S(ε) ∩ C(ε) is s-a connected. So there exists a s-a path γ(ε) : [0, 1] → S(ε) ∩ C(ε), with γ(ε)(0) = x(ε), γ(ε)(1) =
x ′ (ε). Moreover, there exists a partition of (0, 1) ⊂ R ε into a finite number of open intervals and points, such that for every open interval I in the partition one of the following holds : Case 1:

γ(ε)(I) ⊂ W (ε) (p) y . Case 2: there exists z(ε) ∈ N ′ (ε) such that γ(ε)(I) ⊂ V (ε) (y,z(ε)) . Since W (ε) (p) y ⊂ V (ε) y , for each point a ∈ (0, 1) defining the partition γ(ε)(a) ∈ A(ε) ⊂ RM(W (ε) (p) y , A(ε)). (7.2)
Hence, by definition of M z (see (7.1))

(π [1,k] • lim ε )(γ(ε)(a)) ∈ M z , (7.3)
where lim ε (z(ε)) = z.

In Case 1, we can replace γ(ε)(I) by a s-a path having the same endpoints and whose image is contained in RM(W (ε) (p) y , W N ′ (ε) ) using RM 1 as well as (7.2). Taking the image under π [1,k] • lim ε of this new path we obtain a s-a path γ : lim

ε (I) → R.
In Case 2, writing

I = (a, b), (π [1,k] • lim ε )(γ(ε)(a)), (π [1,k] • lim ε )(γ(ε)(b)) both belong to BGRM(V (y,z) , M z ∪ (M 0 ) z )
using (7.3). Using the induction hypothesis for BGRM(V (y,z) , M z ∪ (M 0 ) z ) there exists a s-a path

γ : [lim(ε)(a), lim(ε)(b)] → BGRM(V (y,z) , M z ∪ (M 0 ) z ).
Finally, we have constructed a s-a path γ : [0, 1] → C ′ with γ(0) = x, γ(1) = x ′ . This proves that BGRM(V (y,z) , M z ∪(M 0 ) z )∩C is non-empty and s-a connected proving RM 1 . Proof of RM 2 .

Let c ∈ R such that V (y,c) is not empty, and let C be a s-a connected component of V (y,c) . We prove that

BGRM(V (y,z) , M z ∪ (M 0 ) z ) ∩ C is not empty. It follows from [3, Lemma 15.6 ] that there exists a s-a connected component C(ε) of V (ε) (y,c) such that C = (π [1,k] • lim ε )(C(ε)). Since C(ε) is non-empty, let x(ε) ∈ C(ε) and let z(ε) = π [mp+1,(m+1)p] (x(ε)). It follows from Proposition 5.3 that (W (ε) (p) y ) z(ε) = W (ε) (0) (y,z(ε)) meets every s-a con- nected component of V (ε) (y,z(ε)) . Since C(ε) contains a s-a connected component of V (ε) (y,z(ε)) , we have that W (ε) (0) (y,z(ε)) ∩ C(ε) = ∅,
and thus C(ε) contains a s-a connected component of (W (ε)

(p) y ) c (since W (ε) (p) y ⊂ V (ε) y ). Now, since the roadmap RM(W (ε) (p) y , A(ε)) satisfies RM 2 , RM(W (ε) (p)
y , A(ε)) has a non-empty intersection with every s-a connected component of (W (ε) (p) y ) c , and in particular with the one contained in C(ε). Taking the image under the map (π

[1,k] • lim ε ), we get that R = (π [1,k] • lim ε )(RM(W (ε) (p) y , A(ε))) has a non-empty intersection with (π [1,k] • lim ε )(C(ε)) = C. Since BGRM(V (y,z) , M z ∪ (M 0 ) z ) c contains R, this finishes the proof.

Complexity analysis. We first bound the number of arithmetic operations in

Step 1. Since we assume that the degrees of the polynomials in F, F are bounded by d O(k) , it follows from the complexity analysis of [2, Algorithm 15.3 (Bounded Algebraic Roadmap)], and [3, Algorithm 15.2 (Curve Segments)], that the number of arithmetic operations in this step is bounded by

d O(km) d O((k-mp) 2 ) = d O(km+p 2 ) since k -mp ≤ p.
The The total number of recursive calls at depth i is d O(ki) , and for each such call the number of arithmetic operations in D in Steps 1, 2, and 3 is bounded by d O((m+i+p)k+p 2 , where 0 ≤ i ≤ ⌊k/p⌋m. Since the depth of the recursion is at most ⌊k/p⌋m, we conclude that the total number of arithmetic operations in the domain D is bounded by

d O(k 2 /p) d O((k/p+p)k+p 2 ) = d O(k 2 /p+pk) .
We now describe Algorithm 7 (Baby-giant Roadmap for General Algebraic Sets) for computing a roadmap of a general (i.e. not necessarily bounded algebraic set). This algorithm is essentially the same algorithm as [2, Algorithm 15.5 (Algebraic Roadmap)], except that we call Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) after reducing to the bounded case instead of [2, Algorithm 15.3 (Bounded Algebraic Roadmap)]. We first need a notation. Let P ∈ R[X] be given by P = a p X p + • • • + a q X q , p > q, a q a p = 0. Notation 7.3. We write

c(P ) =   q≤i≤p a i a q   -1 . Algorithm 7. [Baby-giant Roadmap for General Algebraic Sets] Input. (1) a polynomial Q ∈ D[X 1 , . . . , X k ];
(2) a finite set of points

M 0 in Zer(Q, R k ), represented by real univariate representations U 0 . Output. a roadmap, BGRM(Zer(Q, R k ), M 0 ), for (Zer(Q, R k ), M 0 ). Complexity. d O(k 2 /p+pk) operations in D. Procedure.
Step 1. Introduce new variables X k+1 and ε and replace Q by the polynomial

Q(ε) = Q 2 + (ε 2 (X 2 1 + • • • + X 2 k+1 ) -1) 2 . Replace M 0 ⊂ R k by the set of real univariate representations representing the elements of Zer(ε 2 (X 2 1 + • • • + X 2 k+1 ) -1, R ε k+1 )
(Zer(Q a , R k+1 ), M 0 ). When projected to R k , this roadmap gives a roadmap BGRM(Zer(Q, R k ), M 0 ) ∩ B k (0, 1/a).
Step 4. In order to extend the roadmap outside the ball B(0, 1/a) collect all the points (y 1 , . . . , y k , y k+1 ) ∈ R ε k+1 in the roadmap

BGRM(Zer(Q(ε), R ε k+1 ), M 0 )
which satisfy ε(y 2 1 +. . .+y 2 k ) = 1. Each such point is described by a real univariate representation involving ε. Add to the roadmap the curve segment obtained by first forgetting the last coordinate and then treating ε as a parameter which varies over (0, a] to get a roadmap BGRM(Zer(Q, R k ), M 0 ).

Proof of correctness. The proof of correctness follows from the proof of correctness of Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets).

Complexity analysis. The complexity is dominated by the complexity of Step 2.

Proofs of Theorem 1.2 and Corollary 1.3. Follows directly from the correctness and complexity analysis of Algorithm 7 (Baby-giant Roadmap for General Algebraic Sets), after substituting m = 0 and p = √ k.

8. Appendix: computing the limit of bounded points and curve segments 8.1. Limit of a bounded point. Before computing the limit of a bounded point we need to explain how to perform some useful computations modulo a quasi-monic triangular Thom encoding F, σ representing a point t ∈ R m . We associate to t ∈ R m specified by a triangular Thom encoding F, σ,

F = (f [1] , . . . , f [m] ), f [i] ∈ D[T 1 , . . . , T i ],
the ordered domain D[t] contained in R and generated by t.

We now aim at describing the pseudo-inversion of a non-zero element in the domain D[t] specified by F, σ.

Definition 8.1. A pseudo-inverse of f ∈ D[t] is an element g ∈ D[t] such that f g ∈ D is strictly positive.
This notion is delicate as the computation of the pseudo-inverse sometimes requires us to update the quasi-monic triangular Thom encoding specifying t, in the spirit of dynamical methods in algebra (see for example [START_REF] Coste | Dynamical method in algebra: effective Nullstellensätze[END_REF]). We start with a motivating example.

Example 8.2. We consider t, specified as the root of

f (T ) = T 4 -T 2 -2
giving signs (+, +, +, +) to the set Der(f ) of derivatives of f . Consider T 2 + 1. It is easy to see, using for example [2, Algorithm 10.13 (Sign Determination Algorithm)] applied to f and the list Der(f ), T 2 + 1, that the sign of T 2 + 1 at t is positive. In order to compute its pseudo-inverse, we perform [2, Algorithm 8.22 (Extended Signed Subresultant)] of f and T 2 + 1. If f (T ) and T 2 + 1 were coprime, we would obtain the pseudo-inverse of T 2 + 1 modulo f (T ) since the last subresultant would be a non-zero constant in D. But f (T ) and T 2 + 1 are not coprime and their gcd is T 2 + 1. So we divide f (T ) by T 2 + 1, obtain a new polynomial g(T ) = T 2 -2 and check that the root t of f (T ) giving signs (+, +, +, +) to the set Der(f ) coincides with √ 2 which is the root of T 2 -2 making the derivative g ′ (T ) = 2T positive, using again -for example-[2, Algorithm 10.13 (Sign Determination Algorithm)]. It is now possible to compute a pseudo-reduction of T 2 + 1 modulo g(T ), which gives 3.

In other words, during the process of computing the pseudo-inverse of T 2 + 1 we discovered the factor g(T ) of f (T ) having t as a root and coprime with T 2 + 1. Using this new description of t we have been able to compute a pseudo-inverse of T 2 + 1.

We can now describe the computation of the pseudo-inverse in general. Description 8.3. Given t = (t 1 , . . . , t m ) ∈ R m specified by the quasi-monic triangular Thom encoding F = (f [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF] , . . . , f [m] ), σ = (σ 1 , . . . , σ m ), we describe how to compute a pseudo-inverse of a non-zero element of D [t].

We proceed by induction on the number m of variables of F.

If m = 0, there is nothing to do since D is an ordered domain.

If m = 0, let t ′ = (t 1 , . . . , t m-1 ) specified by

F ′ = (f [1] , . . . , f [m-1] ), σ = (σ 1 , . . . , σ m-1 ).
We consider f as a polynomial in T m whose coefficients, which are elements of

{h ∈ D[T 1 , . . . , T m-1 ] | deg Ti (h) < deg Ti (f [i] ), i = 1, . . . , m -1}, represent elements of D[t ′ ].
We first decide the sign of f at t, which is done by [2, Algorithm 12.19 (Triangular Sign Determination Algorithm)].

If f (t) = 0, we try to pseudo-invert f modulo F. We perform [2, Algorithm 8.22 (Extended Signed Subresultant)] for f and f [m] , with respect to the variable T m and compute a gcd(f, Proposition 8.4. Let D be an ordered domain contained in a real closed field R, and t = (t 1 , . . . , t m ) ∈ R m be specified by a quasi-monic triangular Thom encoding F, σ,

f [m] ) ∈ D[t ′ ] (the last non zero subresultant polynomial) as well as the cofactors u, v ∈ D[t ′ ] with uf + vf [m] = gcd(f, f [m] ). (1) If gcd(f, f [m] ) is of degree 0 in T m , u is a quasi-inverse of f . (2) If gcd(f, f [m] ) is of degree > 0 in T m ,
F = (f [1] , . . . , f [m] ), f [i] ∈ D[T 1 , . . . , T i ]. Let d be a bound of the degree of f [i] with respect to each T j , 1 ≤ j ≤ i, 1 ≤ i ≤ m. a) If g ∈ D[T 1 , . . . , T m
] is a polynomial of degree D, the complexity of computing a pseudo-reduction (c, ḡ) of g modulo F is (Dd) O(m) arithmetic operations in D.

b) The complexity of the computation of the pseudo-inverse of an element of

D[t] is d O(m) arithmetic operations in D. Proof. a) Suppose that C g ∈ D is such that C g T i1 1 • • • T im m g has a reduction in D modulo F for every (i 1 , . . . i m ) with i j < deg(f [j] , T j ), 1 ≤ j ≤ m.
We denote by Mat(C g g) the matrix of multiplication by C g g modulo (F) with respect to monomial bases. The entries of Mat(C g g) are in D. Its rows and columns are indexed by (i 1 , . . . , i m ), i j < deg(f [j] , T j ), 1 ≤ j ≤ m and the (j 1 , . . . , j m )-th entry of the column indexed by (i 1 , . . . , i m ) is the coefficient of

T j1 1 • • • T jm m in the reduction of C g T i1 1 • • • T im m g modulo F. Note that Mat(C g C h gh) = Mat(C g g)Mat(C h h).
Note also that the entries of the first column of Mat(C g g) (indexed by (0, . . . , 0)) are the coefficients of the reduction of C g g modulo F.

We first compute C Tj such that

C Tj T i1 1 • • • T im m T j has a reduction in D modulo F for every (i 1 , . . . i m ), i h < deg(f [h] , T h ), 1 ≤ h ≤ m.
The algorithm proceeds by induction on j.

For j = 1, let c 1 ∈ D be the leading coefficient of f

[1] ∈ D[T 1 ], d 1 = deg(f [1]
, T 1 ), and C T1 = c 1 . The matrix Mat(c 1 T 1 ) is simply obtained by replacing each occurence of c 1 T d1

1 by f [1] -c 1 T d1 1 in c 1 T d1-1 1 T i2 2 • • • T im m T 1 with i h < d h , 2 ≤ h ≤ m
and writing the result as a linear combination of the monomials

T j1 1 • • • T jm m , j i < d i , 1 ≤ i ≤ m. Compute Mat(C h T1 T h 1 ) = Mat(c 1 T 1 ) h , h < 2d,
C j f [j+1] -C Tj+1 T dj+1 j+1 in C Tj+1 T i1 1 • • • T ij j T dj+1-1 j+1 T ij+2 j+2 • • • T im m T j+1 , with i ℓ < d ℓ .
Notice that the polynomials obtained this way have degrees at most 2d in T 1 , . . . , T j , and degrees < d h in T h for h > j. Reduce all such monomials using the matrices of multiplication computed before. We can now give the description of Algorithm 3 (Limit of a Bounded Point).

Description of Algorithm 3 (Limit of a Bounded Point)

The precise input and output of this algorithm appear in Section 6.2.

Procedure Remove from g(ε)(T 1 , . . . , T m , U ) the coefficients vanishing at the point (t 1 , . . . , t m ), using [2, Algorithm 12.19 (Triangular Sign Determination)]. Supposing without loss of generality that not all the coefficients of g(ε)(t 1 , . . . , t m , U ) are multiples of ε, denote by g(T 1 , . . . , T m , U ) the polynomial obtained by substituting 0 for ε in g(ε)(T 1 , . . . , T m , U ).

Similarly denote by G(T 1 , . . . , T m , U ) the polynomials obtained by substituting 0 for ε in G(ε)(T 1 , . . . , T m , U ).

Compute the set Σ of Thom encodings of roots of g(t, U ) using [2, Algorithm 12.19 (Triangular Sign Determination)]. Denoting by µ σ the multiplicity of the root of g(t, U ) with Thom encoding σ, define G σ as the (µ σ -1)-th derivative of G with respect to U .

Identify the Thom encoding σ and G σ representing z using [2, Algorithm 12.19 (Triangular Sign Determination)], by checking whether a ball of infinitesimal radius δ (1 ≫ δ ≫ ε > 0) around the point x represented by the real univariate representation g, σ, G σ contains z(ε).

Pseudo-invert the leading coefficient of the univariate representation, denote by F ′ , σ ′ the new triangular Thom encoding describing t and compute a pseudo-reduction of the output modulo F ′ .

Complexity analysis: Follows from the complexity of [2, Algorithm 12.19 (Triangular Sign Determination)]. 8.2. Limit of a curve. Computing the limit of a curve is not immediate when some part of the curve has a vertical limit, as seen in the following example.

Example 8.5. Consider the s-a curve γ : [0, ε] → R ε 3 , parametrized by the X 1 coordinate defined by

γ(x 1 ) = (x 1 , γ 2 (x 1 ), γ 3 (x 1 )), x 1 ∈ [0, ε]
where (γ 2 (x 1 ), γ 3 (x 1 )) is the solution of the triangular system,

X 2 -x 1 /ε = 0, X 2
2 + X 2 3 -1 = 0, with Thom encoding (0, +), (0, +, +).

Notice that the image of γ is contained in the cylinder of unit radius with axis the X 1 -axis and is bounded over R. The image of γ under the lim ε map is contained in a circle in the plane X 1 = 0, and can no longer be described as a curve parametrized by the X 1 -coordinate.

However, it is possible to reparametrize γ by the X 2 -coordinate. By doing so we obtain another s-a curve ϕ : [0, 1] → R ε 3 (having the same image as γ) defined by ϕ(x 2 ) = (ϕ 1 (x 2 ), x 2 , ϕ 3 (x 2 )), x 2 ∈ [0, 1] where (ϕ 1 (x 2 ), ϕ 3 (x 2 )) is the real solution of the triangular system

X 1 -εx 2 = 0, X 2
3 + x 2 2 -1 = 0, with Thom encoding (0, -), (0, +, +). Notice that the image under lim ε of the curve which is the graph of ϕ can be easily described as the curve represented by the following triangular system parametrized by x 2 ∈ [0, 1] X 1 = 0, X 2 3 + x 2 2 -1 = 0, and Thom encoding (0, -1), (0, +, +). This is the reason why some kind of reparametrization is necessary before computing the limit. 8.2.1. Reparametrization of curve segments. We define the notion of well-parametrized curve, and prove that the limit of a well-parametrized curve is easy to describe. Definition 8.6. A differentiable s-a curve

γ = (γ 1 , . . . , γ k ) : (a, b) → R k parametrized by X 1 (i.e. γ 1 (x 1 ) = x 1 ) is well-parametrized if for every x 1 ∈ (a, b), k i=1 ∂γ i ∂X 1 2 ≤ k.
Let t ∈ R m be represented by a triangular Thom encoding F, σ, and

f 1 , σ 1 , f 2 , σ 2 , g, τ, G
be a curve segment with parameter X j over t on (α 1 , α 2 ) where α 1 and α 2 are the elements of R represented by the Thom encodings f 1 , σ 1 and f 2 , σ 2 .

The curve segment

f 1 , σ 1 , f 2 , σ 2 , g, τ, G is well-parametrized if the s-a curve γ : (α 1 , α 2 ) → R ε k defined by γ(x j ) = g 1 (t, x j , u(x j )) g 0 (t, x j , u(x j )) , . . . , g k (t, x j , u(x j )) g 0 (t, x j , u(x j ))
is well-parametrized, where u : (α 1 , α 2 ) → R maps each x j ∈ (α 1 , α 2 ) to the root of g(t, x j , U ) with Thom encoding τ . This means that k i=1 g i (t, x j , u(x j )) g 0 (t, x j , u(x j ))

′ 2 ≤ k,
where the derivative is taken with respect to x j .

Example 8.5 is not a well-parametrized curve segment. If a curve segment defined over R ε is well-parametrized, and represents a curve bounded over R, then the image of the curve under the lim ε map can be easily described. The following proposition explains why this is true.

Proposition 8.7. Let (a(ε), b(ε)) ⊂ R ε , a(ε), b(ε) bounded over R, r < j ≤ k, z(ε) ∈ R ε r , and γ(ε) =: (a(ε), b(ε)) → {z(ε)} × R ε k-r
a s-a differentiable curve parametrized by X j and bounded over R. If γ(ε) is wellparametrized, then:

(1) there exists a continuous extension of γ(ε) to a continuous, s-a curve,

γ(ε) =: [a(ε), b(ε)] → {z(ε)} × R ε k-r defined over the closed interval [a(ε), b(ε)]; (2) for each x ∈ [lim ε (a(ε)), lim ε (b(ε))] and any x(ε) ∈ [a(ε), b(ε)] with lim ε (x(ε)) = x, γ(x) := lim ε (γ(ε)(x)) = lim ε (γ(ε)(x(ε))); (3) lim ε (γ(ε)([a(ε), b(ε)])) = γ([lim ε (a(ε)), lim ε (b(ε)]),
In other words, the graph of the s-a function γ(-) := lim ε (γ(ε)(-)) is the image under lim ε of the graph of γ(ε).

Proof. Since γ(ε) is bounded it follows that there exists a continuous extension of γ(ε) to the end points of the interval (a(ε), b(ε)). It also follows from the definition of being well-parametrized that ||γ(ε) ′ (x)|| ≤ √ k for all x ∈ (a(ε), b(ε)). By the s-a mean value theorem [2, Exercice 3.4] we have that for each x ∈ (a(ε), b(ε)) ∩ R and any

x(ε) ∈ (a(ε), b(ε)) with lim ε (x(ε)) = x, ||γ(ε)(x) -γ(ε)(x(ε))|| = ||γ(ε) ′ (w(ε))|||x -x(ε)|,
for some w ∈ (x, x(ε)) (assuming without loss of generality that x < x(ε)). Taking the image under lim ε and noticing that ||γ(ε) ′ (w(ε))|| is bounded over R by the previous observation, we obtain that

lim ε (γ(ε)(x)) = lim ε (γ(ε)(x(ε))),
proving [START_REF] Basu | Computing roadmaps of semi-algebraic sets on a variety[END_REF]. This implies that the function γ : (lim ε (a(ε)), ε (b(ε))) → R k defined by γ(x) = lim ε (γ(ε)(x)) is a continuous, bounded (since γ(ε) is bounded over R) s-a function, and hence can be extended to a continuous, bounded s-a function on the closed interval

[lim ε (a(ε)), lim ε (b(ε))]. Moreover, it is clear that γ(lim ε (a(ε))) = lim ε (γ(ε)(a(ε))) and γ(lim ε (b(ε))) = lim ε (γ(ε)(b(ε))), since γ(lim ε (a(ε))), γ(lim ε (b(ε))) ∈ γ((lim ε (a(ε)), lim ε (b(ε)))) = lim ε (γ(ε)([a(ε), b(ε)])).
It is then clear that (2) follows.

A s-a curve is in general not well-parametrized. However, subdividing if necessary the curve into several pieces, it is possible to choose for each such piece a parametrizing coordinate which makes the piece well-parametrized. This is what we do in Algorithm 8 (Reparametrization of a Curve). (2) a bounded curve S represented by a curve segment,

f 1 , σ 1 , f 2 , σ 2 , g, τ, G
with parameter X 1 in R k over t on (a, b). All the polynomials in the input have coefficients in D. Output. (1) A finite set V = {v 1 , . . . , v N -1 }, of real univariate representations over (t, c i ) where each c i is represented by a Thom encoding over t fixing X m(i) . (2) A finite set W = {w 1 , . . . , w N }, of curve segments with w i parametrized by X ℓ(i) . Moreover, the union of the curves represented by W, and the points represented by V define a partition of S. Complexity If the polynomials occurring in the input have degrees bounded by D, then the complexity of the algorithm is bounded by k O(1) D O(m) .

Procedure.

Step 1. Let g 1 (X 1 , T ) = X 1 g 0 (X 1 , T ), and for each i, 1 ≤ i ≤ k, let

F i := ∂g ∂T ∂g i ∂X 1 g 0 -g i ∂g 0 ∂X 1 - ∂g i ∂T g 0 -g i ∂g 0 ∂T ∂g ∂X 1
(which is proportional to the projection on the i-th coordinate of the tangent vector to the input curve by the chain rule) and

G i := kF 2 i - k j=1 F 2 j .
Step ] and get a = c 1 < . . . < c L = b, where each c j is represented by a Thom encoding (C j , σ j ) over t ∈ R m , such that for each j, 1 ≤ j ≤ L, there exists an ℓ(j), 1 ≤ ℓ(j) ≤ k, such that for all x 1 ∈ (c j-1 , c j ), G ℓ(j) (t, x 1 , u(x 1 )) ≥ 0, denoting by u(x 1 ) the root of g(t, x 1 , U ) with Thom encoding τ . For each j fix an ℓ(j) satisfying this property.

Step 3. For each j, 1 ≤ j ≤ L, reparametrize the segment of the input curve over the interval (c j-1 , c j ) using the coordinate X ℓ(j) . Suppose without loss of generality from here on that ℓ(j) = 2. Step 3 a). Set

H := g 2 + (X 2 • g 0 (T, X 1 , U ) -g 2 (T, X 1 , U )) 2 ∈ D[T, X 1 , X 2 , U ].
Note that Zer(H(t, -), R 3 ) is a curve bounded over R (by assumption on the input). Call Algorithm 1 (Curve Segments) with input the polynomial H, and the triangular system F, σ, noticing that X 2 is now the parameter. Let D i (respectively, C i ) be the set of distinguished points (respectively, curves) output by Algorithm 1.

Step 3 b). For each element

(h(T, X 2 , V ), σ h , H(T, X 2 , V )) ∈ D i , where H(T, X 2 , V ) = (h 0 (T, X 2 , V ), h 1 (T, X 2 , V ), h 2 (T, X 2 , V )), use [2, Algorithm 12.19 (Triangular Sign Determination)] to check if the point (x 1 , x 2 , u) represented by (h, σ h , (h 0 , h 1 , X 2 h 0 , h 2 )) over t, coincides with (x 1 , g 2 (t, x 1 , u(x 1 )) g 0 (t, x 1 , u(x 1 )) , u(x 1 )).
Retain only the element

(h(T, X 2 , V ), σ h , H(T, X 2 , V )) ∈ D i
for which this is the case, and add to the set V the real univariate representation

u = (h, σ h , G H ) (see Notation 4.6) representing a point v h ∈ R k , with parameter X 2 over t. Step 3 c). For each element (f 1 (T, V ), σ 1 , f 2 (T, V ), σ 2 , h(T, X 2 , V ), σ h , H(T, X 2 , V )) ∈ C i , where H(T, X 2 , V ) = (h 0 (T, X 2 , V ), h 1 (T, X 2 , V ), h 2 (T, X 2 , V )), use [2, Algorithm 12.19 (Triangular Sign Determination)] to check if the point (x 1 , x 2 , u) represented by h(T, X 2 , V ), σ h , (h 0 , h 1 , X 2 h 0 , h 2 ) over t, coincides with (x 1 , g 2 (t, x 1 , u(x 1 )) g 0 (t, x 1 , u(x 1 )) , u(x 1 )) for x 2 = (v 1 + v 2 )/2
: (a, b) → R k . Let (c, d) be a sub-interval of (a, b) such that for every x 1 ∈ (a, b) G (t, x 1 , u(x 1 )) = kF 2 ℓ (t, x 1 , u(x 1 )) - k j=1 F 2 j (t, x 1 , u(x 1 )) ≥ 0. ( 8.1)
(using the notation of Step 1 and Step 2). This implies

∂γ ℓ ∂X 1 ≥ 1 √ k ,
and hence the mapping

γ ℓ from (c, d) to (c ′ , d ′ ) with c ′ = γ ℓ (c), d ′ = γ ℓ (d) is invertible. Defining γ(x ℓ ) = γ(γ -1 ℓ (x ℓ )), γ((c ′ , d ′ )) = γ((c, d)) is well-parametrized by X ℓ .
Moreover, at each point x 1 ∈ (a, b) such a choice of ℓ exists, since there must exist

an ℓ, 1 ≤ ℓ ≤ k such that ∂γ ℓ ∂X 1 2 is at least the average value 1 k k i=1 ∂γ i ∂X 1 2 .
Notice also that for such a choice of ℓ we have by the chain rule, In Steps 3-4 the Algorithm 1 (Curve Segments) and [2, Algorithm 12.19 (Triangular Sign Determination)] are both called with a constant number of variables in the input. Using the complexity analysis of these algorithms, the total complexity is bounded by k O(1) D O(m) . 8.2.2. Limit of a curve. We are now ready to describe Algorithm 4 (Limit of a Curve).

k i=1 ∂γ i ∂X ℓ 2 = k i=1 ∂γi ∂X1 2 ∂γ ℓ ∂X1 2 ≤ k. ( 8

Description of Algorithm 4 (Limit of a Curve)

The algorithm proceeds by reparametrizing the curve and computing the limit of the well-parametrized curve segments so obtained, as explained below. Its precise input and output appear in Section 6.2.

Procedure

Step 1. Let T = (T 1 , . . . , T m ), X ′ = (X 1 , . . . , X r ). Call a slight variant of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], computing pseudo-reductions of the intermediate computations modulo F (using Proposition 8.4), with input

A∈H(ε) A 2 ∈ D[ε, T, X ′ ]
and parameters ε, T , and output the set U ε of parametrized univariate representations with variable U . For every (h(ε), H(ε)) ∈ U(ε), use [2, Algorithm 12.20 (Triangular Thom Encoding)] with input the triangular system (F, h(ε)) to compute the Thom encodings of the real roots of h(ε)(y, U ). If

H(ε) = (h [1] , . . . , h [r] ) with h [i] ∈ D[T, X 1 , . . . , X i ] substitute the variables X ′ in 0,...,r Der Xi (h [i] )
using H(ε) by (Notation 4.5) and define a family A of polynomials in ε, T, U . Using [2, Algorithm 12. (Triangular Sign Determination)], compute the signs of the polynomials of A at the roots of h(ε)(y, U ). Comparing the Thom encodings, identify a specific (h(ε), τ (ε), H(ε)) representing z(ε) over t.

Then apply Algorithm 3 (Limit of a Bounded Point) with input (h(ε), τ (ε), H(ε))

representing z(ε) over t to obtain a real univariate representation p z , ρ z , P z representing z over t.

Step 2. Using Algorithm 8 (Reparametrization of a Curve) reparametrize the input curve segment.

Step 3. For every well-parametrized curve segment S(ε) computed in Step 2, and represented by

(f (ε) 1 , σ(ε) 1 , f (ε) 2 , σ(ε) 2 , g(ε), τ (ε), G(ε)),
do the following. First reorder the variables to ensure that the parameter of S(ε) is X r+1 . Then compute a description of lim ε (S(ε)). This process is going to generate a finite list of open intervals and points above which the representation of the restriction of the curve lim ε (S(ε)) by a curve segment is fixed. This is done as follows.

Step 3 a). Denote by α(ε) 1 the element of R ε represented by

f (ε) 1 (T, X ′ , X r+1 ), σ(ε) 1 over (t, z(ε)).
Call a slight variant of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], computing pseudo-reduction of the intermediate computations modulo F of the output modulo F (using Proposition 8.4), with input

A∈H(ε) A 2 + f (ε) 1 (T, X ′ , X r+1 ) 2 ∈ D[ε, T, X ′ , X r+1 ]
and parameters ε, T , and output a set U ′ ε of parametrized univariate representations with variable U .

For every (h(ε), H(ε)) ∈ U ′ ε , use [2, Algorithm 12.20 (Triangular Thom Encoding)] with input the triangular system (F, h(ε)) to compute the Thom encodings of the real roots of h(ε)(y, U ).

If representing (z(ε), α(ε) 1 ) over t to obtain a quasi-monic real univariate representation p z,α1 , ρ z,α1 , P z,α1 representing (z, α 1 ) over t with α 1 = lim ε (α(ε) 1 ). Obtain a Thom encoding over t, of α 1 using [2, Algorithm 15.1 (Projection)].

H(ε) = (h [1] , . . . , h [r] ) with h [i] ∈ D[T, X 1 , . . . , X i , ] substitute the variables X ′ , X r+1 in Der Xr+1 (f (ε) 1 (T, X ′ , X r+1 ), X r+1 ∪ 1
Similarly, for α(ε) 2 the element of R ε represented by f (ε) 2 (T, X ′ , X r+1 ), σ(ε) 2 over (t, z(ε)), compute a Thom encoding over t, of α 2 = lim ε (α(ε) 2 ).

Step 3 b). Perform a slight variant of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], computing pseudo-reductions of intermediate computations modulo F of the output modulo F (using Proposition 8.4), with input A∈H(ε)

A 2 + g(ε)(T, X ′ , X r+1 , V ) 2 ∈ D[ε, T, X ′ , X r+1 , U ] with parameters ε, T, X r+1 and output a set V(ε) of parametrized univariate representations with parameter ε, T, X r+1 and variable V . Denote by Θ(ε) the set of polynomials θ(ε) such that there exists Θ(ε) with (θ(ε), Θ(ε)) ∈ V(ε). Note that θ(ε) ∈ D[ε, T, X r+1 , V ]. Step 3 e). Compute using [2, Algorithm 12.19 (Triangular Sign Determination)] the Thom encodings of the real roots of the polynomials in E(t), and the ordered list c 1 < • • • < c h-1 of the roots of the polynomials in E(t) in the interval (c 0 , c h ), with c 0 = α 1 , c h = α 2 . Denote by C j , ρ j a polynomial in E(t) and a Thom encoding representing c j . Step 3 f). For every j from 1 to h -1, and for every θ ∈ Θ, determine using [2, Algorithm 12.19 (Triangular Sign Determination)], the Thom encoding θ(t, c j , V ), τ j of a root v j such that v j = lim ε (v(ε)), where v(ε) is the root of θ(ε)(t, c j , V ) with Thom encoding τ (ε). The multiplicity µ j of the root v j is determined by τ j . Step 3 g). For every j from 1 to h, define I = (c j-1 , c j ). For every θ ∈ Θ determine, using [2, Algorithm 12.19 (Triangular Sign Determination)] the Thom encoding θ I (t, x r+1 , V ), τ I of a root v I (x r+1 ), of multiplicity µ I such that for every x r+1 ∈ I, v I (x r+1 ) = lim ε (v(ε)) where v(ε) is the root of θ(ε)(t, x r+1 , V ) with Thom encoding τ (ε). The multiplicity µ I of the root v I (x r+1 ) is determined by τ I .

Step 3 h). Given (θ(ε), Θ(ε)) in U (ε) denote by (g Θ(ε) , G Θ(ε) ) the kr + 1-tuple of polynomials obtained by substituting in (g(ε), G(ε)) the variables X ′ , U by F (ε) (see Notation 4.5). Denote by V ′ (ε) ⊂ D[ε, T, X j , V ] the set of kr + 1-tuples of polynomials (g Θ(ε) , G Θ(ε) ). Step 3 i). For every j from 1 to h -1 and every (h(ε), H(ε)) ∈ V ′ (ε), with H(ε) = (h(ε) 0 , h(ε) r+2 , . . . , h(ε) k ) determine the order in ε of h ε (t, c j , v j ), h(ε) i (t, c j , v j ). This is done by determining the signs of the coefficient h ℓ , h i,ℓ of ε ℓ in h(t, c j , v j ), h i (t, c j , v j ) using [2, Algorithm (T, X r+1 , V ))

over t, u. The image under lim ε of the point of S(ε) with X r+1 -coordinate (c j ) is (z, c j , d j ). Step 3 j). For every j from 1 to h define I = (c j-1 , c j ). For every (h(ε), H(ε)) ∈ V ′ (ε), with H(ε) = (h(ε) 0 , h(ε) r+2 , . . . , h(ε) k ) subdivide I so that the order in ε of h(ε)(t, c j , v j ) and h i (ε)(t, x r+1 , v I (x r+1 )) is fixed. This is done by computing On each open interval J between two successive roots, the order in ε, denoted by o(h ε ), o(h(ε) i ) of the polynomials h(ε)(t, x r+1 , v J (x r+1 )), h i (ε)(t, x r+1 , v J (x r+1 )) remains fixed.

E I =
Retain those (h(ε), H(ε)) such that o(h(ε) 0 ) ≤ o(h(ε) i ) for all i from r + 2 to k and replace ε by 0 in ε -o(h(ε)0) (h, H(ε)), which defines a set H J . Inspecting every (h, H) ∈ H J , determine, using [2, Algorithm 12.19 (Triangular Sign Determination)], a kr + 1-tuple (h J , H J ) such that the point represented by (h J (t, x r+1 , v I ), H (µ J -1) J (t, x r+1 , v I ))

is the image under lim ε of the point of S(ε) with X r+1 -coordinate x r+1 , where µ J is the multiplicity of u J (x r+1 ) as a root of h J (x r+1 , V ).

Let w J be the curve represented by the curve segment representation h I (T, X r+1 , U ), τ j , H (µ J -1) J

(T, X r+1 , U ) with parameter X r+1 over t, u.

Step 3 k). Let c 1 < • • • < c N -1 denote the set of all the elements of R computed in

Steps 2 d), and 2 i) above, and c N = c. Re-index each v j computed in Step 3 h), such that d j lies above c j . Similarly, re-index each w I computed in

Step 3 i) by some j, 1 ≤ j ≤ N , so that w j lies above the interval (c j-1 , c j ).

Output the lists consisting of d 1 , . . . , d N -1 , and w 1 , . . . , w N .

Proof of correctness. Let γ(ε) : (α(ε) 1 , α(ε) 2 ) → R ε k be the curve represented by a well-parametrized curve segment

f (ε) 1 , σ(ε) 1 , f (ε) 2 , σ(ε) 2 , g(ε), τ (ε), G(ε) computed in Step 2.
Let G : (α 1 , α 2 ) → R k be the curve whose image equals the image of γ(ε) under lim ε . Since the input curve segment is well-parametrized it follows from Proposition 8.7 that in order to compute for any x 1 ∈ (c 0 , c N ), G(x 1 ) it suffices to compute lim ε γ(ε)(x 1 ). The proof of correctness of the algorithm is then similar to the proof of correctness of Algorithm 3 (Limit of a Bounded Point).

Complexity analysis. Let D be a bound on the degrees of all polynomials appearing in the input. We first bound the degrees in the various variables, ε, T, X ′ , X r+1 , U, V of the polynomials computed in various steps of the algorithm. In Step 1, the degrees of the polynomials in U (ε) are bounded as follows. The degrees in ε, U are bounded by D O(r) by the complexity analysis of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] and the degrees in the T i are bounded by D, because of the pseudo-reduction. Moreover, the complexity of this step is bounded by D O(m+r) from the complexity of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] and the complexity of pseudo-reduction (see Defi-

3 Figure 1 .

 31 Figure 1. Torus in R 3

3 Figure 2 . 3 b)

 323 Figure 2. A roadmap of the torus in R 3

Remark 4 . 3 .

 43 If g ∈ D[T 1 , . . . , T m ] is a polynomial of degree D, and d is a bound on the degree of the f i with respect to the T i , the complexity of computing a pseudo-reduction (c, ḡ) of g ∈ D[T 1 , . . . , T m ] modulo F is (Dd) O(m) (see Section 8 Proposition 8.4 a)). Definition 4.4. A real block representation F, σ, L, F representing y ∈ R ℓ consists of (1) a triangular Thom encoding F = (f [1] , . . . , f [m] ), σ representing a root t = (t 1 , . . . , t m ) of F in R m ; (2) a list of natural numbers L = (ℓ 1 , . . . , ℓ m ) such that

  z) has a finite number of points and, since V is bounded, intersects every s-a connected component of V (y,z) by [3, Proposition 7.4]. Proposition 5.3. Suppose that V is bounded and Q satisfies Property 5.1. Let (1) M = W (0) y ⊂ V y ; Output. a roadmap RM(W (p-r) (y,z) , M 0 ) for (W (p-r) (y,z) , M 0 ) represented as a union of curve segment representations and real univariate representations over points defined by triangular Thom encodings. The adjacencies between the images of the associated curves and points are also part of the output. Complexity. D O(m+p) d O((m+p)k) where d = deg(Q) ≥ 2, and D is a bound on the degree of H, F, F and the number and degrees of the elements in U 0 . Procedure.

  z,z ′ ) is finite by Property 5.1.

  Proof. a) follows from [2, Proposition 12.44] and b) from [2, Lemma 15.6].

Algorithm 3 .O(m) 1 DO( 1 ) 2 . 3 .

 31123 [Limit of a Bounded Point] Input. (1) a quasi-monic triangular Thom encoding F, σ, with coefficients in D, representing a point t ∈ R m ; (2) a real univariate representation g(ε), τ (ε), G(ε) over t with coefficients in D[ε], representing a point z(ε) ∈ R ε p bounded over R. Output. (1) a quasi-monic triangular Thom encoding F ′ , σ ′ , representing the point t ∈ R m ; (2) a quasi-monic real univariate representation (h, τ, H) representing z = lim ε z(ε) ∈ R p . Complexity. If D 1 (resp. D 2 ) is a bound on the degrees of the polynomials in F, g(ε) and G(ε) with respect to T 1 , . . . , T m (resp. ε, U ), then D 1 (resp. D 2 ) is a bound on the degrees of the polynomials appearing in the output, and the number of arithmetic operations in D is bounded by D Remark 6.3. Note that there is a possibly new representation of the point t ∈ R m specified in the input, in the output of Algorithm 3 (Limit of a Bounded Point). The reason for this peculiarity is explained in Section 8 (cf. Proposition 8.4 b)). Algorithm 4. [Limit of a Curve] Input. (1) a quasi-monic triangular Thom encoding F, σ with coefficients in D representing t ∈ R m ; (2) a triangular Thom encoding H(ε), ρ(ε) over t with coefficients in D[ε] representing z(ε) ∈ R ε r over t; (3) a curve segment with parameter X r+1 and coefficients in D[ε] over (t, z(ε)), representing a curve S(ε) in R ε k bounded over R. Output. (1) a real univariate representation p z , ρ z , P z of z = lim ε (z(ε)), with u the root of p z with Thom encoding ρ z ;(2) a finite set D = {d 1 , . . . , d N -1 } where each d i is a real univariate representation over (t, u, c i ), and c i is given by a Thom encoding over t fixing X m(i) ;(3) a finite set W = {w 1 , . . . , w N } of curve segments over (t, u) with w i parametrized by X ℓ(i) . Moreover, the union of the curves represented by W, together with the points represented by D define a partition of S = lim ε (S(ε)). All the coefficients of the polynomials in the output belong to D. Complexity If the polynomials occurring in the input have degrees bounded by D, then the complexity of the algorithm is bounded by k O(1) D O(m+r) .6.Low dimensional roadmap algorithm. We are going to describe an algorithm computing the limit of a roadmap of the critical locus of dimension p, W

  Algorithm 5. [Limit of Roadmaps of Special Low Dimensional Varieties] Input. (1) natural numbers p ≤ k;

  ) y ∈ R mp represented by the real block representation F, σ, [p m ], F, (see (4.1)) with coefficients in D, such that t ∈ R m is represented by a quasi-monic triangular Thom encoding F, σ; (4) a finite set of points N (ε) ∈ {y} × R ε p represented by quasi-monic real univariate representations V(ε), over t. Output. Real univariate representations and curve segments representing the set of points

  Step 1 is bounded by D O(m+p) d O((m+p)k) arithmetic operations in D[ε] according to the complexity analysis of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] and [2, Algorithm 12.20 (Triangular Thom Encoding)]. Since the degree in ε in the output of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)] is d O(k) and does not change during the pseudo-reduction, the number of arithmetic operations in D in Step 1 and hence the complexity is bounded by D O(m+p) d O((m+p)k) . The number of arithmetic operations performed in D[ε] in Step 2 is bounded by D O(m+p) d O((m+p)k) according to the complexity analysis of Algorithm 2 (Roadmap for Lower Dimensional Special Algebraic Sets). Moreover the degree in ε is bounded by O(d) k . To see this one has to observe that the arithmetic operations in D[ε] in the call to Algorithm 1 (Curve Segments) coincide with those performed by [2, Algorithm 15.10 (Parametrized Curve Segments)] with ε treated as a parameter. It follows from the complexity analysis of [2, Algorithm 15.10 (Parametrized Curve Segments)] that the degree in ε is bounded by O(d) k . So the number of arithmetic operations in D in Step 2 and hence the complexity is bounded by D O(m+p) d O((m+p)k) . The complexity of Step 3 is also bounded by D O(m+p) d O((m+p)k according to the complexity analysis of Algorithm 4 (Limit of Curve).

  number of arithmetic operations in D[ε] in Step 2 is bounded by d O(mk) and the degree and number of univariate representations produced is bounded by O(d) k-mp . Moreover the degree in ε is bounded by O(d) k . To see this one has to observe that the arithmetic operations in D[ε] in the call to Algorithm 1 (Curve Segments) coincide with those performed in [2, Algorithm 15.10 (Parametrized Curve Segments)] with ε treated as a parameter. It follows from the complexity analysis of [2, Algorithm 15.10 (Parametrized Curve Segments)] that the degree in ε is bounded by O(d) k . So the number of arithmetic operations in D in Step 2 is bounded by d O(mk) . The complexity of computing R y in Step 3 is bounded by d O((m+p)k) given that the number of arithmetic operations of Algorithm 5 (Limit of Roadmaps of Special Low Dimensional Varieties) is d O((m+p)k) .

  above the points M 0 using [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)]. Step 2. Call Algorithm 6 (Baby-giant Roadmap for Bounded Algebraic Sets) with input Q(ε), M 0 , m = 0, performing arithmetic operations in the domain D[ε]. The algorithm outputs a roadmap BGRM(Zer(Q(ε), R ε k+1 ), M 0 ) composed of points and curves whose description involves ε. Step 3. Denote by L the set of polynomials in D[ε] whose signs have been determined in the preceding computation and take a = min P ∈L c(P ) (Notation 7.3). Replace ε by a in the polynomial Q(ε) to get a polynomial Q a . Replace ε by a in the output roadmap to obtain a roadmap BGRM

  we have discovered a factor of f [m] . We define h as the quasi-monic polynomial proportional to f [m] / gcd(f, f [m] ) obtained by [2, Algorithm 8.22 (Extended Signed Subresultant)] (see [2, Algorithm 10.1 (Gcd and Gcd-free part)]). We perform [2, Algorithm 12.19 (Triangular Sign Determination)] applied to f [m] and Der(f [m] ), Der(h) to identify the Thom encoding τ of t [m] as a root of h. We replace f [m] by h and σ [m] by τ in F. Now f and the new f [m] , considered as polynomials in T [m] are coprime, and we can invert f modulo f [m] .

1 .

 1 and define C 1 = c 2d-1 Suppose by induction that for every monomial M in T 1 , . . . , T j of degree < 2d,C M T i1 1 • • • T im m M has a reduction in D modulo F for every (i 1 , . . . , i m ), i j < deg(f [j] , T j ), 1 ≤ j ≤ m.Also, suppose that Mat(C M M ) has been computed. Denote by C j ∈ D the product of C M for all the monomials M of degree < 2d in the j variables T 1 , . . . , T j . Let c j+1 ∈ D be the leading coefficient of f [j+1] ∈ D[T 1 , . . . , T j+1 ] with respect to T j+1 and d j+1 = deg(f [j+1] , T j+1 ), and take C Tj+1 = c j+1 C j . The matrix Mat(C Tj+1 T j+1 ) is obtained by replacing each occurence of C Tj+1 T dj+1 j+1 by

  Finally compute for every monomial M of degree ≤ D in T 1 , . . . , T m , C M and Mat(C M M ) by taking products of the C Ti and the matrices Mat(C Ti T i ) (respectively), and let C g be the product of the C M for all monomials M of degree ≤ D. Now determine Mat(C g g) by taking an appropriate linear combination of Mat(C M M ) and thus obtain the reduction of C g g modulo F.Notice that the complexity of computing the C Tj+1 , and Mat(C Tj+1 T j+1 ) is bounded by d O(m) . In the last step, there are O(D) m monomials of degree at most D, and hence at most O(D) m matrix multiplications to perform, and the sizes of the matrices isd 1 • • • d m ≤ d m . So the complexity is (Dd) O(m) .b) The proof proceeds by induction on the number of variables m of F. If m = 1, the computation of a gcd takes (d+1) c operations in the domain D, for some universal constant c > 0, using the complexity analysis of [2, Algorithm 8.22 (Extended Signed Subresultant)] and [2, Algorithm 10.13 (Sign Determination)].If m > 1, let t = (t ′ , u), and we suppose by induction hypothesis that the complexity of arithmetic operations including pseudo-inversion in D[t ′ ] is (d + 1) c(m-1) arithmetic operations in the ordered domain D. The claim is clear since the arithmetic operations in the domain D[t] are using (d+1) c operations in the domain D[t ′ ] using the complexity analysis of [2, Algorithm 8.22 (Extended Signed Subresultant)] and [2, Algorithm 10.13 (Sign Determination)].

Algorithm 8 .

 8 [Reparametrization of a Curve] Input. (1) t ∈ R m represented by a triangular Thom encoding F, σ,

. 2 )

 2 In Step 2 of the algorithm we obtain a partition of the interval (a, b) into points and open intervals, such that over each sub-interval (c j-1 , c j ) of the partition, there exists an index ℓ = ℓ(j) such that (8.1) is satisfied at each point v ∈ (c j-1 , c j ), and the curve segment over this interval is well-parametrized by X ℓ by (8.2).Each curve segment corresponding to elements of V output by the algorithm is thus well-parametrized. The remaining property of the output is a consequence of the correctness of Algorithm 1 (Curve Segments), and [2,Algorithm 12.19 (Triangular Sign Determination)]. Complexity analysis. Let D be a bound on the degrees of the polynomials in the input. The complexity of Steps 1 and 2 is bounded by k O(1) D O(m) from the complexity of [2, Algorithm 11.19 (Restricted Elimination)], and [2, Algorithm 12.23 (Triangular Sample Points)], noting that the number of polynomials in L is bounded by k O(1) D O(m) .

  ,...,r Der Xi (h [i] ) using Notation 4.5 and define a family B of polynomials in ε, T, U . Using [2, Algorithm 12. (Triangular Sign Determination)], compute the signs of the polynomials of B at the roots of h(ε)(y, U ). Comparing the Thom encodings, identify a specific (h(ε), τ (ε), H(ε)) representing (z(ε), α(ε) 1 ) over t.Then apply Algorithm 3 (Limit of a Bounded Point) with input (h(ε), τ (ε), H(ε))

  Step 3 c). Compute the family of coefficients C ⊂ D[T, X r+1 ] of the polynomials θ(ε) ∈ Θ(ε) considered as elements of D[T, X r+1 ][ε, V ] and the list L ⊂ {= 0, = 0} C of non-empty conditions = 0, = 0 satisfied by C in R using [2, Algorithm 12.23 (Triangular Sample Points)]. Note that for every x r+1 in the realization of τ ∈ L, the orders in ε of the coefficients of the polynomials in Θ(ε)(t, x r+1 ) ⊂ D[ε, V ] are fixed. For every θ(ε) ∈ Θ(ε) we denote by o(θ(ε), τ ) the minimal order in ε of the coefficients of θ(ε)(t, x r+1 ) on the realization of τ and by Θ τ ⊂ D[T, X r+1 , V ] the set of polynomials obtained by substituting 0 for ε in ε -o(θ(ε),τ ) θ(ε).Step 3 d). DefineΘ = τ ∈L Θ τ ⊂ D[T, X r+1 , V ]. Compute E = C ∪ θ∈Θ RElim V (θ, Der(θ)) ⊂ D[T, X r+1 ]using [2, Algorithm 11.19 (Restricted Elimination)], so that the Thom encodings of the real roots of θ(t, x r+1 , V ) are fixed when x r+1 varies in an open interval defined by the roots of the polynomials E(t).

  θ∈Θ,(h,H(ε))∈V ′ (ε),0≤ℓ≤deg ε hiRElim V (θ, h ℓ ) ⊂ D[T, X r+1 ],andE I,i = θ∈Θ,(h,H(ε))∈V ′ (ε),0≤ℓ≤deg ε hi RElim V (θ, h i,ℓ ) ⊂ D[T, X r+1 ], using [2, Algorithm 11.19 (Restricted Elimination)].DefiningE ′ I = E I ∪ i∈0,r+2,...,k E I,i ,compute the Thom encodings of the roots of the polynomials in E ′ I (t), using [2, Algorithm 12.19 (Triangular Sign Determination)].

  nition 4.2). The degrees in ε, T i , X ′ , U in the output of Step 2 are all bounded by D O(1) and the complexity of Step 2 is bounded by(kr) O(1) D O(m+r) = k O(1) D O(m+r)using the complexity analysis of Algorithm 8 (Reparametrization of a Curve).The degrees of the polynomials in Step 3 a are bounded as follows. In the output of the call to [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], the degrees in ε, U are bounded by D O(r) , and the degrees in the T i are bounded by D. Now, from the complexity analysis of Algorithm 3 (Limit of a Bounded Point) it follows that the degrees in the T i of the polynomials output are bounded by D and those in ε, U are bounded by D O(r) . Moreover, the complexity of Step 3 a is bounded by D O(m+r) from the complexity of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], the complexity of Algorithm 3 (Limit of a Bounded Point) and the complexity of pseudo-reduction (see Proposition 8.4). The degrees of the polynomials in Step 3 b are bounded as follows. In the output of the call to [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], the degrees in ε, X r+1 , V are bounded by D O(r) , and the degrees in the T i are bounded by D. The complexity of Step 3 b is bounded by D O(m+r) from the complexity of [2, Algorithm 12.18 (Parametrized Bounded Algebraic Sampling)], and the complexity of pseudo-reduction (see Definition 4.2). The complexity of Step 3 c is bounded by D O(m+r) using the degree bounds from the complexity analysis of the previous steps and the complexity of [2, Algorithm 12.23 (Triangular Sample Points)]. It now follows from the complexity analysis of [2, Algorithm 12.19 (Triangular Sign Determination)], [2, Algorithm 11.19 (Restricted Elimination)], and the degree estimates proved above that the complexity of the remaining steps are all bounded by k O(1) D O(m+r) . Thus, the complexity of the algorithm is bounded by k O(1) D O(m+r) .

  e. independent of the formula Φ describing S [2, Proposition 2.87]. Many properties of S can be transferred to Ext(S, R ′ ): for example S is non-empty if and only if Ext(S, R ′ ) is non-empty; also S is s-a connected if and only if Ext(S, R ′ ) is s-a connected [2, Proposition 5.24].

  Algorithm 1. [Curve Segments] Input. (1) a point t ∈ R m represented by a triangular Thom encoding F, σ;(2) a polynomial P ∈ D[T 1 . . . , T m , X 1 , . . . , X k ] for which Zer(P (t, -), R k ) is bounded; (3) a finite set of points contained in Zer(P (t, -), R k ) represented by real univariate representations U over t. Moreover, all the polynomials describing the input are with coefficients in D.Output. (1) An ordered list of pointsc 1 < • • • < c N of R with each c i i = 1, . . . ,N represented by a Thom encoding g i , τ i over t. The c i 's are called distinguished values. 3) For every i = 1, . . . , N -1 a finite set of curve segments C i defined on (c i , c i+1 ) with parameter X 1 , over t. The represented curves are called distinguished curves. (4) For every i = 1, . . . , N -1 a list of pairs of elements of C i and D i (resp. D i+1 ) describing the adjacency relations between distinguished curves and distinguished points. The distinguished curves and points are contained in Zer(P (t, -), R k ). The sets of distinguished values, distinguished curves, and distinguished points satisfy the following properties. CS 1 . If c ∈ R is a distinguished value, the set of distinguished points in the output intersect every s-a connected component of Zer(P (t, c, -), R k-1 ).

	3, Algorithm 15.2 (Curve
	segments)].

(2) For every i = 1, . . . , N , a finite set of real univariate representations D i over t representing a finite number of points in R k , called distinguished points. (If c ∈ R is not distinguished, the distinguished curves in the output intersect every s-a connected component of Zer(P (t, c, -), R k-1 ). CS 2 . For each distinguished curve in the output over an interval with endpoint a given distinguished value, there exists a distinguished point over this distinguished value which belongs to the closure of the curve. Complexity. If d = deg X (P ) ≥ 2, deg T (P ) = D, and the degree of the polynomials in F and the number of elements of U are bounded by D, the number of arithmetic operations in D is bounded by D O(m) d O

  2. Computing RElim T (G i , g), 1 ≤ i ≤ k, using [2, Algorithm 11.19 (Restricted Elimination)], obtain a family L of polynomials in the ring D[T 1 , . . . , T m , X 1 ]. Subdivide (a, b) in a finite union of points and intervals over which the signs of the polynomials in L are fixed using [2, Algorithm 12.23 (Triangular Sampling Points)

  where v 1 , v 2 are represented by (f 1 , σ 1 ) and (f 2 , σ 2 ) respectively. Retain only the element of C i for which this is the case, and add to the set W the curve segment(f 1 , σ 1 , f 2 , σ 2 , h, σ h , G H )with parameter X 2 over t (see Notation 4.6).

	Proof of correctness. Let

(f 1 , σ 1 , f 2 , σ 2 , g, τ, G)

be a curve segment parametrized by X 1 over t representing the curve γ

  12.19 (Triangular Sign Determination)]. Retain those (h(ε), H(ε)) such that o(h(ε) 0 ) ≤ o(h(ε) i ) for all i from r + 2 to k and replace ε by 0 in (ε -o(hε) h(ε), ε -o(h(ε)0) H(ε)),which defines a set H j . Inspecting every (h, H) ∈ H j , determine, using [2, Algorithm 12.19 (Triangular Sign Determination)], a k-r+1-tuple (h j , H j ) with the following property. Let d j be the point represented by the real univariate representation (h j (T, X r+1 , V ), τ j , H

(µj -1) j

Acknowledgement

We are very grateful to the ananymous referees of the paper for their numerous suggestions. We are particularly grateful to one of them for pointing out an error in a preliminary version.

Communicated by Teresa Krick. The first author was supported in part by NSF grants CCF-0915954, CCF-1319080 and DMS-1161629. The first and the second authors did part of the work during a research stay in Oberwolfach as part of the Research in Pairs Programme. The third author is member of Institut Universitaire de France and supported by the French National Research Agency EXACTA grant (ANR-09-BLAN-0371-01) and GeoLMI grant (ANR-2011-BS03-011-06). The fourth author was supported by an NSERC Discovery Grant and by the Canada Research Chairs program.

(2) D (p) ⊂ R the set of pseudo-critical values (see [2, Definition 12.41]) of π ℓ+1 on W (p) y , and M (p) a set of points such that for every c ∈ D (p) , M (p) intersects every s-a connected component D of (W

(y,z) is a finite set of points having non-empty intersection with every s-a connected component of V (y,z) by Remark 5.2. Moreover, Zer(Q(y, -), R k-ℓ ) is clearly bounded (since Zer(Q, R k ) is bounded), and the finite set M = W (0) y is the union of the Q(y, -)-singular points of Zer(Q(y, -), R k-ℓ ) and the Q(y, -)-critical points of the map π ℓ+1 on V y = Zer(Q(y, -), R k-ℓ ). Thus, M satisfies Property 3.2 1).

Note also that M (p) satisfies Property 3.2 3). Indeed, the intersection of M (p) with every s-a connected component of (W represented by real univariate representations U 0 , over (t, z) (using the notation of Property 5.1).