Search for: All records

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 toS. 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 toS. The complexity of our algorithm is bounded by$(sd)^{k^{O(\ell )}}$, wheresis the number of polynomials appearing in the formula$\phi $, andda bound on their degrees. For fixed$\ell $, this bound issingly exponentialink. In particular, since$\ell $-equivalence implies that thehomotopy groupsup to dimension$\ell $of$|\Delta |$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$\ell $homotopy groups ofSto the combinatorial problem of computing the first$\ell $homotopy groups of a finite simplicial complex of size bounded by$(sd)^{k^{O(\ell )}}$.