#  Efficient computation of a semi-algebraic basis of the first homology group
of a semi-algebraic set

Saugata Basu  Department of Mathematics, Purdue University, West Lafayette, IN
47907, U.S.A<EMAIL_ADDRESS>and  Sarah Percival  Department of
Mathematics, Purdue University, West Lafayette, IN 47907, U.S.A.
<EMAIL_ADDRESS>
###### Abstract.

Let $\mathrm{R}$ be a real closed field and $\mathrm{C}$ the algebraic closure
of $\mathrm{R}$. We give an algorithm for computing a semi-algebraic basis for
the first homology group, $\mbox{\rm H}_{1}(S,\mathbb{F})$, with coefficients
in a field $\mathbb{F}$, of any given semi-algebraic set
$S\subset\mathrm{R}^{k}$ defined by a closed formula. The complexity of the
algorithm is bounded singly exponentially. More precisely, if the given
quantifier-free formula involves $s$ polynomials whose degrees are bounded by
$d$, the complexity of the algorithm is bounded by $(sd)^{k^{O(1)}}$. This
algorithm generalizes well known algorithms having singly exponential
complexity for computing a semi-algebraic basis of the zero-th homology group
of semi-algebraic sets, which is equivalent to the problem of computing a set
of points meeting every semi-algebraically connected component of the given
semi-algebraic set at a unique point. It is not known how to compute such a
basis for the higher homology groups with singly exponential complexity.

As an intermediate step in our algorithm we construct a semi-algebraic subset
$\Gamma$ of the given semi-algebraic set $S$, such that $\mbox{\rm
H}_{q}(S,\Gamma)=0$ for $q=0,1$. We relate this construction to a basic
theorem in complex algebraic geometry stating that for any affine variety $X$
of dimension $n$, there exists Zariski closed subsets

$Z^{(n-1)}\supset\cdots\supset Z^{(1)}\supset Z^{(0)}$

with $\dim_{\mathrm{C}}Z^{(i)}\leq i$, and $\mbox{\rm H}_{q}(X,Z^{(i)})=0$ for
$0\leq q\leq i$. We conjecture a quantitative version of this result in the
semi-algebraic category, with $X$ and $Z^{(i)}$ replaced by closed semi-
algebraic sets. We make initial progress on this conjecture by proving the
existence of $Z^{(0)}$ and $Z^{(1)}$ with complexity bounded singly
exponentially (previously, such an algorithm was known only for constructing
$Z_{0}$).

###### Key words and phrases:

semi-algebraic sets, singly exponential, homology groups, basis

###### 1991 Mathematics Subject Classification:

Primary 14F25; Secondary 68W30

Basu was partially supported by NSF grants CCF-1618918, DMS-1620271 and
CCF-1910441.

###### Contents

  1. 1 Introduction
    1. 1.1 Background and history
      1. 1.1.1 Exact vs numeric
    2. 1.2 Model of computation and definition of complexity
      1. 1.2.1 Definition of complexity
      2. 1.2.2 $\mathcal{P}$-formulas, $\mathcal{P}$-semi-algebraic sets, realizations
    3. 1.3 Singly vs doubly exponential
    4. 1.4 Computing a basis for $\mbox{\rm H}_{0}(S)$
      1. 1.4.1 Interpretation in terms of a homology basis
  2. 2 New Results
    1. 2.1 Generalization to the first homology group
    2. 2.2 Connections with the “basic lemma” in complex algebraic geometry
    3. 2.3 Comparison with roadmaps
  3. 3 Preliminaries
    1. 3.1 Some notation
    2. 3.2 Representations of points and curves
  4. 4 Proofs of Theorems 2 and 3
    1. 4.1 Outline of the proofs of Theorems 2 and 3
    2. 4.2 Implementing Step 1: computing surjection
      1. 4.2.1 Morse-type partition
      2. 4.2.2 Constructing curve segments
    3. 4.3 Implementing Step 2: proofs of Theorems 2 and 3
      1. 4.3.1 Outline of Algorithm 7
      2. 4.3.2 Conversion of curve segment representations to closed formulas
      3. 4.3.3 Efficient algorithm for computing a simplicial replacement
      4. 4.3.4 Algorithm for computing basis of $\mbox{\rm H}_{1}(S)$
  5. 5 Conclusion and open problems

##  1\. Introduction

We fix a real closed field $\mathrm{R}$, and denote by $\mbox{\rm
D}\subset\mathrm{R}$ a fixed ordered domain. We will denote by
$\mathrm{C}=\mathrm{R}[i]$ the algebraic closure of $\mathrm{R}$. For example,
one can take $\mathrm{R}=\mathbb{R}$, and $\mbox{\rm D}=\mathbb{Z}$.

Semi-algebraic sets are subsets of $\mathrm{R}^{k},k\geq 0$, which are defined
by quantifier-free first-order formulas with atoms of the form
$P=0,P>0,P\in\mathrm{R}[X_{1},\ldots,X_{k}]$. Algorithmic semi-algebraic
geometry deals with computing geometric and topological invariants of semi-
algebraic subsets of $\mathrm{R}^{k}$, and is a very well-developed topic.
Examples of algorithmic problems in semi-algebraic geometry that have been
investigated include effective quantifier-elimination, the decision problem of
the first order theory of the reals, computing topological invariants, such as
the dimension, number of semi-algebraically connected components, the Euler-
Poincaré characteristic (appropriately defined), and more generally the Betti
numbers of a given semi-algebraic set.

###  1.1. Background and history

The problem of computing the Betti numbers (i.e. the ranks of homology groups)
of semi-algebraic sets has a long history and is an active area of current
research. Since doubly exponential complexity algorithms for computing the
Betti numbers follow from effective triangulation algorithms for semi-
algebraic sets, the emphasis has been on obtaining algorithms with singly
exponential complexity (see Section 1.3 below). Singly exponential algorithms
for computing the zero-th Betti number (i.e. the number of connected
components) of semi-algebraic sets via construction of roadmaps was obtained
by several authors and the complexity of the algorithms successively improved
over the years [17, 20, 21, 23, 4].

An algorithm with singly exponential complexity is known for computing the
first Betti number of semi-algebraic sets and is given in [10], and then
extended to the first $\ell$ (for any fixed $\ell$) Betti numbers in [2]. The
Euler-Poincaré characteristic, which is the alternating sum of the Betti
numbers, is easier to compute, and a singly exponential algorithm for
computing it is known [1, 5]. While many advances have been made in recent
years [2, 10], the best algorithm for computing _all_ the Betti numbers of any
given semi-algebraic set $S\subset\mathrm{R}^{k}$ still has doubly exponential
(in $k$) complexity, even in the case where the degrees of the defining
polynomials are assumed to be bounded by a constant ($\geq 2$) [28] (here we
are talking about exact algorithms, see Section 1.1.1 below for a different
model). The existence of algorithms with _singly exponential complexity_ for
computing all the Betti numbers of a given semi-algebraic set is considered to
be a major open question in algorithmic semi-algebraic geometry (see the
survey [8]).

Unlike the singly exponential complexity algorithms for computing the zero-th
Betti numbers, the algorithms for computing the higher Betti numbers do not
produce a semi-algebraic basis. Obtaining such a basis efficiently and of
small complexity is of interest in geometric applications. In classical
algebraic geometry over algebraically closed fields, representing homology
classes by _algebraic_ cycles is a well studied problem with deep connections
to Hodge theory. The existence of a _semi-algebraic_ basis with singly
exponential complexity for the higher homology groups of a given semi-
algebraic set is not known (other than in the zero-th homology case discussed
above). In this paper we remedy this deficiency by proving the existence of
such a basis in the case of the first homology group (cf. Theorem 2).

We note here that in the category of finite simplicial complexes, obtaining
optimal representatives (as cycles) of homology classes is a well-studied
problem. Early work on efficient algorithms for obtaining a shortest set of
loops generating the first homology group of a two dimensional oriented
manifold (given as a simplicial complex) appears in [19] (see for example,
[18, 26] for recent work on this topic). However, these algorithms are
primarily combinatorial in nature and the main difficulty in the semi-
algebraic version of the problem is precisely that a triangulation of the
given semi-algebraic set is not available (at least not known to be computable
within the complexity we are aiming for).

####  1.1.1. Exact vs numeric

We remark here that by the word “algorithm” in the previous paragraphs we are
referring only to algorithms that work correctly for all inputs and whose
complexity is uniformly bounded, i.e. bounded in terms of the degrees and the
number of input polynomials and independent of the actual coefficients of the
polynomials (so in particular they always terminate). In contrast to this
exact/symbolic model which is valid over arbitrary real closed fields, in
numerical analysis it is common to consider algorithms whose complexity do
depend on the coefficients (via a condition number). Such algorithms work only
over the field of real numbers and might not terminate on ill-conditioned
inputs (i.e. if the condition number is infinite). In this latter model,
algorithms with singly exponential complexity for computing all the Betti
numbers of semi-algebraic sets have been developed [14, 15, 16]. As noted
above, these algorithms will fail to produce any result on certain inputs.
Also, they do not produce semi-algebraic bases for the homology groups. In
this paper we will be concerned only with exact algorithms that work for all
possible inputs.

###  1.2. Model of computation and definition of complexity

There are several models of computation that one can consider while dealing
with semi-algebraic sets (and also several notions of what constitutes an
algorithm). If the real closed field $\mathrm{R}=\mathbb{R}$, and $\mbox{\rm
D}=\mathbb{Z}$, one can consider these algorithmic problems in the classical
Turing model and measure the bit complexity of the algorithms. In this paper,
we will follow the book [6] and take a more general approach valid over
arbitrary real closed fields. In the particular case, when $\mbox{\rm
D}=\mathbb{Z}$, our method will yield bit-complexity bounds. The precise
notion of complexity that we use is defined in Definition 1 below.

####  1.2.1. Definition of complexity

We will use the following notion of “complexity” in this paper. We follow the
same definition as used in the book [6].

######  Definition 1 (Complexity of algorithms).

In our algorithms we will usually take as input quantifier-free first order
formulas whose terms are polynomials with coefficients belonging to an ordered
domain D contained in a real closed field $\mathrm{R}$. By _complexity of an
algorithm_ we will mean the number of arithmetic operations and comparisons in
the domain D. If $\mbox{\rm D}=\mathbb{R}$, then the complexity of our
algorithm will agree with the Blum-Shub-Smale notion of real number complexity
[12]. 111 In case $\mbox{\rm D}=\mathbb{Z}$, it is possible to deduce the bit-
complexity of our algorithms in terms of the bit-sizes of the coefficients of
the input polynomials, and this will agree with the classical (Turing) notion
of complexity. We do not state the bit complexity separately in our
algorithms, but note that it is always bounded by a polynomial in the bit-size
of the input times the complexity upper bound stated in the paper.

It is also useful for what follows to introduce the following mathematical
definition of “complexity” of formulas and semi-algebraic sets.

####  1.2.2. $\mathcal{P}$-formulas, $\mathcal{P}$-semi-algebraic sets,
realizations

######  Notation 1 ($\mathcal{P}$-formulas, $\mathcal{P}$-closed formulas and
their realizations).

For any finite set of polynomials
$\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{k}]$, we call a quantifier-free
first order formula $\Phi$ with atoms $P=0,P<0,P>0,P\in\mathcal{P}$, to be a
_$\mathcal{P}$ -formula_. Given any semi-algebraic subset
$Z\subset\mathrm{R}^{k}$, we call the _realization of $\Phi$ in $Z$_, namely
the semi-algebraic set

$\displaystyle{\mathcal{R}}(\Phi,Z)$ $\displaystyle:=$
$\displaystyle\\{\mathbf{x}\in Z\mid\Phi(\mathbf{x})\\}$

a _$\mathcal{P}$ -semi-algebraic subset of $Z$_. If $Z=\mathrm{R}^{k}$, we
often denote the realization of $\Phi$ in $\mathrm{R}^{k}$ by
${\mathcal{R}}(\Phi)$.

We say that a quantifier-free formula $\Phi$ is _closed_ if it is a formula in
disjunctive normal form with no negations, and with atoms of the form $P\geq
0,P\leq 0$, where $P\in\mathrm{R}[X_{1},\ldots,X_{k}]$. If the set of
polynomials appearing in a closed formula is contained in a finite set
$\mathcal{P}$, we will call such a formula a $\mathcal{P}$-closed formula, and
we call the realization, ${\mathcal{R}}(\Phi,\mathrm{R}^{k})$, a
_$\mathcal{P}$ -closed semi-algebraic set_.

######  Definition 2 (Complexity of semi-algebraic sets).

For $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$, and
$\mathcal{P}$-formula (resp. $\mathcal{P}$-closed formula) $\Phi$, we say that
the complexity of $\Phi$ is bounded by $C$, where
$C=\mathrm{card}(\mathcal{P})\cdot d$, where
$d=\max_{P\in\mathcal{P}}\deg(P)$. If $S={\mathcal{R}}(\Phi,\mathrm{R}^{k})$,
then we will say that the complexity of $S$ is bounded by
$\mathrm{card}(\mathcal{P})\cdot d$.

For the rest of the paper we fix a field $\mathbb{F}$.

######  Notation 2.

For any closed semi-algebraic set $X$, we will denote by $\mbox{\rm
H}_{i}(X)=\mbox{\rm H}_{i}(X,\mathbb{F})$ the $i$-th homology group of $X$
with coefficients in $\mathbb{F}$ (we refer the reader to [6, Chapter 6] for
definition of homology groups of semi-algebraic subsets of $\mathrm{R}^{k}$,
where $\mathrm{R}$ is an arbitrary real closed field).

######  Notation 3.

Given $\mathbf{x}\in\mathrm{R}^{k},r>0$, we will denote by
$B_{k}(\mathbf{x},r)\subset\mathrm{R}^{k}$ the (open) euclidean ball of radius
$r$ centered at $\mathbf{x}$, and by $\mbox{${\bf
S}$}^{k-1}(\mathbf{x},r)\subset\mathrm{R}^{k}$, the sphere of radius $r$
centered at $\mathbf{x}$. Note that these are semi-algebraic subsets of
$\mathrm{R}^{k}$.

###  1.3. Singly vs doubly exponential

The problem of computing topological invariants (such as the number of semi-
algebraically connected components) of semi-algebraic sets in general is a
hard problem (known to be $\mathrm{PSPACE}$-hard in the Turing model).

From the point of view upper bounds on the complexity, these problems can be
solved by combinatorial means if we have in hand a triangulation of the given
semi-algebraic set. A semi-algebraic triangulation of a closed and bounded
semi-algebraic set $S\subset\mathrm{R}^{k}$, consists of a finite simplicial
complex $K$, and a semi-algebraic homeomorphism $h:|K|\rightarrow S$ (where
$|\cdot|$ denotes the _geometric realization_ functor). Moreover, the homology
group $\mbox{\rm H}_{*}(S)$ is isomorphic to the simplicial homology groups
$\mbox{\rm H}_{*}(K)$ which can be computed using standard linear algebra with
complexity polynomial in the size of $K$.

Closed and bounded semi-algebraic sets admit semi-algebraic triangulations,
and more pertinently such triangulations can be effectively computed. However,
the algorithms with the best complexity for computing such triangulations have
_doubly exponential_ complexity (doubly exponential in $k$). More precisely,
if $S\subset\mathrm{R}^{k}$ is defined by a quantifier-free formula involving
$s$ polynomials of degrees at most $d$, the best algorithm for computing a
semi-algebraic triangulation of $S$ is bounded by $(sd)^{2^{O(k)}}$.

It is a common belief in algorithmic semi-algebraic geometry that topological
invariants satisfying a certain bound (say singly exponential) should in fact
be computable by algorithms with complexity reflecting the mathematical bound.
So invariants which are bounded singly exponential should in fact be
computable by algorithms with singly exponentially bounded complexity. The
intuition behind this belief is that the natural way to compute a topological
invariant (such as the the zero-th Betti number of a semi-algebraic set) is
often by computing a semi-algebraic representative or witnessing set (for
example, a semi-algebraic basis of $\mbox{\rm H}_{0}(S)$ in the case of the
zero-th homology – see Problem 2 below), and the cardinality of this
witnessing set is the invariant to be computed. One expects the complexity of
the algorithm for computing the witnessing set should reflect the complexity
of this set – which includes the cardinality but also its “algebraic
complexity” as well. The Betti numbers (ranks of homology groups) of semi-
algebraic sets admit singly exponential upper bounds [27, 29, 24]. From this
point of view one expects that there should exist algorithms for computing the
Betti numbers of semi-algebraic sets with complexity bounded singly
exponentially. Indeed, algorithms for computing the zero-th Betti number (i.e.
the number of semi-algebraically connected components 222The reason behind
insisting on “semi-algebraically” connected instead of just connected (in the
Euclidean topology) is that over an arbitrary real closed field these two
notions are distinct. On the other hand if $\mathrm{R}=\mathbb{R}$, then being
semi-algebraically connected is equivalent to being connected (see for example
[6, Theorem 5.22]).) of semi-algebraic sets have been investigated in depth,
and nearly optimal algorithms are known for this problem.

