Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space E r partitions E r into connected subsets compatible with the zeros of the polynomials. By “compatible with the zeros of the polynomials” we mean that on each subset of E r , each of the polynomials either vanishes everywhere or nowhere. For example, consider the bivariate polynomial $${y^4} - 2{y^3} + {y^2} - 3{x^2}y + 2{x^4}.$$