2006/02/17 by Saugata Basu, Thierry Zell
Computer Science · Mathematics · #Commutative Algebra and Its Applications #Mathematical functions and polynomials #Polynomial and algebraic computation #math.AG #math.AT #msc:14P10 #msc:55T99 #msc:68W30
paper · pdf · doi:10.1007/s00454-007-9014-1
published as Discrete and Computational Geometry 39 (2008), 100--122. · 21 pages, 1 figure. Requires diagrams.tex
arxiv created 2006/02/17 · openalex publication_date 2007/09/14 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Let S ⊂ \Rk + m be a compact semi-algebraic set defined by a system of ℓ polynomial inequalities of degree at most 2. Let π denote the standard projection from \Rk + m onto \Rm. 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 the first q Betti numbers of π(S), whose complexity is (k+m)^2O(qℓ). For fixed q and ℓ, both the bounds are polynomial in k+m.