Basu, Saugata Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities. (English) Zbl 1103.14032 Comput. Complexity 15, No. 3, 236-251 (2006). Summary: Let \(R\) be a real closed field. We present an algorithm which takes as input a closed semi-algebraic set, \(S \subset R^k\), defined by \(P_1 \leq 0, \ldots P_\ell \leq 0, \quad P_i \in R[X_1,\ldots,X_k], \quad \deg(P_i) \leq 2,\) and computes the Euler-Poincaré characteristic of \(S\). The complexity of the algorithm is \(k^{O(\ell)}\). Cited in 4 Documents MSC: 14P10 Semialgebraic sets and related spaces 14P25 Topology of real algebraic varieties 14Q20 Effectivity, complexity and computational aspects of algebraic geometry 68Q25 Analysis of algorithms and problem complexity PDFBibTeX XMLCite \textit{S. Basu}, Comput. Complexity 15, No. 3, 236--251 (2006; Zbl 1103.14032) Full Text: DOI