###  1.4. Computing a basis for $\mbox{\rm H}_{0}(S)$

As mentioned above, all algorithms for computing the zero-th Betti number
(i.e. the number of semi-algebraically connected components) of a given semi-
algebraic set actually solve the following more general problem.

######  Problem 1.

Given a quantifier-free formula $\Phi$ defining a semi-algebraic subset
$S\subset\mathrm{R}^{k}$, compute a finite subset $\Gamma\subset S$, such that
for each connected component $C$ of $S$, $\mathrm{card}(\Gamma\cap C)=1$ (i.e.
$\Gamma$ contains a unique representative from each connected component of
$S$).

######  Remark 1.

Note that one needs to allow points in $\Gamma$ whose coordinates are
algebraic over the ring generated by the coefficients of the polynomials
appearing in the formula $\Phi$. At this point we ignore the question of
representation of such points (cf. Definition 4 below) other than commenting
that any algorithm for solving this problem needs to address this issue.

Problem 1 has been studied in depth and we now have very close to optimal
algorithms for solving it. The solution is in two steps.

  1. Step 1.

The first and easier step is solving a weaker problem of computing a finite
subset $\Gamma\subset S$ of “sample points” with the property that for each
connected component $C$ of $S$, $\mathrm{card}(\Gamma\cap C)\geq 1$. (The
above property is equivalent to the property that the zero-th homology,
$\mbox{\rm H}_{0}(S,\Gamma)$, of the pair $(S,\Gamma)$ is trivial.) There are
now very efficient algorithms for solving this problem (see for example, [22,
3], [6, Algorithm 13.3 (Sample points on a variety)]). In fact, such
algorithms form the basic building block for efficient algorithms for solving
the quantifier-elimination algorithms in the theory of the reals.

  2. Step 2.

The second step is more complicated and involves solving the problem of
deciding whether two given points in a semi-algebraic set $S$ belong to the
same semi-algebraically connected component of $S$ efficiently. This problem
has a long history. The key idea is that of a roadmap of a semi-algebraic set
(cf. Definition 3 for a precise definition).

If we have a roadmap $\Gamma$ of $S$ which contains $\mathbf{x},\mathbf{y}\in
S$, then it is easy to decide whether $\mathbf{x}$ and $\mathbf{y}$ belong to
the same semi-algebraically connected component of $\Gamma$, which tells us if
they are in the same semi-algebraically connected component of $S$ itself
because of the defining property of a roadmap. There exists singly exponential
complexity algorithms for construction of roadmaps of semi-algebraic sets [17,
20, 21, 23, 4], and hence for the problem of deciding whether two given points
belong to the same semi-algebraically connected component of a semi-algebraic
set. Once we can decide if two points of the set of sample points $\Gamma$
belong to the same semi-algebraically connected component of $S$, we can then
select exactly one point in every semi-algebraically connected component of
$S$ and thus obtain a singly-exponential algorithm for solving Problem 1.

####  1.4.1. Interpretation in terms of a homology basis

Note that Problem 1 can be reformulated in terms of homology as follows.

######  Problem 2.

Given a quantifier-free formula $\Phi$ defining a semi-algebraic subset
$S\subset\mathrm{R}^{k}$, compute a semi-algebraic basis of $\mbox{\rm
H}_{0}(S)$. More precisely, compute a semi-algebraic subset
$\Gamma=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{N}\\}\subset S$, such that the
subspaces $[\mathbf{x}_{1}],\ldots,[\mathbf{x}_{N}]\subset\mbox{\rm H}_{0}(S)$
are linearly independent and span $\mbox{\rm H}_{0}(S)$. Here
$[\mathbf{x}_{i}]$ is the image of $\mbox{\rm
H}_{0}(\\{\mathbf{x}_{i}\\})(\cong\mathbb{F})$ in $\mbox{\rm H}_{0}(S)$ under
the linear map induced by the inclusion $\\{\mathbf{x}_{i}\\}\hookrightarrow
S$.

The discussion in the beginning of this subsection yields the following
theorem.

######  Theorem 1.

[17, 20, 21, 23, 4] There exists an algorithm that takes as input a finite set

$\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}],$

and a $\mathcal{P}$-formula $\Phi$ whose complexity is bounded by $C$, and
outputs a semi-algebraic basis, $\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{N}\\}$,
of $\mbox{\rm H}_{0}({\mathcal{R}}(\Phi))$. The complexity of each
$\mathbf{x}_{i}$ (as a semi-algebraic subset of $\mathrm{R}^{k}$ defined over
D), as well as the complexity of the algorithm, are both bounded by
$C^{k^{O(1)}}$.

##  2\. New Results

We now state the new results proved in the paper.

###  2.1. Generalization to the first homology group

The main goal of this paper is to prove an analog of Theorem 1 with the zero-
th homology group replaced by the first homology group. The following theorem
is the main result of the paper.

######  Theorem 2.

There exists an algorithm that takes as input a finite set

$\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}],$

and a $\mathcal{P}$-closed formula $\Phi$ whose complexity is bounded by $C$,
and outputs a finite set $\mathcal{Q}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$,
as well as a finite tuple $(\Psi_{j})_{j\in J}$, in which each $\Psi_{j}$ is a
$\mathcal{Q}$-formula, such that the realizations
$\Gamma_{j}={\mathcal{R}}(\Psi_{j},\mathrm{R}^{k})$ have the following
properties:

  1. 1.

For each $j\in J$, $\Gamma_{j}\subset S$ and $\Gamma_{j}$ is semi-
algebraically homeomorphic to $\mbox{${\bf S}$}^{1}$ ( $=\mbox{${\bf
S}$}^{1}(\mathbf{0},1)$);

  2. 2.

the inclusion map $\Gamma_{j}\hookrightarrow S$ induces an injective map
$\mathbb{F}\cong\mbox{\rm H}_{1}(\Gamma_{j})\rightarrow\mbox{\rm H}_{1}(S)$,
whose image we denote by $[\Gamma_{j}]$;

  3. 3.

the tuple $([\Gamma_{j}])_{j\in J}$ forms a basis of $\mbox{\rm H}_{1}(S)$.

The complexity of each $\Gamma_{j},j\in J$ (as a semi-algebraic subset of
$\mathrm{R}^{k}$ defined over D) is bounded by $C^{O(k^{2})}$, and the
complexity of this algorithm is bounded by $C^{k^{O(1)}}$.

###  2.2. Connections with the “basic lemma” in complex algebraic geometry

As mentioned previously, designing an efficient algorithm (i.e. with singly
exponential complexity) for computing semi-algebraic triangulations of semi-
algebraic sets is one of the most important open problems in algorithmic semi-
algebraic geometry. In the absence of such an algorithm, several low
dimensional work-arounds have been designed to compute important topological
invariants without having to compute a full triangulation. For example, there
are algorithms with singly exponential complexity for computing the first
$\ell$ Betti numbers (for any fixed $\ell\geq 0$) which do not use
triangulations [2]. More recently, in [9], the authors give an algorithm with
singly exponential complexity for computing a simplicial complex which is
homologically $\ell$-equivalent (see Definition 9 below) to a given closed
semi-algebraic set (for any fixed $\ell\geq 0$).

Over the complex numbers, algebraic varieties cannot be triangulated (in the
usual topological sense) using algebraic sets and maps. The following result
(see for example [25] where it is called the “Basic Lemma”) serves as a
substitute and can be considered a weak analog in complex algebraic geometry
of the property that real semi-algebraic sets can be triangulated using semi-
algebraic maps.

######  Lemma 1 (Basic Lemma - first form [25]).

Let $K$ be a subfield of $\mathrm{C}$. Let $W$ be Zariski closed in an affine
variety $X$ defined over $K$. Assume $\dim W<\dim_{\mathrm{C}}X$. Then, there
is a Zariski closed $Z$ in $X$ so that $\dim_{\mathrm{C}}Z<\dim_{\mathrm{C}}X$
with $W_{\mathrm{C}}\subset Z$, and

$\mbox{\rm H}_{q}(X,Z)=0,$

whenever $q\neq\dim_{\mathrm{C}}X$.

######  Remark 2.

Note also that by applying Lemma 1 repeatedly to an affine variety $X$ of
dimension $n$, one obtains Zariski closed subsets of $X$,

$Z^{(n-1)}\supset\cdots Z^{(i)}\supset\cdots\supset Z^{(1)}\supset Z^{(0)}$

with $\dim Z^{(i)}\leq i$, and $\mbox{\rm H}_{q}(X,Z^{(i)})=0$ for $0\leq
q\leq i$. (This follows from applying the basic lemma with $W=\emptyset$,
first to $X$ to obtain $Z^{(n-1)}$, and then to $Z^{(n-1)}$ to obtain
$Z^{(n-2)}$ and so on, and the homology long exact sequence of the various
triples $(X,Z^{(i)},Z^{(i-1)})$.)

One could ask for a semi-algebraic version of the basic lemma, where $W,X,Z$
are closed semi-algebraic subsets (or even Zariski closed subsets) of
$\mathrm{R}^{k}$, where $\mathrm{R}$ is a real closed field. The proof of the
basic lemma (actually of a stronger version) given in [25] is valid over real
closed fields. However, the proof is not effective in the sense that no bound
on the complexity of $Z$ is given (in terms of the complexities of $X$ and
$W$). However, since the proof depends on iterated projections, the complexity
of the construction is likely to be doubly exponential.

Notice that in the semi-algebraic case (taking $W=\emptyset$), one can take
$Z=Z^{(i)}=h(|\mathrm{sk}_{i}(K)|)$, where $h:|K|\rightarrow X$ is a semi-
algebraic triangulation of $X$, and $\mathrm{sk}_{q}(K)$ denotes the
$q$-dimensional skeleton of $K$. The sequence of semi-algebraic subsets
$Z^{(\dim X-1)}\supset\cdots\supset Z^{(0)}$ would then satisfy the properties
of Remark 2. However, it is clear that the best complexity one can obtain in
this way is doubly exponential. The existence of the sequence $Z^{(i)}$ over
algebraically closed fields (cf. Remark 2) inspires the following the
question.

Is it possible to prove in the semi-algebraic case the existence of a similar
sequence satisfying the homological property in Remark 2, but where the the
subsets $Z^{(i)}$ do not correspond to skeleta of some triangulation – and
hence could be potentially of smaller complexity ?

In fact, it makes sense to ask for the existence of the sequence $Z^{(i)}$
whose complexity is graded in terms of $i$ i.e. $Z^{(0)}$ has the smallest
complexity, followed by $Z^{(1)}$, and so on. We formulate below a
quantitative conjecture which is a version of the basic lemma in the semi-
algebraic case as follows.

######  Conjecture 1.

Let $X\subset\mathrm{R}^{k}$ be a semi-algebraic set defined by a closed
formula of complexity bounded by $C$, and let $\dim X=n$. Then there exists
closed semi-algebraic subsets of $X$,

$Z^{(n-1)}\supset\cdots\supset Z^{(1)}\supset Z^{(0)}$

with $\dim Z^{(i)}\leq i$, and $\mbox{\rm H}_{q}(X,Z^{(i)})=0$ for $0\leq
q\leq i$, such that for each ${i,0\leq i\leq n-1}$, the complexity of
$Z^{(i)}$ is bounded by $C^{O(k^{i+1})}$.

Moreover, there exists an algorithm for computing closed formulas describing
$Z^{(0)},\ldots,Z^{(\ell)},0\leq\ell\leq n-1$, whose complexity is bounded by
$C^{k^{O(\ell)}}$.

######  Remark 3.

Conjecture 1 is especially interesting because of the following observation.
The standard algorithms for triangulating semi-algebraic sets using
cylindrical algebraic decomposition (see for example [6, Chapter 5]) can be
modified so that their complexities are bounded doubly exponentially only in
the dimension of the given semi-algebraic set rather than that of the ambient
space. Hence if Conjecture 1 is true, then it will provide an alternative
approach (compared to [2, 9]) towards the problem of computing the the first
$\ell$ Betti numbers of any given semi-algebraic set with singly exponential
complexity for each fixed $\ell$. In this paper, we take an initial step
towards verifying the conjecture (see Theorem 3). We believe that the same
inductive approach used in the proof of Proposition 3 can be generalized to
handle the full conjecture.

We prove the following.

######  Theorem 3.

With the same notation as in Conjecture 1, there exists closed semi-algebraic
subsets of $X$,

$Z^{(1)}\supset Z^{(0)}$

with $\dim Z^{(i)}\leq i$, and $\mbox{\rm H}_{q}(X,Z^{(i)})=0$ for $0\leq
q\leq i,i=0,1$, such that the complexities of $Z^{(0)},Z^{(1)}$ are bounded by
$C^{O(k^{2})}$.

Moreover, there exists an algorithm for computing closed formulas describing
$Z^{(0)},Z^{(1)}$, whose complexity is bounded by $C^{k^{O(1)}}$.

###  2.3. Comparison with roadmaps

One of our intermediate constructions, namely the semi-algebraic subset
$Z^{(1)}$ in Theorem 3 (also the set $\Gamma$ constructed in Algorithm 4) is
reminiscent of roadmaps of semi-algebraic sets (mentioned earlier), and their
construction is somewhat similar to the (classical) construction of roadmaps.
333More modern algorithms such as those described in [7, 11] use different
techniques. We describe here the key difference between our construction and
the classical construction of roadmaps in Section 4.1 where we give an outline
of Algorithm 4. In this section, we recall the defining property of roadmaps
of semi-algebraic sets and indicate why a roadmap is not sufficient for the
purposes of the current paper.

The following definition is taken from [6, Chapter 15]. Let
$S\subset\mathrm{R}^{k}$ be a semi-algebraic set. We denote by
$\pi_{1}:\mathrm{R}^{k}\rightarrow\mathrm{R}$ the projection to the
$X_{1}$-coordinate and denote for $x\in\mathrm{R}$,
$S_{x}=S\cap\pi_{1}^{-1}(x)$ (cf. Notation 6 below).

######  Definition 3.

A semi-algebraic subset $\Gamma\subset S$ is called a roadmap of $S$ if it
satisfies the following properties:

  1. $\mathrm{RM}_{0}$.

$\dim\Gamma\leq 1$;

  2. $\mathrm{RM}_{1}$.

for every semi-algebraically connected component $C$ of $S$, $C\cap\Gamma$ is
semi-algebraically connected;

  3. $\mathrm{RM}_{2}$.

for every $x\in\mathrm{R}$ and for every semi-algebraically connected
component $D$ of $S_{x}$, $D\cap\Gamma\neq\emptyset$.

######  Remark 4.

We note that the design of efficient algorithms for construction of roadmaps
of semi-algebraic sets has a long history [17, 20, 21, 23, 4]. The algorithm
with the best complexity can be found in [4]. The complexity of this algorithm
is bounded by $s^{k^{\prime}+1}d^{O(k^{2})}$, where $s$ is the number of
polynomials used to define the given set, $d$ a bound on their degrees, $k$
the dimension of the ambient space, and $k^{\prime}$ is the dimension of a
real variety containing the given set [4]. More recently, the dependence on
$k$ in the exponent has been further improved using new methods [7, 11], but
for the moment these new algorithms work only for algebraic (rather than semi-
algebraic) sets.

Notice that if $S$ is a closed semi-algebraic set and $\Gamma\subset S$ is a
roadmap of $S$, then the homomorphism $i_{*,1}:\mbox{\rm
H}_{1}(\Gamma)\rightarrow\mbox{\rm H}_{1}(S)$ need not be surjective. A simple
example of this phenomenon is provided by a torus $T\subset\mathrm{R}^{3}$ as
depicted in Figure 3.

Figure 1. figure

$T\subset\mathrm{R}^{3}$

Figure 2. figure

$\Gamma\subset T$

Figure 3. figure

$\Gamma^{\prime}\subset T$

