On Minimal and Minimum Cylindrical Algebraic Decompositions
Lucas Michel, Pierre Mathonet, Naïm Zénaïdi · 2024
We consider cylindrical algebraic decompositions (CADs) as a tool for representing semi-algebraic subsets of Math 1 . In this framework, a CAD Math 2 is adapted to a given set S if S is a union of cells of 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.