On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

摘要

Let S⊂ℝ k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝ[X ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ k+m onto ℝ m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) O(q ℓ). We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is (k+m)2O(ql)(k+m)^{2^{O(qell)}} . For fixed q and ℓ, both the bounds are polynomial in k+m.