EFFICIENT ALGORITHM FOR COMPUTING THE EULER-POINCARE CHARACTERISTIC OF A SEMI-ALGEBRAIC SET DEFINED BY FEW QUADRATIC INEQUALITIES

摘要

We present an algorithm which takes as input a closed semi-algebraic set, S is contained in R~k, defined by P_1 ≤ 0,...,P_l ≤ 0, P_i ∈ R[X_1,...,X_k], deg(P_i) ≤ 2, and computes the Euler-Poincare characteristic of 5. The complexity of the algorithm is k~(O(l)).