On geometric shape construction via growth operations

Almalki, Nada ORCID: 0000-0001-9403-1702 and Michail, Othon ORCID: 0000-0002-6234-3960 (2024) On geometric shape construction via growth operations. Theoretical Computer Science, 984. p. 114324.

Text AM-TCS23.pdf - Author Accepted Manuscript Download (792kB) | Preview

Abstract

We study algorithmic growth processes under a geometric setting. Each process begins with an initial shape of nodes SI=S0 and, in every time step t≥1, by applying (in parallel) one or more growth operations of a specific type to the current shape, St−1, generates the next, St, always satisfying |St|>|St−1|. We define three types of growth operations and explore the algorithmic and structural properties of their resulting processes. Our goal is to characterize the classes of shapes that can be constructed in O(log⁡n) or polylog n time steps, n being the size of the final shape SF. Moreover, we want to determine whether a given shape SF can be constructed from a given initial shape SI using a finite sequence of growth operations of a given type, called a constructor of SF. We give exact and partial characterizations of classes of shapes that can be constructed in polylog n time steps, polynomial-time centralized algorithms for deciding reachability between pairs of input shapes (SI,SF) and for generating constructors when SF can be constructed from SI, as well as some negative results.

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	27 Nov 2023 16:09
Last Modified:	27 Feb 2024 15:40
DOI:	10.1016/j.tcs.2023.114324
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177030