Varieties of Doubly-Exponential Behaviour in Cylindrical Algebraic Decomposition

It is almost fifty years since cylindrical algebraic decomposition was introduced: it was far better than previous ideas, but the algorithm was doubly exponential in the number of variables. Various mitigations have been developed over the last forty years. But we have known for over thirty years that cylindrical algebraic decomposition has a worst-case lower bound doubly-exponential in the number of quantifier alternations, which in worst case is proportional to the number of variables. This lower bound can describe the degree of the polynomials, or the number of polynomials, or both. This paper explores the reasons for this, and what further developments, theoretical or practical, might be possible.