On Geometric Shape Construction via Growth Operations

Almalki, Nada and Michail, Othon ORCID: 0000-0002-6234-3960 (2022) On Geometric Shape Construction via Growth Operations. In: International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS).

Text 2207.03275.pdf - Author Accepted Manuscript Download (563kB) | Preview

Abstract

In this work, we investigate novel algorithmic growth processes. Our system runs on a 2-dimensional grid and operates in discrete time steps. The growth process begins with an initial shape of nodes and, in every time step by applying (in parallel) one or more growth operations of a specific type to the current shape-instance, generates the next instance, always satisfying. Our goal is to characterize the classes of shapes that can be constructed in or polylog n time steps, n being the size of the final shape, and determine whether a shape can be constructed from an initial shape using a finite sequence of growth operations of a given type, called a constructor of. In particular, we propose three growth operations, full doubling, row and column doubling, which we call RC doubling, and doubling, and explore the algorithmic and structural properties of their resulting processes under a geometric setting. For full doubling, in which, in every time step, every node generates a new node in a given direction, we completely characterize the structure of the class of shapes that can be constructed from a given initial shape. For RC doubling, in which complete columns or rows double, our main contribution is a linear-time centralized algorithm that for any pair of shapes decides if can be constructed from and, if the answer is yes, returns an -time step constructor of S:F from S:I. For the most general doubling operation, where a subset of individual nodes can double, we show that some shapes cannot be constructed in sublinear time steps and give two universal constructors of any from a singleton, which are efficient (i.e., up to polylogarithmic time steps) for large classes of shapes. Both constructors can be computed by polynomial-time centralized algorithms for any shape S:F.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Centralized algorithm, Geometric growth operations, Programmable matter, Constructor
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	08 Aug 2022 08:01
Last Modified:	08 Mar 2023 14:52
DOI:	10.1007/978-3-031-22050-0_1
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3160450