A rectangular partition algorithm for planar self-assembly

Collective construction is concerned with the study of how multiple robots construct a structure without centralized control. In this paper, we proposed an algorithm to generate labels and transition rules for robots to producing an arbitrary two dimensional structure with only local sensing. The algorithm proceeds by first partitioning the desired structure into a set of rectangles, generating rules and labels for each rectangle, assigning labels to tiles to be placed, generating rules to connect the rectangles, and finally replacing redundant labels and rules in a post-processing step. This algorithm guarantees convergence to the desired structure, produces fewer labels than those algorithms found in the literature, and has the potential to handle structures impossible with a single seed.