Universal Reconfigurability in Two-Dimensional Space

Abstract

Master's defense:

A geometric graph is a graph possessing certain geometric properties. The study of geometric graphs has emerged as a fruitful field of research at the intersection of computer science and mathematics that bridges the gap between theory and practice. Moreover, in many situations, it is these geometric properties that lead to the discovery of new solutions to existing problems. This thesis considers a reconfiguration problem and presents multiple hardness results for an important problem in the field that justify the setting as well as the positive result.

Reconfiguration is the process of changing the state of a system using predetermined moves - like reconfiguring a Rubik's cube. While this is a very general concept, the focus in this dissertation is on one main type: reconfiguring the ``outer'' shape of an object. Chapter 2 presents a reconfiguration problem for robots made of n smaller identical pivoting robots that we will call modules. To reconfigure the system, individual modules can move along the boundary of the system. Chapter 3 provides hardness results motivating the setting and necessity of all parts of the setting. For the final setting, an O(n^3) algorithm is known. These results characterize the question of universal reconfigurability of modular pivoting robots in two dimensions.