In recent years, there has been a strong effort in computational real algebraic geometry to provide algorithms (and corresponding complexity estimates) for determining the geometric and topological properties of semialgebraic sets, namely, those sets in Rn defined by a finite number of polynomial equations and inequalities. These properties include the number of connected components, and their explicit descriptions as semialgebraic sets, roadmaps, Betti numbers, and so on.
This paper shows how the restriction to quadratic inequalities, when defining the considered semialgebraic set, is very helpful for obtaining more efficient algorithms for computing its Euler-Poincaré characteristic. More precisely, it introduces a new algorithm for computing the Euler-Poincaré characteristic of a semialgebraic set, defined by l quadratic inequalities in k variables whose complexity is kO(l). This algorithm improves the previous best complexity bound for this problem, given by an algorithm relying on the computation of all the Betti numbers of the considered semialgebraic set (being the complexity of such an algorithm k2O(l). The main tools used are spectral sequences (for topological considerations) and quantifier elimination techniques coming from real algebraic geometry (for computing with sign conditions on polynomials).
This paper is particularly relevant for two reasons. First, it shows that a better algorithm can be obtained for computing the Euler-Poincaré characteristic of a semialgebraic set without previously determining their Betti numbers, and using the usual formula. Second, it shows that the consideration of restricted families of semialgebraic sets is very helpful for deriving new algorithms, and is particularly efficient with respect to their complexity estimates.
