Recursively-regular subdivisions and applications

<p>We generalize regular subdivisions (polyhedral complexes resulting from the projection of the lower faces of a polyhedron) introducing the class of <em>recursively-regular subdivisions</em>. 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 <em>finest regular coarsening</em> and the <em>regularity tree</em> 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.</p><p> </p><p> </p><p> </p><p> </p><p>