The classical construction of roadmap (see for example [6, Chapter 15])
produces the one dimensional semi-algebraic subset $\Gamma$ depicted in Figure
3. In this example, the set $\Gamma$ does satisfy the property that $\mbox{\rm
H}_{q}(T,\Gamma)=0,q=0,1$, though this is not ensured by the classical roadmap
algorithm. However, notice that if we take the subset
$\Gamma^{\prime}\subset\Gamma$ consisting only of the larger horizontal circle
as depicted in the Figure 3, then $\Gamma^{\prime}$ does satisfy the property
of being a roadmap of $T$ (cf. Definition 3), but $\mbox{\rm
H}_{1}(T,\Gamma^{\prime})\neq 0$ (in fact, $\dim\mbox{\rm
H}_{1}(T,\Gamma^{\prime})=1$).

The rest of the paper is devoted to proving Theorems 2 and 3. In Section 3, we
discuss some preliminaries including definitions of representations of real
algebraic numbers, points, and curve segments that we use in our algorithms.
In Section 4, we prove Theorems 2 and 3.

##  3\. Preliminaries

###  3.1. Some notation

######  Notation 4 (Sign conditions).

For a finite set $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{k}]$ we will
call any element of $\\{0,1,-1\\}^{\mathcal{P}}$ a _sign condition on
$\mathcal{P}$_. For a semi-algebraic subset $Z\subset\mathrm{R}^{k}$, we will
denote by

${\mathcal{R}}(\sigma)=\\{\mathbf{x}\in Z\;|\;\mbox{\bf
sign}(P(\mathbf{x}))=\sigma(P),P\in\mathcal{P}\\}.$

Given a sign condition $\sigma\in\\{0,1,-1\\}^{\mathcal{P}}$, we will denote
by $\overline{\sigma}$ the formula defined by

$\overline{\sigma}=\bigwedge_{\sigma(P)=0}(P=0)\wedge\bigwedge_{\sigma(P)=1}(P\geq
0)\wedge\bigwedge_{\sigma(P)=-1}(P\leq 0),$

and call $\overline{\sigma}$ the _weak sign condition associated to $\sigma$_.

######  Notation 5 (Closure).

For any semi-algebraic subset $S\subset\mathrm{R}^{k}$, we will denote by
$\mathrm{clos}(S)$ the closure of $S$ (in the euclidean topology). It is a
consequence of the fact that theory of real closed fields admits quantifier-
elimination that $\mathrm{clos}(S)$ is again a semi-algebraic subset of
$\mathrm{R}^{k}$.

######  Notation 6 (Projections to coordinate subspaces).

We will denote by $\pi_{i}:\mathrm{R}^{k}\rightarrow\mathrm{R}$, the
projection on to the $i$-th coordinate. More generally, for a subset
$J\subset\\{1,\ldots,k\\}$, we denote by
$\pi_{J}:\mathrm{R}^{k}\rightarrow\mathrm{R}^{J}$, the projection on the
coordinates indexed by $J$. In particular,
$\pi_{[1,i]}:\mathrm{R}^{k}\rightarrow\mathrm{R}^{[1,i]}$ will denote the
projection onto the first $i$ coordinates.

For $1\leq i\leq k$, $S\subset\mathrm{R}^{k}$, $J\subset\\{1,\ldots,k\\}$, and
$Z\subset\mathrm{R}^{J}$, we will denote by $S_{Z}=\pi^{-1}_{J}(Z)\cap S$. If
$Z=\\{\mathbf{z}\\}\subset\mathrm{R}^{J}$, then we will write $S_{\mathbf{z}}$
instead of $S_{\\{\mathbf{z}\\}}$.

###  3.2. Representations of points and curves

While the algorithms that we describe have certain geometric underpinnings, it
is important to remember that the points and curve segments that we compute
need to be represented algebraically, and hence we need to specify the precise
representations that we use.

Moreover, we often fix a set of coordinates (say $(X_{1},\ldots,X_{i})$), to
$\mathbf{t}=(t_{1},\ldots,t_{i})$ and call an algorithm recursively in the
fiber $\\{\mathbf{t}\\}\times\mathrm{R}^{k-i}$. This necessitates the
introduction of triangular Thom encodings (which fixes points), and all our
representations of points and curve segments are introduced relative to such
triangular Thom encodings.

The following definitions are adapted from [6].

We begin with the representations of elements of $\mathrm{R}$ (which are
algebraic over D) as roots of polynomials in $\mbox{\rm D}[X]$ with a given
Thom encoding (cf. Definition 4 below).

######  Definition 4 (Thom encoding, associated element of $\mathrm{R}$).

For $P\in\mathrm{R}[X]$ we will denote by

${\rm Der}(P)=\left(P,P^{\prime},\ldots,P^{(\deg(P))}\right)$

the list of derivatives of $P$.

We will call a pair $\tau=(P,\sigma)$ with $\sigma\in\\{0,1,-1\\}^{{\rm
Der}(P)}$, the _Thom encoding of $x\in\mathrm{R}$_ 444It is a consequence of
the well-known Thom’s lemma, that the Thom encoding uniquely characterizes a
root in $\mathrm{R}$ of a polynomial in $\mbox{\rm D}[X]$ (see for example,
[6, Proposition 2.27]). , if $\sigma(P)=0$ and $\sigma(P^{(i)})=\mbox{\bf
sign}(P^{(i)}(x))$ for $0\leq i\leq\deg(P)$.

We will sometimes abuse notation and sometime call $\sigma$ _the Thom encoding
of the root $x$ of $P$_. We will denote $x$ by $\mathrm{ass}(\tau)$, and call
$\mathrm{ass}(\tau)$ _the element of $\mathrm{R}$ associated to $\tau$_.

We will call $\deg(P)$ to be _the degree of the Thom encoding $\tau$_, and
denote it by $\deg(\tau)$.

As remarked before we will often need to fix a block of variables
$(X_{1},\ldots,X_{i})$ to $\mathbf{t}=(t_{1},\ldots,t_{i})\in\mathrm{R}^{i}$,
and perform arithmetic operations in the ring $\mbox{\rm D}[\mathbf{t}]$. For
this purpose we introduce the notion of a triangular Thom encoding whose
associated point is an element of $\mathrm{R}^{i}$.

######  Definition 5 (Triangular Thom encoding and associated point).

A _triangular Thom encoding_ $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size
$i$ is a tuple (triangular system) of polynomials,

$\mathbf{F}=(f_{1},\ldots,f_{i})$

where $f_{j}\in\mathrm{R}[X_{1},\ldots,X_{j}],1\leq j\leq i$, and a tuple of
Thom encodings $\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{i})$, with
$\sigma_{j}\in\\{0,1,-1\\}^{{\rm Der}_{X_{j}}(f_{j})}$, such that for each
$j,1\leq j\leq i$, there exists $t_{j}\in\mathrm{R}$, such that $t_{j}$ is a
root of the polynomial $f_{j}(t_{1},\ldots,t_{j-1},T_{j})$ with Thom encoding
$\sigma_{j}$. We call $(t_{1},\ldots,t_{i})\in\mathrm{R}^{i}$ the _point
associated to $\mathcal{T}$_ and denote
$\mathrm{ass}(\mathcal{T})=(t_{1},\ldots,t_{i})$.

Given a triangular Thom encoding

$\mathcal{T}^{+}=((f_{1},\ldots,f_{i+1}),(\sigma_{1},\ldots,\sigma_{i+1})),$

with $\mathrm{ass}(\mathcal{T}^{+})=(t_{1},\ldots,t_{i+1})$, we will sometimes
call the pair $\tau=(f_{i+1},\sigma_{i+1})$ a _Thom encoding over the
triangular Thom encoding
$\mathcal{T}=((f_{1},\ldots,f_{i}),(\sigma_{1},\ldots,\sigma_{i}))$_. In this
case we will denote $t_{i+1}$ by $\mathrm{ass}(\tau)$ (generalizing Definition
4).

We will call $\max_{1\leq j\leq i}\deg(F_{j})$ the degree of the triangular
Thom encoding $\mathcal{T}$, and denote it by $\deg(\mathcal{T})$.

If $\tau=(f_{i+1},\sigma_{i+1})$ a is Thom encoding over a triangular Thom
encoding

$\mathcal{T}=((f_{1},\ldots,f_{i}),(\sigma_{1},\ldots,\sigma_{i})),$

we will call $\deg_{T_{i+1}}(f_{i+1})$, the degree of $\tau$, and denote it by
$\deg(\tau)$.

Finally, given a triangular Thom encoding
$\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size $i$, we denote by
$\theta(\mathcal{T})$, the formula

$\bigwedge_{1\leq j\leq i}\;\;\bigwedge_{0\leq
h\leq\deg_{X_{j}}(f_{j})}\left(\mbox{\bf
sign}(f_{j}^{(h)})=\sigma_{j}(f_{j}^{(h)})\right).$

######  Notation 7.

Given a triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of
size $i$ (following the same notation as in Definition 5 above), we will
denote by $\overline{\bm{\sigma}}$, the closed formula obtained from
$\bm{\sigma}$ by replacing each sign condition on the derivatives by the
corresponding weak inequality (i.e. replacing $f_{j}^{(h)}>0$ by
$f_{j}^{(h)}\geq 0$ and $f_{j}^{(h)}<0$ by $f_{j}^{(h)}\leq 0$).

It is a consequence of Thom’s lemma [6] that:

######  Lemma 2.

Given a triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of
size $i$,

$\mathrm{ass}(\mathcal{T})={\mathcal{R}}(\overline{\bm{\sigma}},\mathrm{R}^{i}).$

###### Proof.

Follows directly from [6, Proposition 5.39] (Generalized Thom’s Lemma). ∎

We will represent points in $\mathrm{R}^{k}$ using real univariate
representations [6, pp. 465] defined below. As explained previously, we need
to define this notion with a block of variables fixed by a triangular Thom
encoding. In this case the first $i$ coordinates of the point are fixed by a
triangular Thom encoding, and the real univariate representation specifies the
remaining $k-i$ coordinates.

######  Definition 6 (Real univariate representations over a triangular Thom
encoding and associated point).

Let $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ be a triangular Thom encoding of
size $i,0\leq i<k$.

A _real univariate representation $u$ in $\mathrm{R}^{k}$ over $\mathcal{T}$_
is a pair $(F,\sigma)$ where
$F=(f,g_{0},g_{i+1},\dots,g_{k})\in\mathrm{R}[X_{1},\ldots,X_{i},T]$, with
$f(\mathrm{ass}(\mathcal{T}),T),g_{0}(\mathrm{ass}(\mathcal{T}),T)$ co-prime,
and $\sigma$ a Thom encoding of a real root of
$f(\mathrm{ass}(\mathcal{T}),T)\in\mathrm{R}[T]$.

We denote by $\mathrm{ass}(u)\in\mathrm{R}^{k}$ the point

(3.1)
$\left(\mathrm{ass}(\mathcal{T}),\frac{g_{i+1}(\mathrm{ass}(\mathcal{T}),\mathrm{ass}(\tau))}{g_{0}(\mathrm{ass}(\mathcal{T}),\mathrm{ass}(\tau))},\ldots,\frac{g_{k}(\mathrm{ass}(\mathcal{T}),\mathrm{ass}(\tau))}{g_{0}(\mathrm{ass}(\mathcal{T}),\mathrm{ass}(\tau))}\right)\in\mathrm{R}^{k},$

where $\tau=(f,\sigma)$ (notice that $\tau$ is a Thom encoding over
$\mathcal{T}$), and call $\mathrm{ass}(u)$ _the point associated to $u$_.

We will call the pair $(D_{1},D_{2})$, denoted $\deg(u)$, the degree of $u$,
where $D_{1}=\deg(\mathcal{T})$ and $D_{2}$ is the maximum of
$\deg_{T}(f),\deg_{T}(g_{0}),\ldots,\deg_{T}(g_{k})$.

We describe semi-algebraic curve segments by real univariate representations
parametrized by one of the coordinates. As before the following definition
assumes a triangular Thom encoding fixing the first $i$ coordinates.

######  Definition 7 (Curve segment representation over a triangular Thom
encoding).

Let $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ be a triangular Thom encoding of
size $i,0\leq i\leq k-1$. A _curve segment representation $\gamma$ above
$\mathcal{T}$_ consists of:

  1. (a)

Thom encodings, $\tau_{1}=\tau_{1}(\gamma),\tau_{2}=\tau_{2}(\gamma)$, over
$\mathcal{T}$, with $\mathrm{ass}(\tau_{1})<\mathrm{ass}(\tau_{2})$;

  2. (b)

a pair $(u,\rho)=(u(\gamma),\rho(\gamma))$, where

$u=(f,g_{0},g_{i+2},\ldots,g_{k})\in\mathrm{R}[X_{1},\ldots,X_{i+1},T]^{k-i+1},$

and

$\rho\in\\{0,1,-1\\}^{{\rm Der}_{T}(f)},$

such that for every
$x_{i+1}\in(\mathrm{ass}(\tau_{1}),\mathrm{ass}(\tau_{2}))$ there exists a
real root $t(x_{i+1})$ of $f(\mathrm{ass}(\mathcal{T}),x_{i+1},T)$ with Thom
encoding $\rho$ and

$f(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1})),g_{0}(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1}))$

co-prime.

We will call $(\tau_{1},\tau_{2})$ the _Thom encoding of the interval of
definition of $\gamma$_.

The semi-algebraic function $h$ which maps
$x_{i+1}\in(\mathrm{ass}(\tau_{1}),\mathrm{ass}(\tau_{2}))$ to the point of
$\mathrm{R}^{k}$ defined by

$h(x_{i+1})=\left(\mathrm{ass}(\mathcal{T}),x_{i+1},\frac{g_{i+2}(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1}))}{g_{0}(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1}))},\ldots,\frac{g_{k}(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1}))}{g_{0}(\mathrm{ass}(\mathcal{T}),x_{i+1},t(x_{i+1}))}\right),$

is a continuous injective semi-algebraic function, and we will denote its
image by $\mathrm{ass}(\gamma)$.

We will also call $\lim_{x_{i+1}\rightarrow\mathrm{ass}(\tau_{1})+}h(x_{i+1})$
(resp. $\lim_{x_{i+1}\rightarrow\mathrm{ass}(\tau_{2})-}h(x_{i+1})$) (if it is
defined) the _left end-point_ (resp. _right end-point_) of $\gamma$.

We will call the pair $(D_{1},D_{2})$, denoted $\deg(\gamma)$, the degree of
$\gamma$, where

$D_{1}=\deg(\mathcal{T}),$

and $D_{2}$ is the maximum of

$\deg(\tau_{1}),\deg(\tau_{2}),\deg_{X_{i+1,T}}(f),\deg_{X_{i+1,T}}(g_{0}),\deg_{X_{i+1,T}}(g_{i+2}),\ldots,\deg_{X_{i+1,T}}(g_{k}).$

######  Remark 5.

Note that in Definition 7, $\mathrm{ass}(\gamma)$ is a semi-algebraic set of
dimension one, and if it is bounded over $\mathrm{R}$, then its left and right
endpoints are well-defined.

Also note that if $i=k-1$, and $\tau_{1},\tau_{2}$ are two Thom encodings over
$\mathcal{T}$ with $\mathrm{ass}(\tau_{1})<\mathrm{ass}(\tau_{2})$, then if
$\gamma$ is the curve segment representation over $\mathcal{T}$ defined by,

$\displaystyle\tau_{1}(\gamma)$ $\displaystyle=$ $\displaystyle\tau_{1},$
$\displaystyle\tau_{2}(\gamma)$ $\displaystyle=$ $\displaystyle\tau_{2},$
$\displaystyle u(\gamma)$ $\displaystyle=$ $\displaystyle((T,1),(0,1)),$

then
$\mathrm{ass}(\gamma)=\\{\mathrm{ass}(\mathcal{T})\\}\times(\mathrm{ass}(\tau_{1}(\gamma)),\mathrm{ass}(\tau_{2}(\gamma)))$.
Thus, an open interval whose end points are given by Thom encodings can be
represented by the curve segment representation given above and we will later
use this fact without mention.

##  4\. Proofs of Theorems 2 and 3

###  4.1. Outline of the proofs of Theorems 2 and 3

As in the case of the zero-th homology in Section 1.4 we solve the problem in
two steps (cf. Steps 1 and 2 in the solution of Problem 1).

  1. Step 1.

In the first step, we develop an algorithm (see Algorithm 4 below) that takes
as input a $\mathcal{P}$-closed formula $\Phi$, and produces as output a
description of a semi-algebraic subset $\Gamma\subset S={\mathcal{R}}(\Phi)$,
having dimension $\leq 1$, and such that the homomorphism $i_{*,1}:\mbox{\rm
H}_{1}(\Gamma)\rightarrow\mbox{\rm H}_{1}(S)$ induced by the inclusion
$i:\Gamma\hookrightarrow S$ is surjective, and the homomorphism
$i_{*,0}:\mbox{\rm H}_{0}(\Gamma)\rightarrow\mbox{\rm H}_{0}(S)$ is an
isomorphism. This is equivalent to $\mbox{\rm H}_{q}(S,\Gamma)=0$ for $q=0,1$.

