An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions

Saugata Basu, Richard Pollack, Marie-Francoise Roy

We prove an asymptotically tight bound (asymptotic with respect to the number of polynomials for fixed degrees and number of variables) on the number of semi-algebraically connecte…