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

Abstract

Let $S\subset {\mathbb{R}}^{k+m}$ be a compact semi-algebraic set defined by a system of $\ell$ polynomial inequalities of degree at most 2. $Let$π$denotethestandardprojectionfrom$\R^{k + m}$onto$\R^m$.Weprovethatforany$q >0$,thesumofthefirst$q$Bettinumbersof$π(S)$isboundedby$(k + m)^{O(q\ell)}.$Wealsopresentanalgorithmforcomputingthethefirst$q$Bettinumbersof$π(S)$,whosecomplexityis$ (k+m)^{2^{O(q\ell)}}.$Forfixed$q$and$\ell$,boththeboundsarepolynomialin$k+m$.

21 pages, 1 figure. Requires diagrams.tex

References in corpus (2)

• Polynomial-time computing over quadratic maps I: sampling in real algebraic sets
• Topology of definable Hausdorff limits