  We generalize regular subdivisions (polyhedral complexes resulting from the
projection of the lower faces of a polyhedron) introducing the class of
recursively-regular subdivisions. Informally speaking, a recursively-regular
subdivision is a subdivision that can be obtained by splitting some faces of a
regular subdivision by other regular subdivisions (and continue recursively).
We also define the \emph{finest regular coarsening} and the \emph{regularity
tree} of a polyhedral complex. We prove that recursively-regular subdivisions
are not necessarily connected by flips and that they are acyclic with respect
to the in-front relation. We show that the finest regular coarsening of a
subdivision can be efficiently computed, and that whether a subdivision is
recursively regular can be efficiently decided. As an application, we also
extend a theorem known since 1981 on illuminating space by cones and present
connections of recursive regularity to tensegrity theory and graph-embedding
problems.
