Efficient simplicial replacement of semialgebraic sets

Saugata Basu ; Negin Karisani

Forum of Mathematics, Sigma, Tome 11 (2023)

Résumé

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 )}}$.

Détail

DOI : 10.1017/fms.2023.36