  A Cylindrical Algebraic Decomposition (CAD) is a decomposition of R^n into a
finite collection of semialgebraic cells. A CAD satisfies the "frontier
condition" if, for every cell C, there is a collection of cells of the
decomposition whose union is the closure of C. This property is referred to in
other literature as "closure finiteness" or "boundary coherence". This paper
proves the existence of, and presents an algorithm to construct, a CAD
satisfying the frontier condition without a preliminary change of coordinates,
e.g., in the potential presence of blow-ups. The algorithm has elementary (in
the sense of L. Kalmar) complexity. This also provides an upper bound on the
number of cells in a CAD with this property. The frontier condition can be
useful in computing topological properties of semialgebraic sets defined by
first-order formulas, in solving motion planning problems and in triangulations
of definable monotone families. The algorithm presented takes a novel approach
in that it uses a recursion on the lexicographical order of cell indices in the
initial decomposition.
