Rafel Jaume and Günter Rote:

Recursively-regular subdivisions and applications

Journal of Computational Geometry 7 (2016), 185–220. doi:10.20382/jocg.v7i1a10, arXiv:1310.4372 [cs.CG].


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, a recursively-regular subdivision is a subdivision that can be obtained by splitting some faces of a regular subdivision by other regular subdivisions (and continuing recursively). We also define the finest regular coarsening and the 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.

  pdf file (gzipped)
other papers about this subject
Last update: May 2, 2016.