Algebraic decomposition of regular curves

The cylindrical algebraic decomposition method decomposes Er into regions over which a given polynomial has constant sign by extension of one complicated decomposition of Er-1. We investigate a method which decomposes Er into sign-invariant region by combining several but simpler decompositions of Er-1. We can obtain a sign-invariaat decomposition of E2 defined by a bivariate polynomial of total degree n and coefficient size d in time O(n12 (d + log n)2 log n). Preliminary experiments suggest that the method is useful in practice