This is the analog of Step 1 in the outline for the solution of Problem 1
above. The main idea behind the construction of $\Gamma$ comes from the
classical construction of a roadmap of a semi-algebraic set $S$ that goes as
follows (see also the description in [6, Chapter 15]. One first computes
curves parametrized by the $X_{1}$-coordinate, such that the set of curves so
constructed meets, for every $x\in\mathrm{R}$, each semi-algebraically
connected component of $S_{x}$. The algorithm is then called recursively on a
certain finite set of “slices”, namely on sets of the form $S_{x}$, where
$x\in\mathrm{R}$ varies over a certain finite set of _distinguished values_.
The set of distinguished values includes values at which the connectivity of
the set $S_{\leq x}$ changes. Algorithm 4 follows a similar paradigm. The main
_new feature_ is that the set of distinguished values at which the algorithm
makes recursive calls satisfies a stronger property than in the case of
roadmap algorithms (cf. Proposition 2 below). This stronger property of the
distinguished values allows us to prove inductively (using a little
homological algebra via the “Five-lemma” [13]), the _surjectivity_ of the map
$i_{*,1}:\mbox{\rm H}_{1}(\Gamma)\rightarrow\mbox{\rm H}_{1}(S)$. The proof of
the _isomorphism_ $i_{*,0}:\mbox{\rm H}_{0}(\Gamma)\rightarrow\mbox{\rm
H}_{0}(S)$ is the same as in the classical construction of a roadmap of a
semi-algebraic set. It follows from the exact homology sequence of the pair
$(S,\Gamma)$, that $\mbox{\rm H}_{q}(S,\Gamma)=0$, for $0\leq q\leq 1$. The
semi-algebraic set $\Gamma$ is initially described as a union of points and
curve segments (cf. Definitions 6 and 7)). Converting this description into an
equivalent _closed_ formula of complexity bounded singly exponentially (cf.
Algorithm 5 (Conversion of curve segment representations to closed formulas))
yields a proof of Theorem 3.

  2. Step 2.

In this step we use the fact that the semi-algebraic set $\Gamma$ is semi-
algebraically homeomorphic to the geometric realization $|G|$ of a finite
graph $G$ having singly exponential size, and it is a relatively easy
combinatorial task to choose a basis of simple cycles,
$\Gamma_{1},\ldots,\Gamma_{N}$, for the cycle space of $G$. The images
$[\Gamma_{1}],\ldots,[\Gamma_{N}]$ (here $[\Gamma_{i}]$ denotes the image of
$\mbox{\rm H}_{1}(|\Gamma_{i}|)$ in $\mbox{\rm H}_{1}(S)$ under the
homomorphism induced by the inclusion $|\Gamma_{i}|\hookrightarrow S$), span
$\mbox{\rm H}_{1}(S)$ but are not necessarily linearly independent. We need to
select a minimal spanning subset from amongst the
$[\Gamma_{1}],\ldots,[\Gamma_{N}]$. For this purpose we use an algorithm for
replacing a given semi-algebraic set and a tuple of subsets by a simplicial
complex and a tuple of corresponding subcomplexes, which are homologically
$\ell$-equivalent (cf. Definition 9) for any fixed $\ell$, and which has
singly exponentially bounded complexity [9] (cf. Algorithm 6 below). We use
this algorithm in the case $\ell=1$. This is analogous to the usage of a
roadmap algorithm for overcoming the corresponding obstacle in the case of the
zero-th homology (cf. Step 2 in the outline for the solution of Problem 1).

We now describe in detail the two steps outlined above.

###  4.2. Implementing Step 1: computing surjection

In this section we describe an algorithm which will accomplish Step 1 of the
two-step algorithm sketched out in Section 4.1. Recall that the goal of this
step is to obtain an algorithm with singly exponential complexity that
computes a description of a semi-algebraic subset $\Gamma$ having dimension at
most one, such that $\mbox{\rm H}_{q}(S,\Gamma)=0,q=0,1$.

As mentioned previously, we will follow the same approach of constructing a
roadmap of $S$ (see for instance [6, Chapters 15 and 16]), however with one
key additional property.

####  4.2.1. Morse-type partition

In the (classical) construction of the roadmap, one makes recursive calls to
the roadmap constructing algorithm at certain special fibers where the $X_{1}$
coordinate is fixed to certain values (called “distinguished values” in [6]).
Thee distinguished values include the values $c$ of the $X_{1}$ coordinate
where the connectivity of the fiber $S_{c}$ can change. This is sufficient for
construction of roadmaps, since the main property of the roadmap is related to
connectivity (the intersection of the roadmap with any semi-algebraically
connected component of $S$ should be semi-algebraically connected). Since in
this paper we are mainly concerned with the first homology group, we need our
set of distinguished values to satisfy a more stringent property. Fortunately,
there exists a singly exponential complexity algorithm for this purpose which
we are going to utilize.

The following algorithm (without a triangular Thom encoding in the input)
appears in [9, Algorithm 6]. However, as remarked before in our applications,
it will be necessary to fix a block of $i$ variables by a triangular Thom
encoding $\mathcal{T}$, and perform the computations over the ring $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$. Each arithmetic operation in the ring
$\mbox{\rm D}[\mathrm{ass}(\mathcal{T})]$ costs $D^{O(i)}$ arithmetic
operations in D, where $D=\deg(\mathcal{T})$.

Algorithm 1 (Morse partition)

1:

2:

  1. (a)

$r=\frac{a}{b},a,b\in\mbox{\rm D},a,b>0$;

  2. (b)

A triangular Thom encoding $\mathcal{T}$ of size $i,0\leq i\leq k$;

  3. (c)

A finite set $\mathcal{P}=\\{P_{1},\ldots,P_{s}\\}\subset\mbox{\rm
D}[X_{1},\ldots,X_{k}]$;

  4. (d)

A $\mathcal{P}$-closed formula $\Phi$.

3:

4: An ordered tuple $\mathcal{F}=(\tau_{1},\ldots,\tau_{N})$ of Thom encodings
over $\mathcal{T}$, with associated points $t_{1}<\cdots<t_{N}$, with $-r\leq
t_{1},t_{N}\leq r$, and such that for each $j,1\leq j\leq N-1$, and all
$t\in[t_{j},t_{j+1})$ the inclusion maps
$S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,t_{j}]}\hookrightarrow
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(\infty,t]}$ (resp.
$S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j+1},\infty)}\hookrightarrow
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t,\infty)}$) induce isomorphisms
$\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(\infty,t_{j}]})\rightarrow\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(\infty,t]})$ (resp. $\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j+1},\infty)})\rightarrow\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t,\infty)})$ ), where
$S={\mathcal{R}}(\Phi,\mathrm{R}^{k})\cap\mathrm{clos}(B_{k}(\mathbf{0},r)).$

5:

6:Call [9, Algorithm 6] (up to Step 13 and doing all computations in the ring
$\mbox{\rm D}[\mathrm{ass}(\mathcal{T}$) twice with inputs,
$(-,r,\mathcal{P},\Phi,X_{i+1})$ and $(-,r,\mathcal{P},\Phi,-X_{i+1})$, and
let $\mathcal{F}_{1},\mathcal{F}_{2}$ be the set of Thom encodings over
$\mathcal{T}$ output (Part (a) of the output of [9, Algorithm 6]).

7:Using Algorithm 12.21 (Triangular Comparison of Roots) in [6] order the Thom
encodings in $\mathcal{F}_{1}\cup\mathcal{F}_{2}$, and merge the two sets into
one ordered tuple $\mathcal{F}=(\tau_{1},\ldots,\tau_{N})$ such that
$\mathrm{ass}(\tau_{1})<\cdots<\mathrm{ass}(\tau_{N}).$

8:Output $\mathcal{F}$.

9:The complexity of the algorithm is bounded by  $D^{O(i)}(sd)^{O(k)},$ where
$s=\mathrm{card}(\mathcal{P})$, $d=\max_{P\in\mathcal{P}}\deg(P)$, and
$D=\deg(\mathcal{T})$. Moreover, $\deg(\tau_{i})\leq d^{O(k)}$ for $1\leq
i\leq N$, and the size of $\mathcal{F}$ is bounded by $(sd)^{O(k)}$.

We will need the following extra property of the output of Algorithm 1.

######  Proposition 1.

For each $j,1\leq j\leq N-1$, and all $t\in[t_{j},t_{j+1}]$ the inclusion maps

$S_{\\{\mathrm{ass}(\mathcal{T})\\}\times\\{t\\}}\hookrightarrow
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j}t_{j+1}]}$

induce isomorphisms

$\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times\\{t\\}})\rightarrow\mbox{\rm
H}_{*}(S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j}t_{j+1}]}),$

where

$S={\mathcal{R}}(\Phi,\mathrm{R}^{k})\cap\mathrm{clos}(B_{k}(\mathbf{0},r)).$

###### Proof.

Let

$\displaystyle A_{1}$ $\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,t]},$ $\displaystyle A_{2}$
$\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t,\infty)},$ $\displaystyle B_{1}$
$\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,t_{j+1}]},$ $\displaystyle
B_{2}$ $\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j},\infty)}.$

Then, $A_{h}\subset B_{h},h=1,2$ and

$\displaystyle A_{1}\cap A_{2}$ $\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times\\{t\\}},$ $\displaystyle B_{1}\cap
B_{2}$ $\displaystyle=$ $\displaystyle
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[t_{j}t_{j+1}]},$

and

$A_{1}\cup A_{2}=B_{1}\cup B_{2}=S_{\mathrm{ass}(\mathcal{T})}.$

Moreover the properties of the output of Algorithm 1 imply that that the
homomorphisms $\mbox{\rm H}_{*}(A_{h})\rightarrow\mbox{\rm
H}_{*}(B_{h}),h=1,2$ induced by inclusions are isomorphisms. The Mayer-
Vietoris exact sequence in homology (see for example, [6, Theorem 6.35]) then
yields the following commutative diagram with exact rows and vertical
homomorphisms induced by inclusion (where $A_{12}$ (resp. $B_{12}$) denotes
$A_{1}\cap A_{2}$ (resp. $B_{1}\cap B_{2}$), and $A^{12}$ (resp. $B^{12}$)
denotes $A_{1}\cup A_{2}$ (resp. $B_{1}\cup B_{2}$)):

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
46.23705pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mbox{\rm H}_{m+1}(A_{1})\oplus\mbox{\rm
H}_{m+1}(A_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
70.53044pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
0.0pt\raise-30.63776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
70.53044pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m+1}(A^{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
141.56749pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
93.75557pt\raise-29.5pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
141.56749pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m}(A_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
161.21484pt\raise-30.63776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
205.74239pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
205.74239pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm H}_{m}(A_{1})\oplus\mbox{\rm
H}_{m}(A_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
307.61195pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
244.23708pt\raise-30.63776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
307.61195pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m}(A^{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
327.25931pt\raise-29.5pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mbox{\rm H}_{m+1}(B_{1})\oplus\mbox{\rm
H}_{m+1}(B_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
70.23705pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
70.23705pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m+1}(B^{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
141.2741pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
141.2741pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m}(B_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
205.1556pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
205.1556pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m}(B_{1})\oplus\mbox{\rm
H}_{m}(B_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
307.31856pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
307.31856pt\raise-41.13776pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise 0.0pt\hbox{$\textstyle{\mbox{\rm
H}_{m}(B^{12})}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It follows from the fact that homomorphisms $\mbox{\rm
H}_{*}(A_{h})\rightarrow\mbox{\rm H}_{*}(B_{h}),h=1,2$ induced by inclusions
are isomorphisms, and the fact that $A^{12}=B^{12}$, that all the vertical
arrows other than the middle one are isomorphisms. Hence, by the “Five-lemma”
(see for example [13]) the middle arrow is also an isomorphism, thus proving
the proposition. ∎

We will also need the following algorithm that takes as input a quantifier-
free formula $\Phi$ and outputs $r\in\mbox{\rm D},r>0$, such that
${\mathcal{R}}(\Phi,\mathrm{R}^{k})$ is homologically equivalent to
${\mathcal{R}}(\Phi,\mathrm{R}^{k})\cap\mathrm{clos}(\mbox{\rm
B}(\mathbf{0},r))$.

We need a definition.

######  Notation 8.

For $\mathrm{R}$ a real closed field we denote by
$\mathrm{R}\left\langle{\varepsilon}\right\rangle$ the real closed field of
algebraic Puiseux series in ${\varepsilon}$ with coefficients in $\mathrm{R}$.
As a real closed field $\mathrm{R}{\langle}{\varepsilon}{\rangle}$ is uniquely
ordered, and this order extends the order on $\mathrm{R}$. It is the unique
order in which ${\varepsilon}>0$ and ${\varepsilon}<x$ for every
$x\in\mathrm{R},x>0$. In particular, the subring $\mbox{\rm
D}[{\varepsilon}]\subset\mathrm{R}{\langle}{\varepsilon}{\rangle}$ is ordered
by: $\sum_{i\geq 0}a_{i}{\varepsilon}^{i}>0$ if and only if $a_{p}>0$ where
$p=\min\\{i\;|\;a_{i}\neq 0\\}$.

######  Notation 9.

If $\mathrm{R}^{\prime}$ is a real closed extension of a real closed field
$\mathrm{R}$, and $S\subset\mathrm{R}^{k}$ is a semi-algebraic set defined by
a first-order formula with coefficients in $\mathrm{R}$, then we will denote
by ${\rm ext}(S,\mathrm{R}^{\prime})\subset\mathrm{R}^{\prime k}$ the semi-
algebraic subset of $\mathrm{R}^{\prime k}$ defined by the same formula.
555Not to be confused with the homological functor
$\mathrm{Ext}(\cdot,\cdot)$. It is well-known that ${\rm
ext}(S,\mathrm{R}^{\prime})$ does not depend on the choice of the formula
defining $S$ [6].

######  Notation 10.

For $P=a_{p}T^{p}+\cdots+a_{q}T^{q},p\geq q\in\mbox{\rm D}[T]$,
$a_{p}a_{q}\neq 0$, we denote

$c^{\prime}(P)=\left((p+1)\cdot\sum_{i}\frac{a_{i}^{2}}{a_{q}^{2}}\right)^{-1}.$

We will use the following lemma.

######  Lemma 3.

With the same notation as in Notation 10, if $x\neq 0,x\in\mathrm{R}$ is a
root of $P$, the $|x|>c^{\prime}(P)$.

###### Proof.

See Lemma 10.7 in [6]. ∎

Algorithm 2 (Big enough radius)

1:

2:

  1. (a)

A triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size
$i,0\leq i\leq k$;

  2. (b)

a finite set $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$;

  3. (c)

a $\mathcal{P}$-closed formula $\Phi$ such that
${\mathcal{R}}(\Phi,\mathrm{R}^{k})$ is bounded.

3:

4: Elements $a,b\in\mbox{\rm D}[\mathrm{ass}(\mathcal{T})],a,b>0$, such that
the inclusion map
${\mathcal{R}}(\Phi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})}\cap\mathrm{clos}(\\{\mathrm{ass}(\mathcal{T})\\}\times
B_{k-i}(\mathbf{0},r))\hookrightarrow{\mathcal{R}}(\Phi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})},$
where $r=\frac{a}{b}$, induces an isomorphism  $\mbox{\rm
H}_{*}\left(({\mathcal{R}}(\Phi,\mathrm{R}^{k})\cap\mathrm{clos}(\\{\mathrm{ass}(\mathcal{T})\\}\times
B_{k-i}(\mathbf{0},r)))_{\mathrm{ass}(\mathcal{T})}\right)\rightarrow\mbox{\rm
H}_{*}\left({\mathcal{R}}(\Phi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})}\right).$

5:

6:$P_{1}\leftarrow Y-(X_{i+1}^{2}+\cdots+X_{k}^{2})$.

7:$P_{2}\leftarrow({\varepsilon}^{2}(X_{i+1}^{2}+\cdots+X_{k}^{2})-1)$.

8:$\widetilde{\Phi}\leftarrow\Phi\wedge(P_{1}=0)\wedge(P_{2}\leq 0)$.

9:$\widetilde{\mbox{\rm D}}\leftarrow\mbox{\rm D}[{\varepsilon}]$ where
$D[{\varepsilon}]\subset\mathrm{R}{\langle}{\varepsilon}{\rangle}$ (cf.
Notation 8).

