Open Non-uniform Cylindrical Algebraic Decompositions

This paper introduces the notion of an Open Non-uniform Cylindrical Algebraic Decomposition (NuCAD), and presents an efficient model-based algorithm for constructing an Open NuCAD from an input formula. Using a limited experimental implementation of the algorithm, we demonstrate the effectiveness of the approach. NuCAD generalizes Cylindrical Algebraic Decomposition (CAD) as defined by Collins in his seminal work from the early 1970s, and extended in concepts like Hong's partial CAD. A NuCAD, like a CAD, is a decomposition of Rⁿ into cylindrical cells. But unlike a CAD, the cells in a NuCAD need not be arranged cylindrically. It is in this sense that NuCADs are not uniformly cylindrical. However, NuCADs, like CADs, carry a tree-like structure that relates different cells. It is a very different tree but, as with the CAD tree structure, it allows some operations to be performed efficiently, for example locating the containing cell for an arbitrary input point.