Rafel Jaume and Günter Rote:
The finest regular coarsening and recursively-regular subdivisions
manuscript, arXiv:1310.4372 [cs.CG],
October 2013, 24 pages, submitted for publication.
We generalize the notion of regular polyhedral subdivision of a point (or
vector) configuration in a new direction. This is done after studying some
related objects, like the finest regular coarsening and the regularity tree of
a subdivision. Properties of these two objects are derived, which confer
more structure to the class of non-regular subdivisions, relating them to
its (in a sense) closest regular subdivision. We introduce the class of
recursively-regular subdivisions and show that it is a proper superclass of
the regular subdivisions and a proper subclass of the visibility-acyclic
subdivisions. We also show that recursively-regular triangulations of a given
configuration are in general not connected by geometric bistellar flips.
Finally, some algorithms related to these new concepts are given and
applications of the main results of the article are pointed out. In
particular, relations to covering by floodlights, covering by homotheties,
tensegrity of spider webs and a high-dimensional graph embedding problem are
Last update: October 24, 2013.