Cylindrical Algebraic Decomposition (CAD) algorithms typically produce a decomposition adapted to a finite family of semi-algebraic sets \(\mathcal {F}\) (i.e. every member of \(\mathcal {F}\) is a union of cells). Different algorithms may produce different outputs, and introduce unnecessary cell divisions. Recent work by Michel, Mathonet, and Zénaïdi in ISSAC 2024 formalised this issue by studying the refinement order on the set of all CADs adapted to \(\mathcal {F}\) and analysing the existence of a minimum (coarsest) adapted CAD. It was shown that such a minimum adapted CAD always exists for subsets of \(\mathbb {R}\) and \(\mathbb {R}^2\), but not of \(\mathbb {R}^n\) (n ≥ 3) in general.

We consider cylindrical algebraic decompositions (CADs) as a tool for representing semi-algebraic subsets of <?TeX $\mathbb {R}^n$?> Math 1 . In this framework, a CAD <?TeX $\mathscr{C}$?> Math 2 is adapted to a given set S if S is a union of cells of <?TeX $\mathscr{C}$?> Math 3 . Different algorithms computing an adapted CAD may produce different outputs, usually with redundant cell divisions. In this paper we analyse the possibility to remove the superfluous data. More precisely we consider the set CAD(S) of CADs that are adapted to S, endowed with the refinement partial order and we study the existence of minimal and minimum elements in this poset.