Guest talk: Othon Michail "Algorithmic Transformations and Growth Processes for Programmable Matter"
Algorithmic Transformations and Growth Processes for Programmable Matter
University of Liverpool
Abstract: In this talk, I will first give a high-level introduction to the area of algorithmic foundations of programmable matter and to the types of systems and applications that have been motivating its development. I will then go through two models and respective sets of centralized algorithmic problems: 1. Transformations via rotation and 2. Growth processes. In the former, I will show in detail how any given pair of orthogonal convex shapes of the same size, which are additionally satisfying a color-consistency constraint, can be transformed into each other through a sequence of rotation operations only. In the latter, I will define the model and different types of possible growth operations and I will briefly discuss exact characterizations for restricted types of growth operations and first partial characterizations for the most general types. Depending on time, I might also touch upon growth processes on graphs. I will conclude with a discussion on some interesting open problems.
This talk is mostly based on two recent papers, one joint paper with Nada Almalki and another paper with Matthew Connor. The growth processes on graphs are from joint work with George Mertzios, George Skretas, Paul Spirakis, and Michail Theofilatos.