Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set
$S \subset \mathbb {R}^k$
by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex
$\Delta $
, whose geometric realization,
$|\Delta |$
, is semialgebraically homeomorphic to S. In this paper, we consider a weaker version of this question. We prove that for any
$\ell \geq 0$
, there exists an algorithm which takes as input a description of a semialgebraic subset
$S \subset \mathbb {R}^k$
given by a quantifier-free first-order formula
$\phi $
in the language of the reals and produces as output a simplicial complex
$\Delta $
, whose geometric realization,
$|\Delta |$
is
$\ell $
-equivalent to S. The complexity of our algorithm is bounded by
$(sd)^{k^{O(\ell )}}$
, where s is the number of polynomials appearing in the formula
$\phi $
, and d a bound on their degrees. For fixed
$\ell $
, this bound is singly exponential in k. In particular, since
$\ell $
-equivalence implies that the homotopy groups up to dimension
$\ell $
of
$|\Delta |$
are isomorphic to those of S, we obtain a reduction (having singly exponential complexity) of the problem of computing the first
$\ell $
homotopy groups of S to the combinatorial problem of computing the first
$\ell $
homotopy groups of a finite simplicial complex of size bounded by
$(sd)^{k^{O(\ell )}}$
.