The original Cylindrical Algebraic Decomposition is part of a decision procedure for the theory of real closed fields. It performs an arbitrary cellular decomposition of the Euclidean space in such a way that each given polynomial is invariant in sign throughout every cell and that its solutions are obtained by retaining those cells in which the sign is zero. The discrete CAD extension to binary images can be represented through connectivity graphs which give a description useful both for image recognition and pictorial queries. Moreover this structure itself can be stored by compact strings on a five letter alphabet.

DCAD - Example of discrete cellular decomposition.