×

Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities. (English) Zbl 1103.14032

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

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
Full Text: DOI