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).