10:Call Algorithm 1 (Morse partition) treating $Y$ as the $(i+1)$-st
coordinate, with computations occurring in the domain $\widetilde{\mbox{\rm
D}}$, and with input
$\mathcal{T},\mathcal{P}\cup\\{P_{1},P_{2}\\},\widetilde{\Phi}$.

11:$\mathcal{Q}\in\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})][{\varepsilon}]\leftarrow$ the set of polynomials
whose signs are determined during the call to Algorithm 1 (Morse partition) in
the previous step.

12:$c=\frac{b}{a}\leftarrow\min_{Q\in\mathcal{Q}}c^{\prime}(Q),a,b\in\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$ (cf. Notation 10).

13:$r\leftarrow\frac{a}{b}$.

14:Output $a,b$.

15:The complexity of the algorithm is bounded by  $D^{O(i)}(sd)^{O(k)},$ where
$s=\mathrm{card}(\mathcal{P})$, $d=\max_{P\in\mathcal{P}}\deg(P)$, and
$D=\deg(\mathcal{T})$.

###### Proof of Correctness of Algorithm 2.

Note that the formula $\widetilde{\Phi}$ defines a semi-algebraic subset

$\widetilde{S}\subset\mathrm{R}{\langle}{\varepsilon}{\rangle}^{i}\times\mathrm{clos}(B_{k-i}(\mathbf{0},\frac{1}{{\varepsilon}})).$

It follows from the conic structure theorem at infinity of semi-algebraic sets
(see for example [6, Proposition 5.49]) and the Tarski-Seidenberg transfer
principle (see for example [6, Theorem 2.80]) that ${\rm
ext}(S,\mathrm{R}{\langle}{\varepsilon}{\rangle})_{\mathrm{ass}(\mathcal{T})}$
is semi-algebraically homeomorphic to
$\widetilde{S}_{\mathrm{ass}(\mathcal{T})}$, and hence

(4.1) $\mbox{\rm H}_{*}\left({\rm
ext}(S,\mathrm{R}{\langle}{\varepsilon}{\rangle})_{\mathrm{ass}(\mathcal{T})}\right)\cong\mbox{\rm
H}_{*}\left(\widetilde{S}_{\mathrm{ass}(\mathcal{T})}\right).$

It follows from the way $r$ is computed in the algorithm in Line 12 and Lemma
3, that $c=\frac{1}{r}$ is strictly positive, and smaller than all strictly
positive roots in $\mathrm{R}$ of the polynomials in $\mathcal{Q}$ (defined in
Line 11 of the algorithm). It now follows from the ordering of the ring
$\mbox{\rm D}[\mathrm{ass}(\mathcal{T})][{\varepsilon}]$ (cf. Notation 8) that
all the branchings in the algorithm, each of which depend on the determination
of the sign of an element in $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})][{\varepsilon}]$, remain the same if $c$ is
substituted for ${\varepsilon}$.

It now follows from the correctness of Algorithm 1 (Morse partition), that the
inclusion

$\widetilde{S}_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,r]}\hookrightarrow\widetilde{S}_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,\frac{1}{{\varepsilon}}]}=\widetilde{S}_{\mathrm{ass}(\mathcal{T})}$

(with $r$ as computed in the algorithm) induces an isomorphism

(4.2) $\mbox{\rm
H}_{*}\left(\widetilde{S}_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,r]}\right)\rightarrow\mbox{\rm
H}_{*}\left(\widetilde{S}_{\mathrm{ass}(\mathcal{T})}\right).$

Moreover, for any $r^{\prime}>0$,
$\widetilde{S}_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,r^{\prime}]}$ is
semi-algebraically homeomorphic to ${\rm
ext}(S,\mathrm{R}{\langle}{\varepsilon}{\rangle})\cap\\{\mathrm{ass}(\mathcal{T})\\}\times\mathrm{clos}(B_{k-i}(\mathbf{0},r^{\prime}))$,
and hence

(4.3) $\mbox{\rm
H}_{*}\left(\widetilde{S}_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,r]}\right)\cong\mbox{\rm
H}_{*}\left({\rm
ext}(S,\mathrm{R}{\langle}{\varepsilon}{\rangle})\cap\\{\mathrm{ass}(\mathcal{T})\\}\times\mathrm{clos}(B_{k-i}(\mathbf{0},r))\right).$

Finally, for any closed semi-algebraic set $X\subset\mathrm{R}^{k}$,

(4.4) $\mbox{\rm H}_{*}(X)\cong\mbox{\rm H}_{*}({\rm
ext}(X,\mathrm{R}{\langle}{\varepsilon}{\rangle})).$

The isomorphisms (4.1), (4.2), (4.3), and (4.4) imply that

$\mbox{\rm H}_{*}\left(S_{\mathrm{ass}(\mathcal{T})}\right)\cong\mbox{\rm
H}_{*}(S\cap\\{\mathrm{ass}(\mathcal{T})\\}\times\mathrm{clos}(B_{k-i}(\mathbf{0},r))).$

This proves the correctness of Algorithm 2. ∎

###### Complexity of Algorithm 2.

The stated complexity follows from the complexity of Algorithm 1 (Morse
partition). ∎

####  4.2.2. Constructing curve segments

Another basic building block of our algorithm is an algorithm that takes as
input a closed formula defining a semi-algebraic set, and produces as output a
set of Thom encodings with associated elements $t_{1}<\cdots<t_{N}$, and over
each open interval $(t_{j},t_{j+1})$, a set of semi-algebraic curves
parametrized by the $X_{1}$ coordinate, with $t_{j}<X_{1}<t_{j+1}$, described
by curve segment representations, and for each $j$, a set of points (described
by real univariate presentations) whose first coordinate equals $t_{j}$, such
that the set of left and right end points of the curves are contained in the
set of points. The main properties that these points and curve segments need
to satisfy are listed in Proposition 2, stated after we describe the
algorithm. Two remarks are in order.

First, note that this construction of curve segments parametrized by one of
the coordinates (in our case $X_{1}$), satisfying properties very similar to
those listed in Proposition 2, is a first step in the classical construction
of roadmaps of semi-algebraic sets [17, 20, 21, 23, 4]. One important extra
property that we require is that the partition of the $X_{1}$-axis satisfies
the property of the output of Algorithm 1 (Morse partition), which is a little
stronger than what is needed for such a partition in the classical roadmap
constructions. We also ensure that distinct curves that we construct do not
intersect (cf. Proposition 2, Part (d)). In the classical roadmap
construction, this extra care is unnecessary.

A second remark is that for reasons explained previously, in the description
of the algorithm we will assume that the first $i$ coordinates are fixed (by a
triangular Thom encoding), and the “first coordinate” in the description given
in the beginning of this subsection should be replaced by the “$(i+1)$-st
coordinate”. This is in fact no different from the case of classical
algorithms for computing roadmaps, which also relies on recursive calls in
which a first block of $i$ coordinates are fixed in each nested recursive with
nesting depth $i$.

Finally, we note that since the main steps of the following algorithm are
quite similar to the corresponding steps in several classical algorithms for
constructing roadmaps, we omit a few details, giving pointers to algorithms in
[6] to be used for implementing them in an efficient way.

Algorithm 3 (Curve segments)

1:

2:

  1. 1.

A triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size $i$
with $0\leq i\leq k-1$;

  2. 2.

a finite set $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$;

  3. 3.

a $\mathcal{P}$-closed formula $\Phi$ such that
${\mathcal{R}}(\Phi,\mathrm{R}^{k})$ is bounded.

3:

4:

  1. 1.

A finite tuple $\mathcal{F}=(\tau_{1},\ldots,\tau_{N})$ of Thom encodings over
$\mathcal{T}$, with

$t_{1}=\mathrm{ass}(\tau_{1})<\cdots<t_{N}=\mathrm{ass}(\tau_{N});$

  2. 2.

for each $j,1\leq j\leq N-1$, an indexing set $I_{j}$, and a finite tuple
$\mathcal{C}_{j}=(\gamma_{h})_{h\in I_{j}}$ of curve segment representations
over $\mathcal{T}$, such that for each $h\in I_{j}$

$\tau_{1}(\gamma_{h})=\tau_{j},\tau_{2}(\gamma_{h})=\tau_{j+1}$

(we will let $C_{0}=\mathcal{C}_{N+1}=\emptyset$);

  3. 3.

for each $j,1\leq j\leq N$ a finite set $\mathcal{U}_{j}$ of real univariate
representations over $\mathcal{T}$, such that for each $u\in U_{j}$, the set
of points $\\{\mathrm{ass}(u)\;|\;u\in\mathcal{U}_{j}\\}$ includes the set of
end-points of the curve segment representations in $C_{j-1}\cup C_{j}$;

  4. 4.

mappings $L_{j},R_{j-1}:I_{j}\rightarrow\mathcal{U}_{j}$, such that
$\mathrm{ass}(L_{j}(h))$ is the left end-point of $\gamma_{h}$, and
$\mathrm{ass}(R_{j}(\gamma_{h}))$ is the right end-point of $\gamma_{h}$.

5:

6:Call Algorithm 2 (Big enough radius) with input
$(\mathcal{T},\mathcal{P},\Phi)$ and compute $a,b\in\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$.

7:$\mathcal{P}\leftarrow\mathcal{P}\cup\\{b^{2}(X_{i+1}^{2}+\cdots+X_{k}^{2})-a^{2}\\}$.

8:$\Phi\leftarrow\Phi\wedge b^{2}(X_{i+1}^{2}+\cdots+X_{k}^{2})-a^{2}\leq 0)$.

9:Call Algorithm 1 (Morse partition) with $(\mathcal{T},r,\mathcal{P},\Phi)$
as input and obtain a finite set $\mathcal{F}$ of Thom encodings over
$\mathcal{T}$ as output.

10:Call Algorithm 16.12 (Bounded Roadmap) in [6] with input $\mathcal{P},\Phi$
and the radius $r$, performing all computations over the ring $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$.

11:Retain from the output of the previous step, the set $\mathcal{C}$ of curve
segment representations over $\mathcal{T}$ parametrized by $X_{i+1}$, and the
set $\mathcal{U}$ of real univariate representations over $\mathcal{T}$.

12:For each pair $\gamma,\gamma^{\prime}\in\mathcal{C}$, compute a description
of $\mathrm{ass}(\gamma)\cap\mathrm{ass}(\gamma^{\prime})$ using Algorithm
14.6 (Parametrized Sign Determination) in [6], and refine the set
$\mathcal{C}$ to have the property that
$\mathrm{ass}(\gamma)\cap\mathrm{ass}(\gamma^{\prime})=\emptyset$, for all
$\gamma,\gamma^{\prime}\in\mathcal{C},\;\gamma\neq\gamma^{\prime}$.

13:Augment the set $\mathcal{U}$ to also contain the set of real univariate
representations over $\mathcal{T}$ whose associated points are the end points
of the curve segments in $\mathcal{C}$.

14:Compute Thom encodings over $\mathcal{T}$ whose associated values are the
$X_{i+1}$-coordinates of the asssociated points of $\mathcal{U}$, and add
these to $\mathcal{F}$.

15:Using Algorithm 12.21 (Triangular Comparison of Roots) in [6] order the
Thom encodings in $\mathcal{F}$, and let the associated values be
$t_{1}=\mathrm{ass}(\tau_{1}),\ldots,t_{N}=\mathrm{ass}(\tau_{N})$.
$\mathcal{F}\leftarrow(\tau_{1},\ldots,\tau_{N}).$

16:Further refine $\mathcal{C}$, such that for each $\gamma\in\mathcal{C}$,
there exists $j,1\leq j<N$, such that
$\tau_{1}(\gamma)=\tau_{j},\tau_{2}(\gamma)=\tau_{2}.$

17:Augment the set $\mathcal{U}$ to include the left and the right end points
of each $\gamma\in\mathcal{C}$.

18:for each $j,1\leq j\leq N-1$ do

19: Let $I_{j}$ denote a set indexing the set of curve segment representations
$\gamma\in\mathcal{C}$, such that
$\tau_{1}(\gamma)=\tau_{j},\tau_{2}(\gamma)=\tau_{j+1}$. For $h\in I_{j}$, we
denote the corresponding curve segment representation in $\mathcal{C}$ by
$\gamma_{h}$.

20: $\mathcal{C}_{j}\leftarrow(\gamma_{h})_{h\in I_{j}}$.

21:
$\mathcal{U}_{j}\leftarrow\\{u\in\mathcal{U}\;|\;\pi_{i+1}(\mathrm{ass}(u))=\mathrm{ass}(\tau_{j})\\}$.

22: Compute the maps
$L_{j}:I_{j}\rightarrow\mathcal{U}_{j},R_{j}:I_{j}\rightarrow\mathcal{U}_{j+1}$,
such that $\mathrm{ass}(L_{j}(h))$ is the left end-point of $\gamma_{h}$, and
$\mathrm{ass}(R_{j}(h))$ is the right endpoint of $\gamma_{h}$.

23:end for

24:Output
$\left(\mathcal{F},(I_{j},\mathcal{C}_{j},\mathcal{U}_{j},L_{j},R_{j})_{j\in[1,N]}\right)$.

25:The complexity of the algorithm is bounded by
$D^{O(i)}(sd)^{O((k-i)^{2})}$, where
$s=\mathrm{card}(\mathcal{P}),d=\max_{P\in\mathcal{P}}\deg(P)$, and
$D=\deg(\mathcal{T})$. The degrees of the curve segment representations in the
various $\mathcal{C}_{j}$, and the degrees of the real univariate
representations in $\mathcal{U}_{j}$ are both bounded by $(D,d^{O(k-i)})$.
Finally the sum of the cardinalities
$\sum_{j=1}^{N}(\mathrm{card}(\mathcal{C}_{j})+\mathrm{card}(\mathcal{U}_{j}))$
is bounded by $(sd)^{O(k-i)}$.

######  Proposition 2.

The output of Algorithm 3 (Curve segments) satisfies the following:

  1. (a)

For each $j,\;1\leq j\leq N-1$, and all
$t\in[\mathrm{ass}(\tau_{j}),\mathrm{ass}(\tau_{j+1}))$ the inclusion maps

