  Cylindrical algebraic decomposition (CAD) is an important tool for the study
of real algebraic geometry with many applications both within mathematics and
elsewhere. It is known to have doubly exponential complexity in the number of
variables in the worst case, but the actual computation time can vary greatly.
It is possible to offer different formulations for a given problem leading to
great differences in tractability. In this paper we suggest a new measure for
CAD complexity which takes into account the real geometry of the problem. This
leads to new heuristics for choosing: the variable ordering for a CAD problem,
a designated equational constraint, and formulations for truth-table invariant
CADs (TTICADs). We then consider the possibility of using Groebner bases to
precondition TTICAD and when such formulations constitute the creation of a new
problem.
