Centralized and Distributed Algorithms for Shape Transformation via Size-Changing Dynamics

Abstract

This thesis investigates a fundamental problem of shape transformation in programmable matter: given an initial connected shape SI on a two-dimensional square grid, how can it be transformed into a final shape SF via size-changing dynamics, specifically, growth and shrinking operations, while preserving connectivity and avoiding collisions? We study both the algorithmic power and complexity limitations of this transformation problem under both centralized and distributed models. Our goal is to develop efficient algorithms and establish lower bounds that characterize the computational difficulty of shape transformation via size- changing dynamics. The thesis is organized into three parts. In the first part (Chapter 2), we formalize the geometric and graph based models of shapes and define the primitive operations of growth and shrinking. We distinguish between connectivity and adjacency graph models, define valid transformation processes, and analyze two types of structural collisions. We also introduce execution models (centralized and distributed) and define key geometric concepts such as turning points, compressibility, and other structural properties of shapes, along with the different shape classes considered in this thesis. Finally, we present the lower bounds established in this work, showing the minimum number of steps required to construct or reduce certain classes of shapes—such as staircases, paths, and trees—based on their structural complexity. In the second part (Chapters 3 and 4), we focus on a centralized setting. Chapter 3 introduces and analyzes restricted growth operations, namely full doubling and RC doubling, which enable fast and collision-free construction. We characterize the class of constructible shapes and design efficient decision algorithms and optimal-time shape constructors. Chapter 4 extends this study to the general growth operations, presenting centralized algorithms that construct shapes with kturning points in polylogarithmic time steps in both the connectivity and adjacency graph models. In the last part (Chapter 5), we turn to the distributed setting, where agents are modeled as finite-state machines communicating via reconfigurable circuits. We focus on reduction problems, using shrinking (and, in some cases, growth) operations. We design distributed algorithms for reducing shapes to simpler forms while respecting structural constraints. We present distributed algorithms that reduce trees to single nodes, incompressible forms, or topologically equivalent shapes—within polylogarithmic rounds complexity with high probability. Overall, this thesis introduces a novel framework for shape transformation via size-changing dynamics, providing formal models, efficient algorithms, and lower bounds in both centralized and distributed settings. These results offer new insights into the algorithmic complexity of programmable matter systems.