$S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,\mathrm{ass}(\tau_{j})]}\hookrightarrow
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times(-\infty,t]},$
$S_{\\{\mathrm{ass}(\mathcal{T})\\}\times\\{t\\}}\hookrightarrow
S_{\\{\mathrm{ass}(\mathcal{T})\\}\times[\mathrm{ass}(\tau_{j}),\mathrm{ass}(\tau_{j+1})},$

are homological equivalences;

  2. (b)

for each $h\in I_{j}$, $\mathrm{ass}(\gamma_{h})\subset
S={\mathcal{R}}(\Phi,\mathrm{R}^{k})$;

  3. (c)

for each $t\in(\mathrm{ass}(\tau_{j}),\mathrm{ass}(\tau_{j+1}))$ and each
semi-algebraically connected component $C$ of $S_{\mathbf{y}}$, where
$\mathbf{y}=(\mathrm{ass}(\mathcal{T}),t)\in\mathrm{R}^{i+1}$, there exists
$h\in I_{j}$ such that $\mathrm{ass}(\gamma_{h})_{\mathbf{y}}\in C$;

  4. (d)

if $h_{1},h_{2}\in I_{j}$ with $h_{1}\neq h_{2}$, then
$\mathrm{ass}(\gamma_{h_{1}})\cap\mathrm{ass}(\gamma_{h_{2}})=\emptyset$.

###### Proof.

Part (a) follows from the property of the output of Algorithm 1 (Morse
partition) called in Line 9 (cf. Proposition 1).

Part (b) and follows from (c) fact that the output of Algorithm 16.26 (General
Roadmap) in [6] which is called in Line 10 describes a road map of the semi-
algebraic set ${\mathcal{R}}(\Phi,\mathrm{R}^{k})$.

Finally, Part (d) is ensured in Line 12. ∎

###### Complexity analysis of Algorithm 3.

The stated complexity follows from the complexity bounds of the various
algorithms used in the algorithm, keeping in mind that each arithmetic
operation in the ring $\mbox{\rm D}[\mathrm{ass}(\mathcal{T})]$ costs
$D^{O(i)}$ arithmetic operations in the ring D. ∎

######  Remark 6.

Note that in the step described in Line 10 it is sufficient to compute curve
segment representations $\gamma$ over $\mathcal{T}$, such that for each
$\mathbf{y}=(\mathrm{ass}(\mathcal{T},t)\in\mathrm{R}^{i+1}$, and each semi-
algebraically connected component $C$ of $S_{\mathbf{y}}$, there is a curve
segment representation $\gamma$, such that
$\mathrm{ass}(\gamma)_{\mathbf{y}}\cap C\neq\emptyset$. Calling Algorithm
16.12 (Bounded Roadmap) in [6] for this purpose is convenient but an overkill.
The recursive calls in constructing a full roadmap leads to the quadratic
dependence in the exponent - however, we do not need the parts of the roadmap
in the various slices, but retain only the curve segments parametrized by
$X_{i+1}$.

One could alternatively achieve the same goal by other algorithms having
smaller complexity (namely, $D^{O(i)}(sd)^{O(k-i)}$ instead of
$D^{O(i)}(sd)^{O((k-i)^{2})}$). For example, it is possible to modify
Algorithm 14.1 (Block Elimination) in [6] using as parameter the coordinate
$X_{i+1}$ for this purpose. Doing so would reduce the total complexity of the
algorithm to $D^{O(i)}(sd)^{O(k-i)}$ instead of $D^{O(i)}(sd)^{O((k-i)^{2})}$
as stated in the complexity bound. However, describing the modifications
needed to Algorithm 14.1 (Block Elimination) in [6] would complicate the
exposition and moreover will not change the asymptotic complexity of Algorithm
4 (Computing one-dimensional subset), which is the only place where Algorithm
3 is used. So we chose not to make this modification.

We are now in a position to describe our algorithm which will complete Step 1
of our proof of Theorem 2.

Algorithm 4 (Computing one-dimensional subset)

1:

2:

  1. 1.

A triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size $i$;

  2. 2.

a finite set $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$;

  3. 3.

a $\mathcal{P}$-closed formula $\Phi$ such that
${\mathcal{R}}(\Phi,\mathrm{R}^{k})$ is bounded;

  4. 4.

a finite set $\mathcal{M}$ of real univariate representations over
$\mathcal{T}$, whose set of associated points, $M$, is contained in
${\mathcal{R}}(\Phi,\mathrm{R}^{k})$.

3:

4:

  1. 1.

a finite set $\mathcal{U}$ of real univariate representations over
$\mathcal{T}$;

  2. 2.

a finite indexing set $I$ and a finite tuple $(\gamma_{j})_{j\in I}$ where
each $\gamma_{j}$ a curve segment representation over $\mathcal{T}$;

  3. 3.

mappings $L,R:I\rightarrow\mathcal{U}$, defined by $\mathrm{ass}(L(j))$ is the
left endpoint of $\gamma_{j}$, and $\mathrm{ass}(R(j))$ is the right endpoint
of $\gamma_{j}$.

5:

6:if $k-i=1$ then

7: for each $u=\\{(f,g_{0},g_{k}),\sigma\\}\in\mathcal{M}$ do

8: Let $R_{u}\in\mathrm{R}[X_{k}]$ be the Sylvester resultant (see for example
[6, pp. 106]) with respect to the variable $T$ of the polynomials
$f,X_{k}g_{0}-g_{k}$.

9: Use Algorithm 10.11 (Sign Determination) [6, pp. 390] to compute a Thom
encoding $\tau_{u}=(R_{u},\sigma_{u})$ over $\mathcal{T}$, such that
$\mathrm{ass}(\tau_{u})=\pi_{k}(\mathrm{ass}(u))$.

10: $\mathcal{P}\leftarrow\mathcal{P}\cup\\{R_{u}\\}$.

11: end for

12: Use Algorithm 12.21 (Triangular Comparison of Roots) in [6, pp. 496]
repeatedly with inputs $\mathcal{T}$ and pairs of polynomials in
$\mathcal{P}$, and order the real roots of the polynomials
$P(\mathrm{ass}(\mathcal{T}),X_{k}),P\in\mathcal{P}$, and hence obtain a
partition of $\mathrm{R}$ into points and open intervals, and identify those
points and open intervals which are contained in
${\mathcal{R}}(\Phi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})}$.

13: $\mathcal{U}\leftarrow\emptyset$.

14: $I\leftarrow\emptyset$.

15: $j\leftarrow 0$.

16: for each Thom encoding $(P,\sigma)$ over $\mathcal{T}$ obtained in Line 9
whose associated point is in $S={\mathcal{R}}(\Phi,\mathrm{R}^{k})$ do

17: $\mathcal{U}\leftarrow\mathcal{U}\cup\\{((P,X_{k},1),\sigma)\\}$.

18: end for

19: for each open interval with end-points described by the Thom encodings
$\tau_{1}=((P_{1},X_{k},1),\sigma_{1}),\tau_{2}=((P_{2},X_{k},1),\sigma_{2})\in\mathcal{U}$
with $\mathrm{ass}(\tau_{1})<\mathrm{ass}(\tau_{2})$ such that
$(\mathrm{ass}(\tau_{1}),\mathrm{ass}(\tau_{2}))\subset\pi_{k}({\mathcal{R}}(\Phi,\mathrm{R}^{k}))$
do

20: $I\leftarrow I\cup\\{j\\}$.

21: $j\leftarrow j+1$.

22: $\gamma_{j}\leftarrow\gamma$, where $\gamma$ is the curve segment
representation over $\mathcal{T}$ defined by:  $\displaystyle\tau_{1}(\gamma)$
$\displaystyle=$ $\displaystyle\tau_{1},$ $\displaystyle\tau_{2}(\gamma)$
$\displaystyle=$ $\displaystyle\tau_{2},$ $\displaystyle u(\gamma)$
$\displaystyle=$ $\displaystyle((T,1),(0,1)).$

23: $L(j)\leftarrow\tau_{1}(\gamma_{j})$.

24: $R(j)\leftarrow\tau_{2}(\gamma_{j})$.

25: end for

26: Output $\mathcal{U},(\gamma_{j})_{j\in I}$, and the mappings
$L,R:I\rightarrow\mathcal{U}$.

27:end if

28: Use Algorithm 3 (Curve segments) with input
$(\mathcal{T},\mathcal{P},\Phi)$ to compute:

  1. (a)

A finite tuple $\mathcal{F}=(\tau_{1},\ldots,\tau_{N})$ of Thom encodings over
$\mathcal{T}$, with $\mathrm{ass}(\tau_{1})<\cdots<\mathrm{ass}(\tau_{N})$;

  2. (b)

for each $j,1\leq j\leq N-1$, a finite tuple $\mathcal{C}_{j}$ of curve
segment representations over $\mathcal{T}$ such that for each
$\gamma\in\mathcal{C}_{j}$,
$\tau_{1}(\gamma)=\tau_{j},\tau_{2}(\gamma)=\tau_{j+1})$;

  3. (c)

for each $j,1\leq j\leq N$ a finite set $\mathcal{U}_{j}$ of real univariate
representations over $\mathcal{T}$, such that for each $u\in\mathcal{U}_{j}$,
the set of points $\\{\mathrm{ass}(u)\;|\;u\in\mathcal{U}_{j}\\}$ is precisely
the set of end-points of the curve segments in
$\mathcal{C}_{j-1}\cup\mathcal{C}_{j}$ (with the convention that
$\mathcal{C}_{0}=\emptyset$);

  4. (d)

mappings $L_{j},R_{j-1}:\mathcal{C}_{j}\rightarrow\mathcal{U}_{j}$, such that
$\mathrm{ass}(L_{j}(\gamma))$ is the left end-point of $\gamma$, and
$\mathrm{ass}(R_{j}(\gamma))$ is the right end-point of $\gamma$.

29:for $\tau=(f,\sigma)\in\mathcal{F}$ do

30:
$\mathcal{M}_{\tau}\leftarrow\\{u\in\mathcal{M}\cup\mathcal{U}\;|\;\pi_{i+1}(\mathrm{ass}(u))=\mathrm{ass}(\tau)\\}$.

31: $\mathcal{T}_{\tau}\leftarrow((F,f),(\bm{\sigma},\sigma)))$.

32: Call Algorithm 4 (Computing one-dimensional subset) recursively with input
($\mathcal{T}_{\tau},\mathcal{P},\Phi,\mathcal{M}_{\tau}$) and obtain a set of
$\mathcal{U}_{\tau}$ of real univariate representations over
$\mathcal{T}_{\tau}$, an indexing set $I_{\tau}$, a tuple $(\gamma_{i})_{i\in
I_{\tau}}$ of curve segment representations, and mappings
$L_{\tau},R_{\tau}:I_{\tau}\rightarrow\mathcal{U}_{\tau}$. (Note that for each
$i\in I_{\tau},\mathrm{ass}(\gamma_{i})\subset S_{\mathrm{ass}(\tau)}$.)

33:end for

34:$I\leftarrow\bigcup_{\tau\in\mathcal{F}}I_{\tau}$.

35:$\mathcal{U}\leftarrow\bigcup_{\tau\in\mathcal{F}}\mathcal{U}_{\tau}$.

36:$L\leftarrow\bigcup_{1\leq j\leq
N}L_{j}\cup\bigcup_{\tau\in\mathcal{F}}L_{\tau}$. (Union of disjoint mappings
means the disjoint union of their graphs.)

37:$R\leftarrow\bigcup_{1\leq j\leq
N}R_{j}\cup\bigcup_{\tau\in\mathcal{F}}R_{\tau}$.

38:Output $\mathcal{U},I,(\gamma_{j})_{j\in I},L,R$.

39:Suppose that $\deg(\mathcal{T})=d^{O(k)}$. The complexity of the algorithm
is bounded by $(sd)^{O(k^{2})}$, where
$s=\mathrm{card}(\mathcal{P}),d=\max_{P\in\mathcal{P}}$. Moreover,
$\mathrm{card}(I)=(sd)^{O((k-i)^{2})}$, and the degrees of the elements of
$\mathcal{U}$ and $\gamma_{j},j\in I$ are bounded by $(d^{O(k)},d^{O(k)})$.

######  Proposition 3.

The output of Algorithm 4 (Computing one-dimensional subset) has the following
properties. Let $\Gamma=\bigcup_{j\in
I}\mathrm{clos}(\mathrm{ass}(\gamma_{j}))$, and
$S={\mathcal{R}}(\Phi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})}$.

  1. (a)

$M\subset\Gamma$;

  2. (b)

$\Gamma\subset S$;

  3. (c)

$\dim(\Gamma)\leq 1$;

  4. (d)

the homomorphism $i_{*,0}:\mbox{\rm H}_{0}(\Gamma)\rightarrow\mbox{\rm
H}_{0}(S)$ induced by the inclusion map $i:\Gamma\hookrightarrow S$ is an
isomorphism;

  5. (e)

the homomorphism $i_{*,1}:\mbox{\rm H}_{1}(\Gamma)\rightarrow\mbox{\rm
H}_{1}(S)$ induced by the inclusion map $i:\Gamma\hookrightarrow S$ is an
epimorphism.

###### Proof.

The property in Part (a) is ensured in Lines 7 and 30. Part (b) follows from
the property of the output of Algorithm 3 (Curve segments) (called in Line 28)
given in Part (b) of Proposition 2.

Part (c) is clear since $\Gamma$ is by definition the finite union

$\bigcup_{j\in I}\mathrm{clos}(\mathrm{ass}(\gamma_{j}))$

and $\dim\mathrm{ass}(\gamma_{j})=1$ for each $j\in I$, and taking the closure
does not increase the dimension of a semi-algebraic set.

It is a standard exercise (see for example proof of Proposition 15.7 in [6])
to prove that the semi-algebraic set $\Gamma$ satisfies the properties of
being roadmap for $S={\mathcal{R}}(\Phi,\mathrm{R}^{k})$ (see [6, Chapter
15]), which implies Part (d).

We now prove Part (e).

The proof is by induction on $k-i$.

Base case: $k-i=1$. In this case the claim is clear since $\mbox{\rm
H}_{1}(\Gamma)=\mbox{\rm H}_{1}(S)=0$.

Suppose the claim is true for all smaller values of $k-i$. Notice that
Algorithm 4 (Computing one-dimensional subset) is called recursively in Line
32. In these calls the triangular Thom encoding
$\mathcal{T}_{\tau},\tau\in\mathcal{F}$ in the input is of size $i+1$, while
the number of variables is still $k$. We have also have,

$\Gamma_{\tau}:=\mathrm{clos}\left(\bigcup_{j\in
I_{\tau}}\mathrm{ass}(\gamma_{j})\right)=\Gamma_{\mathrm{ass}(\tau)}.$

Thus, using the induction hypothesis for this recursive call (since
$k-(i+1)<k-i$), we obtain that the restriction of the inclusion
$\Gamma\rightarrow S$ to $\Gamma_{\tau}$ induces a surjection

(4.5) $\mbox{\rm H}_{1}(\Gamma_{\tau})\rightarrow\mbox{\rm
H}_{1}(S_{\mathrm{ass}(\tau)}).$

Denote for $1\leq j\leq N$, $t_{j}=\pi_{i+1}(\mathrm{ass}(\tau_{j}))$.

$\displaystyle a_{0}$ $\displaystyle=$ $\displaystyle t_{1},$ $\displaystyle
a_{j}$ $\displaystyle=$ $\displaystyle\frac{t_{j}+t_{j+1}}{2},1\leq j<N,$
$\displaystyle a_{N}$ $\displaystyle=$ $\displaystyle t_{N}.$

We prove the following claims.

######  Claim 1.

For each $j,0\leq j\leq N$, the inclusion maps induce the following
isomorphisms.

(4.6) $\displaystyle\mbox{\rm H}_{*}(S_{(-\infty,t_{j}]})\rightarrow\mbox{\rm
H}_{*}(S_{(-\infty,a_{j}]}),$ (4.7) $\displaystyle\mbox{\rm
H}_{*}(S_{t_{j}})\rightarrow\mbox{\rm H}_{*}(S_{[a_{j-1},a_{j}]}),$ (4.8)
$\displaystyle\mbox{\rm H}_{*}(\Gamma_{(-\infty,t_{j}]})\rightarrow\mbox{\rm
H}_{*}(\Gamma_{(-\infty,a_{j}]}),$ (4.9) $\displaystyle\mbox{\rm
H}_{*}(\Gamma_{t_{j}})\rightarrow\mbox{\rm H}_{*}(\Gamma_{[a_{j-1},a_{j}]}).$

###### Proof.

Parts (4.6) and (4.7) are consequences of the property of the output of
Algorithm 3 (Curve segments) (which is called in Line 28) given in Part (a) of
Proposition 2.

Parts (4.8) and (4.9) follow from the fact that there is an easy to define
retraction (along the $X_{i+1}$-coordinate) of $\Gamma_{(-\infty,a_{j}]}$ to
$\Gamma_{(-\infty,t_{j}]}$ (resp. $\Gamma_{[a_{j-1},a_{j}]}$ to
$\Gamma_{t_{j}}$) making use of the fact that distinct curve segments over the
open intervals $(t_{j-1},t_{j})$ do not intersect which is ensured by Part (d)
of Proposition 2. ∎

######  Claim 2.

Let $a,b\in\\{a_{0},\ldots,a_{N}\\}$, with $a\leq b$. The inclusion map
$\Gamma\hookrightarrow S$ induces isomorphisms

$\mbox{\rm H}_{0}(\Gamma_{(-\infty,a]})\rightarrow\mbox{\rm
H}_{0}(S_{(\infty,a]}),$ $\mbox{\rm H}_{0}(\Gamma_{[a,b]})\rightarrow\mbox{\rm
H}_{0}(S_{[a,b]}),$

###### Proof.

This follows from the fact that $\Gamma_{(-\infty,a]}$ (resp.
$\Gamma_{[a,b]}$) satisfy the roadmap property with respect to the set
$S_{(\infty,a]}$ (resp. $S_{[a,b]}$). The proof of this fact is standard and
omitted. ∎

Using the claims proved above, we are now going to prove using induction on
$j$, that the inclusion map $\Gamma\rightarrow S$ induces an isomorphism,

$\mbox{\rm H}_{1}(\Gamma_{(\infty,a_{j}]})\rightarrow\mbox{\rm
H}_{1}(S_{(\infty,a_{j}]}).$

The claim is true for $j=0$ by the global induction hypothesis on $i$, and
hence is also true for $j=1$ using using (4.6) and (4.8).

We prove it for $j>1$ by induction. Suppose the claim holds until $j-1$.

Hence we have isomorphism

$\mbox{\rm H}_{1}(\Gamma_{(\infty,a_{j-1}]})\rightarrow\mbox{\rm
H}_{1}(S_{(\infty,a_{j-1}]})$

induced by inclusion.

Observe that for any set $X\subset\mathrm{R}^{k}$,

