Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials

•Every canonical decomposition is optimal for isostatic or underconstrained graphs.•An O(n3)O(n3) algorithm to find a canonical and optimal decomposition–recombination plan.•An efficient technique for optimally modifying large indecomposable systems.•Applications of the theory to modeling materials.•A collection of open problems in the area.

Optimal recursive decomposition (or DR-planning  ) is crucial for analyzing, designing, solving or finding realizations of geometric constraint systems. While the optimal DR-planning problem is NP-hard even for (general) 2D bar–joint constraint systems, we describe an O(n3)O(n3) algorithm for a broad class of constraint systems that are isostatic or underconstrained. The algorithm achieves optimality by using the new notion of a canonical DR-plan that also meets various desirable, previously studied criteria. In addition, we leverage recent results on Cayley configuration spaces to show that the indecomposable systems – that are solved at the nodes of the optimal DR-plan by recombining solutions to child systems – can be minimally modified to become decomposable and have a small DR-plan, leading to efficient realization algorithms. We show formal connections to well-known problems such as completion of underconstrained systems. Well suited to these methods are classes of constraint systems that can be used to efficiently model, design and analyze quasi-uniform (aperiodic) and self-similar, layered material structures. We formally illustrate by modeling silica bilayers as body–hyperpin systems and cross-linking microfibrils as pinned line-incidence systems. A software implementation of our algorithms and videos demonstrating the software are publicly available online (visit http://cise.ufl.edu/~tbaker/drp/index.html).