  In this paper we introduce the notion of an Open Non-uniform Cylindrical
Algebraic Decomposition (NuCAD), and present an efficient model-based algorithm
for constructing an Open NuCAD from an input formula. A NuCAD is a
generalization of Cylindrical Algebraic Decomposition (CAD) as defined by
Collins in his seminal work from the early 1970s, and as extended in concepts
like Hong's partial CAD. A NuCAD, like a CAD, is a decomposition of
n-dimensional real space 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.