$\displaystyle X_{(-\infty,a_{j}]}$ $\displaystyle=$ $\displaystyle
X_{(-\infty,a_{j-1}]}\cup X_{[a_{j-1},a_{j}]},$ $\displaystyle X_{a_{j-1}}$
$\displaystyle=$ $\displaystyle X_{(-\infty,a_{j-1}]}\cap
X_{[a_{j-1},a_{j}]}X_{a_{j-1}}.$

Let

$\displaystyle A_{1}$ $\displaystyle=$
$\displaystyle\Gamma_{(-\infty,a_{j-1}]},$ $\displaystyle A_{2}$
$\displaystyle=$ $\displaystyle\Gamma_{[a_{j-1},a_{j}]},$ $\displaystyle
B_{1}$ $\displaystyle=$ $\displaystyle S_{(-\infty,a_{j-1}]},$ $\displaystyle
B_{2}$ $\displaystyle=$ $\displaystyle S_{[a_{j-1},a_{j}]}.$

Also, let $A_{12}$ (resp. $B_{12}$) denote $A_{1}\cap A_{2}$ (resp. $B_{1}\cap
B_{2}$), and $A^{12}$ (resp. $B^{12}$) denote $A_{1}\cup A_{2}$ (resp.
$B_{1}\cup B_{2}$).

The Mayer-Vietoris exact sequence (see for example [6, Theorem 6.35]) yields
the following commutative diagrams with exact rows and vertical arrows induced
by various restrictions of the inclusion $\Gamma\hookrightarrow S$.

$\textstyle{\mbox{\rm
H}_{1}(A_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\textstyle{\mbox{\rm
H}_{1}(A_{1})\oplus\mbox{\rm
H}_{1}(A_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b_{1}\oplus
b_{2}}$$\textstyle{\mbox{\rm
H}_{1}(A^{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{c}$$\textstyle{\mbox{\rm
H}_{0}(A_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{d}$$\textstyle{\mbox{\rm
H}_{0}(A_{1})\oplus\mbox{\rm
H}_{0}(A_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{e_{1}\oplus
e_{2}}$$\textstyle{\mbox{\rm
H}_{1}(B_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mbox{\rm
H}_{1}(B_{1})\oplus\mbox{\rm
H}_{1}(B_{2})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mbox{\rm
H}_{1}(B^{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mbox{\rm
H}_{0}(B_{12})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mbox{\rm
H}_{0}(B_{1})\oplus\mbox{\rm H}_{0}(B_{2})}$

By induction hypothesis on $j$, the map $b_{1}:\mbox{\rm
H}_{1}(A_{1})\rightarrow\mbox{\rm H}_{1}(B_{1})$ is surjective. Using (4.5),
(4.7), and (4.9) we have that the map $b_{2}:\mbox{\rm
H}_{1}(A_{2})\rightarrow\mbox{\rm H}_{1}(B_{2})$ is surjective. Hence the map
$b=b_{1}\oplus b_{2}$ is surjective.

Using Proposition 2 (c) we have that map $d$ is surjective.

Finally, using Claim 2, we have that the maps $e_{1}$ and $e_{2}$ are both
isomorphisms, and hence so is $e$. In particular, $e$ is injective.

It follows from the above and (one-half of) the “Five-lemma” (see for example
[13]), that $c$ is a surjection. ∎

###### Complexity analysis of Algorithm 4.

It follows from the complexity bounds on the algorithms used that all the
steps before the recursive call in Line 32 has complexity bounded by
$(sd)^{O((k-i)^{2})}$ in terms of the number of arithmetic operations in
$\mbox{\rm D}[\mathrm{ass}(\mathcal{T}]$. Hence,the number of arithmetic
operations in D for these steps is bounded by $d^{O(ki)}(sd)^{O((k-i)^{2})}$.

There are $(sd)^{O(k-i)}$ recursive calls. For each of the recursive calls,
the new triangular Thom encoding is of size $i+1$, and its degree is bounded
again by $d^{O(k)}$. An easy inductive argument now implies the stated
complexity bounds. ∎

###  4.3. Implementing Step 2: proofs of Theorems 2 and 3

We will now prove Theorem 2 by describing an algorithm (cf. Algorithm 7 below)
for computing a semi-algebraic basis of $\mbox{\rm
H}_{1}({\mathcal{R}}(\Phi,\mathrm{R}^{k}))$, for any given closed formula
$\Phi$. Theorem 2 will then follow from the proof of correctness this
algorithm and the analysis of the complexity of the algorithm.

####  4.3.1. Outline of Algorithm 7

Our main tool will be Algorithm 4 (Computing one-dimensional subset) that
produces a one-dimensional subset $\Gamma$ of
$S={\mathcal{R}}(\Phi,\mathrm{R}^{k})$, such that the image of $\mbox{\rm
H}_{1}(\Gamma)$ in $\mbox{\rm H}_{1}(S)$ under the linear map induced by
inclusion is surjective. The semi-algebraic set $\Gamma$ has an underlying
structure of a finite graph $G$, and $\Gamma$ is semi-algebraically
homeomorphic to the geometric realization $|G|$ of $G$. Using a combinatorial
graph-theoretic algorithm it is easy to compute a basis of the cycle space,
$Z(G)\cong\mbox{\rm H}_{1}(\Gamma)$, consisting of simple cycles (say)
$C_{1},\ldots,C_{N}$. Each such simple cycle $C_{i}$ is a subgraph of $G$, and
its geometric realization $|C_{i}|\subset|G|\cong\Gamma$ is semi-algebraically
homeomorphic to $\mbox{${\bf S}$}^{1}$.

We will denote by $[C_{i}]$ a non-zero element of the image of $\mbox{\rm
H}_{1}(|C_{i}|)$ in $\mbox{\rm H}_{1}(S)$ if this image is non-zero (and let
$[C_{i}]=0$ otherwise). However, the set $\\{[C_{1}],\ldots,[C_{N}]\\}$ need
not be linearly independent but thanks to the surjectivity of the map
$\mbox{\rm H}_{1}(\Gamma)\rightarrow\mbox{\rm H}_{1}(S)$, they span $\mbox{\rm
H}_{1}(S)$. We identify a minimal subset of $\\{[C_{1}],\ldots,[C_{N}]\\}$
which spans $\mbox{\rm H}_{1}(S)$ (i.e. form a basis of $\mbox{\rm
H}_{1}(S)$). The corresponding subsets of $\Gamma$ then constitutes a semi-
algebraic basis of $\mbox{\rm H}_{1}(S)$. In order to achieve this last step
effectively and with singly exponential complexity, we use a recent result
proved in [9], giving an algorithm (see Algorithm 6 below for input, output
and complexity) with singly exponential complexity for replacing a tuple of
given closed and bounded semi-algebraic subsets of $\mathrm{R}^{k}$, by a
simplicial complex which is homologically $1$-equivalent to the given tuple of
sets (cf. Definition 11). This simplicial complex is of singly exponential
bounded size, and the various $|C_{i}|$’s can be identified with subcomplexes
of this complex. So to find a basis from amongst the elements
$[C_{1}],\ldots,[C_{N}]$ becomes a problem of ordinary linear algebra which
can be solved with polynomial complexity.

####  4.3.2. Conversion of curve segment representations to closed formulas

We will need the following algorithm. It is needed in order to address the
following technical issue.

The output of Algorithm 4 (Computing one-dimensional subset) contains amongst
other objects, a set of curve segment representations. We will need to convert
these descriptions into _closed formulas_ describing the closure of the
associated curves in order to use Algorithm 6 which only accepts such
descriptions in the input.

Note that the algorithmic problem of computing a _closed_ formula describing
the closure of a given semi-algebraic set described by a quantifier-free (but
not necessarily closed-) formula is far from being easy, and no algorithm with
singly exponential complexity is known for solving this problem in general.
666Note that without the requirement that the output formula be closed it is
straight-forward to obtain a singly exponential complexity algorithm via
quantifier elimination. (A doubly exponential algorithm is known, using the
notion of a stratifying family [6, Chapter 5]). However, fortunately for us
the curve segment representations describing the associated curve have a
special structure. In particular, it is clear that given a curve segment
representation $\gamma$, it is algorithmically quite simple to obtain a
description of the the image, $\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))$, of the
projection of $\mathrm{ass}(\gamma)$, to each of the coordinate subspaces
spanned by $(X_{1},X_{j}),2\leq j\leq k$. More precisely, suppose that
$\gamma$ is the curve segment representation with

$u(\gamma)=((f,g_{0},\ldots,g_{k}),\sigma),$

where $f,g_{i}\in\mbox{\rm D}[X_{1},T]$, and $\sigma\in\\{0,1,-1\\}^{{\rm
Der}_{T}(f)}$. Then, $\mathrm{ass}(\gamma)$ is defined by

$\mathrm{ass}(\gamma)=\left\\{\left(x_{1},\frac{g_{2}(x_{1},t(x_{1}))}{g_{0}(x_{1},t(x_{1}))},\ldots,\frac{g_{k}(x_{1},t(x_{1}))}{g_{0}(x_{1},t(x_{1}))}\right)\;\middle|\;\mathrm{ass}(\tau_{1}(\gamma))<x_{1}<\mathrm{ass}(\tau_{2}(\gamma))\right\\},$

where for each
$x_{1},\mathrm{ass}(\tau_{1}(\gamma))<x_{1}<\mathrm{ass}(\tau_{2}(\gamma))$,
and $t(x_{1})$ is a root of $f(x_{1},T)$ with Thom encoding $\sigma$.

Now for each $j,2\leq j\leq k$, the projection of $\mathrm{ass}(\gamma)$ to
the $(X_{1},X_{j})$-plane is described by

$\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))=\left\\{\left(x_{1},\frac{g_{j}(x_{1},t(x_{1}))}{g_{0}(x_{1},t(x_{1}))}\right)\;\middle|\;\mathrm{ass}(\tau_{1}(\gamma))<x_{1}<\mathrm{ass}(\tau_{2}(\gamma))\right\\}.$

Using an effective quantifier elimination (eliminating $T$), one can obtain
from the above description a quantifier-free formula with free variables
$X_{1},X_{j}$ whose realization is equal to
$\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))$.

We will use the following claim.

######  Claim 3.

Suppose that $\gamma$ is a curve segment representation and
$\mathrm{ass}(\gamma)$ is bounded, then

$\mathrm{clos}(\mathrm{ass}(\gamma))=\bigcap_{2\leq j\leq
k}\pi^{-1}_{\\{1,j\\}}(\mathrm{clos}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma)))).$

###### Proof of Claim 3.

First, suppose that $\mathbf{x}\in\mathrm{clos}(\mathrm{ass}(\gamma))$. Then
we have that

$\mathbf{x}\in\pi^{-1}_{\\{1,j\\}}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma)))$

for all $j$. It is a general fact from topology that for any continuous
function $f$ and set $A$, $f(\mathrm{clos}(A))\subset\mathrm{clos}(f(A))$.
Hence,

$\pi^{-1}_{\\{1,j\\}}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma)))\subset\pi^{-1}_{\\{1,j\\}}(\mathrm{clos}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))))$

for all $j$. Therefore $\mathbf{x}\in\bigcap_{2\leq j\leq
k}\pi^{-1}_{\\{1,j\\}}(\mathrm{clos}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))))$.

Now, suppose that

$\mathbf{x}=(x_{1},\ldots,x_{k})\in\bigcap_{2\leq j\leq
k}\pi^{-1}_{\\{1,j\\}}(\mathrm{clos}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))))$

and let $\mathbf{x}_{1,j}=\pi_{\\{1,j\\}}(\mathbf{x})$ for $j=2,\ldots,k$.

Since,
$\mathbf{x}_{1,j}\in\mathrm{clos}(\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma)))$,
using the semi-algebraic curve selection lemma (see for example [6, Theorem
3.19]) there exists $t_{j,0}>0$, such that there exists a semi-algebraic
curve, $\gamma_{j}=(\gamma_{1,j},\gamma_{2,j}):[0,t_{j,0}]:\mathrm{R}^{2}$,
such that $\gamma_{1,j},\gamma_{2,s}$ are continuous semi-algebraic functions,
$\gamma_{j}(0)=\mathbf{x}_{1,j}$, and
$\gamma((0,t_{j,0}])\subset\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))$. Moreover,
clearly since $\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))$ is a curve parametrized
by the $X_{1}$ coordinate, $\gamma_{1,j}$ is not a constant function, and
without loss of generality (choosing $t_{j,0}$ smaller if necessary) we can
assume that $\gamma_{1,j}$ is a strictly increasing function. For
$j=2,\ldots,k$, let $f_{j}:[x_{1},\gamma_{1,j}(t_{j,0})]\rightarrow\mathrm{R}$
be defined by

$f_{j}(X_{1})=\gamma_{2,j}(\gamma_{1,j}^{-1}(X_{1})).$

Taking $x_{1}^{\prime}=\min_{2\leq j\leq k}\gamma_{1,j}(t_{j,0})$, we obtain a
semi-algebraic curve
$\widetilde{\gamma}:[x_{1},x_{1}^{\prime}]\rightarrow\mathrm{ass}(\gamma)$,
defined by

$\widetilde{\gamma}(X_{1})=(X_{1},f_{2}(X_{1}),\ldots,f_{k}(X_{1})).$

It is easy to check that

$\widetilde{\gamma}(x_{1})=\mathbf{x},$

and

$\widetilde{\gamma}:(x_{1},x_{1}^{\prime}]\subset\mathrm{ass}(\gamma),$

which proves that $\mathbf{x}\in\mathrm{clos}(\mathrm{ass}(\gamma))$. ∎

Using Claim 3 we reduce the problem of computing a closed description of
$\mathrm{clos}(\mathrm{ass}(\gamma))$ to the problem of computing the closures
of $\pi_{\\{1,j\\}}(\mathrm{ass}(\gamma))$, $2\leq j\leq k$, and each of the
latter is a $2$-dimensional problems which can be solved within our allowed
complexity bound using the doubly exponential algorithm referred to
previously.

Finally, as in the case of the other algorithms in this paper we include in
the input a triangular Thom encoding $\mathcal{T}$ that fixes the first
$i$-coordinates, and the curve segment representations in the input is over
$\mathcal{T}$. The computations in the algorithm takes place in the ring
$\mbox{\rm D}[\mathrm{ass}(\mathcal{T})]$, and in the description given above,
the first coordinate is replaced by the $(i+1)$-st coordinate.

Algorithm 5 (Conversion of curve segment representations to closed formulas)

1:

2:

  1. 1.

A triangular Thom encoding $\mathcal{T}=(\mathbf{F},\bm{\sigma})$ of size
$i,0\leq i\leq k$;

  2. 2.

a curve segment representation $\gamma$ over $\mathcal{T}$.

3:

4:

  1. 1.

A finite set of polynomials $\mathcal{Q}\subset\mbox{\rm
D}[\mathrm{ass}(\mathcal{T}][X_{i+1},\ldots,X_{k}]$;

  2. 2.

A $\mathcal{Q}$-closed formula $\Psi$ such that

${\mathcal{R}}(\Psi,\mathrm{R}^{k})_{\mathrm{ass}(\mathcal{T})}=\mathrm{clos}(\mathrm{ass}(\gamma)).$

5:

6:$u\leftarrow u(\gamma)=((f,g_{0},g_{i+2},\ldots,g_{k}),\sigma)$.

7:for $j=i+2,\ldots,k$ do

8: Using Algorithm 14.5 (Quantifier Elimination) in [6, pp. 549] with the
formula  $(\exists T)(f=0)\wedge\bigwedge_{1\leq h\leq\deg_{T}(f)}(\mbox{\bf
sign}(f^{(h)})=\sigma(f^{(h)}))\wedge(X_{j}g_{0}-g_{j}=0),$ as input, and
obtain a $\widetilde{\mathcal{Q}}_{j}$-formula quantifier-free formula
$\widetilde{\phi}_{j}$, for some $\widetilde{\mathcal{Q}}_{j}\subset\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})][X_{i+1},X_{j}]$ describing such that
${\mathcal{R}}(\widetilde{\phi}_{j})=\pi_{[1,i+1]\cup\\{j\\}}(\mathrm{ass}(\gamma))$.

9: Compute a stratifying family of polynomials (see [6, Proposition 5.40] for
definition), $\mathcal{Q}_{j}\subset\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})][X_{i+1},X_{j}]$ containing
$\widetilde{\mathcal{Q}}_{j}$.

