Efficient simplicial replacement of semi-algebraic sets

Abstract

We prove that for any $\ell \ge 0$, there exists an algorithm which takes as input a description of a semi-algebraic subset $S\subset {\mathbb{R}}^k$ given by a quantifier-free first order formula $\varphi$ 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 $\varphi$, 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 )}}$.

55 pages, 8 figures. The previous version has been split into two parts. The second part titled "Persistent homology of semi-algebraic sets" now appears as a separate paper. The title has been shortened to reflect this change. Several proofs have been expanded. More explanations and figures have been added. Comments welcome