10: Using Algorithm 13.1 (Computing realizable sign conditions) in [6, pp.
511] determine the set $\Sigma_{j}\subset\\{0,1,-1\\}^{\mathcal{Q}_{j}}$ of
realizable sign conditions of $\mathcal{Q}_{j}$.

11: Determine $\Theta_{j}\subset\Sigma_{j}$ such that
$\pi_{[1,i+1]\cup\\{j\\}}(\mathrm{ass}(\gamma))=\bigcup_{\theta\in\Theta_{j}}{\mathcal{R}}(\theta)$.

12: $\Psi_{j}\leftarrow\bigvee_{\theta\in\Theta_{j}}\overline{\theta}$.

13:end for

14:$\mathcal{Q}\leftarrow\mathbf{F}\cup\bigcup_{i+2\leq j\leq
k}\mathcal{Q}_{j}$.

15:$\Psi\leftarrow\overline{\bm{\sigma}}\wedge\bigwedge_{i+2\leq j\leq
k}\Psi_{j}$ (see Notation 7 for definition of $\overline{\bm{\sigma}}$).

16:Output $\mathcal{Q},\Psi$.

17:The complexity of the algorithm is bounded by
$(k-i)D_{1}^{O(i)}D_{2}^{O(1)}$, where $D_{1}=\deg(\mathcal{T})$, and
$D_{2}=\deg(\gamma)$. Moreover, $\mathrm{card}(\mathcal{Q})$ is bounded by
$i+(k-i)D_{2}^{O(1)}$, and the degrees of the polynomials in $\mathcal{Q}$ are
bounded by $\max(D_{1},D_{2}^{O(1)})$.

###### Proof of Correctness of Algorithm 5.

The algorithm reduces the problem to obtaining closed formulas describing the
closures of the various $\pi_{i+1,j}(\mathrm{ass}(\gamma)),i+2\leq j\leq k$
(cf. Line 7). After obtaining the descriptions of the various
$\pi_{i+1,j}(\mathrm{ass}(\gamma))$ using effective quantifier elimination
algorithm (Algorithm 14.5 (Quantifier Elimination) in [6, pp. 549] called in
Line 8), closed formulas are obtained describing the closure by computing a
stratifying family (cf. 9) in each case. The important property of the
stratifying families $\mathcal{Q}_{j}$ is that the closures,
$\mathrm{clos}(\pi_{i+1,j}(\mathrm{ass}(\gamma)))$ are unions of realizations
of a set of weak sign conditions on $\mathcal{Q}_{j}$. This is a consequence
of the generalized Thom’s Lemma (see [6, Proposition 5.39]). Finally, the set
of weak sign conditions on $\mathcal{Q}_{j}$ whose realizations are contained
in $\mathrm{clos}(\pi_{i+1,j}(\mathrm{ass}(\gamma)))$ computed using Algorithm
13.1 (Computing realizable sign conditions) in [6, pp. 511] in Line 10. The
disjunction of these weak formulas gives a closed formula, $\Psi_{j}$
describing $\mathrm{clos}(\pi_{i+1,j}(\mathrm{ass}(\gamma)))$ (cf. Line 12).
Now Claim 3 together with Lemma 2 (and noting that the conjunction of a finite
set of closed formulas is also closed), imply that the conjunction, $\Psi$, of
the formulas $\Psi_{j},j=i+2,\ldots,k$ along with the closed formula
$\overline{\bm{\sigma}}$ (Notation 7), describes
$\mathrm{clos}(\mathrm{ass}(\gamma))$ (cf. Line 15). This proves the
correctness of the algorithm. ∎

###### Complexity analysis of Algorithm 5.

As before, each arithmetic operation in $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$ costs $D_{1}^{O(i)}$ arithmetic operations in D
(where $D_{1}=\deg(\mathcal{T})$). There are $(k-i)$ two dimensional
projections (cf. Line 7). The complexity of each of these two-dimensional sub-
problems (measured in terms of number of operations in $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$) is bounded by $D_{2}^{O(1)}$, where
$D_{2}=\deg(\gamma)$, and this follows from the complexity bounds on the
various algorithms used in the different steps (namely, Algorithm 14.5
(Quantifier Elimination) in [6, pp. 549] in Line 8, algorithm for computing
stratifying families in 9, and Algorithm 13.1 (Computing realizable sign
conditions) in [6, pp. 511] in Line 10). Note that these algorithms are used
with the number of variables equal to $2$, and hence the complexity of each
call (measured in terms of arithmetic operations in $\mbox{\rm
D}[\mathrm{ass}(\mathcal{T})]$) are polynomially bounded in $D_{1}$. This
completes the complexity analysis of Algorithm 3. ∎

####  4.3.3. Efficient algorithm for computing a simplicial replacement

As explained in the outline above, in order to obtain a semi-algebraic basis
we will use an algorithm described in [9]. We reproduce below for the reader’s
benefit the input, output and complexity of this algorithm. But before stating
these we need some preliminary definitions.

######  Definition 8 (Homological $\ell$-equivalence).

We say that a map $f:X\rightarrow Y$ between two topological spaces is a
_homological $\ell$-equivalence_ if the induced homomorphisms between the
homology groups $f_{*}:\mbox{\rm H}_{i}(X)\rightarrow\mbox{\rm H}_{i}(Y)$ are
isomorphisms for $0\leq i\leq\ell$.

The relation of homological $\ell$-equivalence as defined above is not an
equivalence relation since it is not symmetric. In order to make it symmetric
one needs to “formally invert” $\ell$-equivalences.

######  Definition 9 (Homologically $\ell$-equivalent).

We will say that _$X$ is homologically $\ell$-equivalent to $Y$_ (denoted
$X\sim_{\ell}Y$), if and only if there exists spaces,
$X=X_{0},X_{1},\ldots,X_{n}=Y$ and homological $\ell$-equivalences
$f_{1},\ldots,f_{n}$ as shown below:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
8.93471pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 32.93471pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.17047pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
8.93472pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
62.3878pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
74.80412pt\raise-30.6848pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
80.73883pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 116.67354pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
92.9093pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
92.67355pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
145.34354pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{4}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
158.54295pt\raise-32.37524pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
158.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
233.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{X_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
208.64914pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n-1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
209.54295pt\raise-32.77734pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
266.66278pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
280.64037pt\raise-30.98157pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
286.85573pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-8.93471pt\raise-39.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{0}}$}}}}}}}{\hbox{\kern
38.86942pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
74.80412pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{2}}$}}}}}}}{\hbox{\kern
122.60825pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
158.54295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
242.09166pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
280.64037pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{n}}$}}}}}}}{\hbox{\kern
323.07109pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It is clear that $\sim_{\ell}$ is an equivalence relation.

######  Definition 10 (Diagrams of topological spaces).

A _diagram of topological spaces_ is a functor, $X:J\rightarrow\mathbf{Top}$,
from a small category $J$ to $\mathbf{Top}$.

We extend Definition 8 to diagrams of topological spaces. We denote by
$\mathbf{Top}$ the category of topological spaces.

######  Definition 11 (Homological $\ell$-equivalence between diagrams of
topological spaces).

Let $J$ be a small category, and $X,Y:J\rightarrow\mathbf{Top}$ be two
functors.

We will say that _a diagram $X:J\rightarrow\mathbf{Top}$ is homologically
$\ell$-equivalent to the diagram $Y:J\rightarrow\mathbf{Top}$_ (denoted as
before by $X\sim_{\ell}Y$), if and only if there exists diagrams
$X=X_{0},X_{1},\ldots,X_{n}=Y:J\rightarrow\mathbf{Top}$ and homological
$\ell$-equivalences $f_{1},\ldots,f_{n}$ as shown below:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
8.93471pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 32.93471pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.17047pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
8.93472pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
62.3878pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
74.80412pt\raise-30.6848pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
80.73883pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 116.67354pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
92.9093pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
92.67355pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
145.34354pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{4}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
158.54295pt\raise-32.37524pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
158.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
233.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{X_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
208.64914pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n-1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
209.54295pt\raise-32.77734pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
266.66278pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
280.64037pt\raise-30.98157pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
286.85573pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-8.93471pt\raise-39.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{0}}$}}}}}}}{\hbox{\kern
38.86942pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
74.80412pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{2}}$}}}}}}}{\hbox{\kern
122.60825pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
158.54295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
242.09166pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
280.64037pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{n}}$}}}}}}}{\hbox{\kern
323.07109pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It is clear that $\sim_{\ell}$ is an equivalence relation.

######  Notation 11 (Diagram of various unions of a finite number of
subspaces).

Let $J$ be a finite set, $A$ a topological space, and
$\mathcal{A}=(A_{j})_{j\in J}$ a tuple of subspaces of $A$ indexed by $J$.

For any subset $J^{\prime}\subset J$, we denote

$\displaystyle\mathcal{A}^{J^{\prime}}$ $\displaystyle=$
$\displaystyle\bigcup_{j^{\prime}\in J^{\prime}}A_{j^{\prime}}.$

We consider $2^{J}$ as a category whose objects are elements of $2^{J}$, and
whose only morphisms are given by:

$\displaystyle 2^{J}(J^{\prime},J^{\prime\prime})$ $\displaystyle=$
$\displaystyle\emptyset\mbox{ if }J^{\prime}\not\subset J^{\prime\prime},$
$\displaystyle 2^{J}(J^{\prime},J^{\prime\prime})$ $\displaystyle=$
$\displaystyle\\{\iota_{J^{\prime},J^{\prime\prime}}\\}\mbox{ if
}J^{\prime}\subset J^{\prime\prime}.$

We denote by $\mathbf{Simp}^{J}(\mathcal{A}):2^{J}\rightarrow\mathbf{Top}$ the
functor (or the diagram) defined by

$\mathbf{Simp}^{J}(\mathcal{A})(J^{\prime})=\mathcal{A}^{J^{\prime}},J^{\prime}\in
2^{J},$

and $\mathbf{Simp}^{J}(\mathcal{A})(\iota_{J^{\prime},J^{\prime\prime}})$ is
the inclusion map
$\mathcal{A}^{J^{\prime}}\hookrightarrow\mathcal{A}^{J^{\prime\prime}}$.

######  Notation 12.

For $N\in\mathbb{Z}$ we denote by $[n]=\\{0,\ldots,N\\}$. In particular,
$[-1]=\emptyset$.

Armed with the definition of homological equivalence of diagrams as defined
above we are finally in a position to state the specifications of the
simplicial replacement algorithm described in [9].

Algorithm 6 (Simplicial replacement)

1:

2:

  1. 1.

A finite set of polynomials $\mathcal{P}\subset\mbox{\rm
D}[X_{1},\ldots,X_{k}]$;

  2. 2.

an integer $N\geq 0$, and for each $i\in[N]$, a $\mathcal{P}$-closed formula
$\phi_{i}$;

  3. 3.

$\ell,0\leq\ell\leq k$.

3:

4: A simplicial complex $\Delta$ and for each $I\subset[N]$ a subcomplex
$\Delta_{I}\subset\Delta$ such that there is a diagrammatic homological
$\ell$-equivalence
$(I\mapsto\Delta_{I})_{I\subset[N]}\overset{h}{\sim}_{\ell}\mathbf{Simp}^{[N]}({\mathcal{R}}(\Phi)),$
where $\Phi(i)=\phi_{i},i\in[N]$.

5:The complexity of the algorithm is bounded by $(sd)^{k^{O(\ell)}}$, where
$s=\mathrm{card}(\mathcal{P})$ and $d=\max_{P\in\mathcal{P}}\deg(P)$.

######  Notation 13.

A finite (directed) graph $G$ is a tuple
$(V(G),E(G),\mathrm{head},\mathrm{tail})$, where $V(G),E(G)$ are finite sets
and $\mathrm{head},\mathrm{tail}:E(G)\rightarrow V(G)$ are maps. To every
finite graph $G$ there is an one-dimensional regular cell complex associated
naturally to it. We will denote this cell complex by $|G|$.

####  4.3.4. Algorithm for computing basis of $\mbox{\rm H}_{1}(S)$

We are now in a position to describe the algorithm that will accomplish Step 2
of our algorithm for computing a semi-algebraic basis of the first homology of
a given closed semi-algebraic set.

The outline of the algorithm is as follows. We first replace the given closed
semi-algebraic set by one that is closed and bounded and which is
homologically equivalent to the given set. This is accomplished in Lines 6, 7
and 8 using Algorithm 2 (Big enough radius). We then use Algorithm 4
(Computing one-dimensional subset) to compute a one-dimensional subset
$\Gamma$ (described in terms of curve-segment representations and real
univariate representations) having the property that $\mbox{\rm
H}_{q}(S,\Gamma)=0$ for $q=0,1$, where $S$ is the given semi-algebraic set.
This is accomplished in Line 9. We then use Algorithm 5 (Conversion of curve
segment representations to closed formulas) in Line 10 to convert the
description of $\Gamma$ obtained in the last step into a formula. In Line 13,
we extract the underlying structure of a combinatorial graph $G$ from $\Gamma$
and compute a set of simple cycles which spans the cycle space of $G$. Finally
in Line 18, we use Algorithm 6 (Simplicial replacement) and Gauss-Jordan
elimination to compute a minimal subset of the simple cycles computed in the
previous step which span $\mbox{\rm H}_{1}(S)$, and these form a semi-
algebraic basis of $\mbox{\rm H}_{1}(S)$.

Algorithm 7 (Computing homology basis)

1:

2:

  1. 1.

a finite set $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$;

  2. 2.

a $\mathcal{P}$-closed formula $\Phi$.

3:

4:

  1. 1.

a finite set $\mathcal{Q}\subset\mbox{\rm D}[X_{1},\ldots,X_{k}]$;

  2. 2.

a finite tuple $(\Psi_{j})_{j\in J}$, in which each $\Psi_{j}$ is a
$\mathcal{Q}$-formula, such that the realizations
$\Gamma_{j}={\mathcal{R}}(\Psi_{j},\mathrm{R}^{k})$ have the following
properties:

    1. (a)

For each $j\in J$, $\Gamma_{j}\subset S$ and $\Gamma_{j}$ is semi-
algebraically homeomorphic to $\mbox{${\bf S}$}^{1}$;

    2. (b)

the inclusion map $\Gamma_{j}\hookrightarrow S$ induces an injective map
$\mathbb{F}\cong\mbox{\rm H}_{1}(\Gamma_{j})\rightarrow\mbox{\rm H}_{1}(S)$,
whose image we denote by $[\Gamma_{j}]$;

    3. (c)

the tuple $([\Gamma_{j}])_{j\in J}$ forms a basis of $\mbox{\rm H}_{1}(S)$.

5:

6:Use Algorithm 2 (Big enough radius) with input $(\mathcal{P},\Phi)$ and let
$r=\frac{a}{b}>0,a,b\in\mbox{\rm D}$ be the output.

7:$\mathcal{P}\leftarrow\mathcal{P}\cup\\{b^{2}(X_{1}^{2}+\cdots+X_{k}^{2})-a^{2}\\}$.

8:$\Phi\leftarrow\Phi\wedge(b^{2}(X_{1}^{2}+\cdots+X_{k}^{2})-a^{2}\leq 0)$.

9:Call Algorithm 4 (Computing one-dimensional subset) with input
$(\mathcal{P},\Phi)$ to obtain

  1. (a)

a finite set $\mathcal{U}$ of real univariate representations over
$\mathcal{T}$;

  2. (b)

a finite indexing set $I$ and a finite tuple $(\gamma_{j})_{j\in I}$ where
each $\gamma_{j}$ a curve segment representation over $\mathcal{T}$;

  3. (c)

mappings $L,R:I\rightarrow\mathcal{U}$, defined by $\mathrm{ass}(L(j))$ is the
left endpoint of $\gamma_{j}$, and $\mathrm{ass}(R(j))$ is the right endpoint
of $\gamma_{j}$.

10:Using Algorithm 5 (Conversion of curve segment representations to closed
formulas) compute for each $j\in I$ a set of polynomials $\mathcal{Q}_{j}$ and
a $\mathcal{Q}_{j}$-closed formula $\Theta_{j}$ such that
${\mathcal{R}}(\Theta_{j})=\mathrm{clos}(\mathrm{ass}(\gamma_{j}))$.

11:$\mathcal{Q}\leftarrow\bigcup_{j\in I}\mathcal{Q}_{j}$.

12:$G\leftarrow(E=I,V=\mathcal{U},\mathrm{head}=L,\mathrm{tail}=R)$.

13:Using a graph traversal algorithm compute a tuple $(C_{1},\ldots,C_{N})$
where each $C_{h}=(i_{h,0},\ldots,i_{h,q_{h}-1})\in I^{q_{h}}$ and

  1. (a)