On some limitations of reaction-diffusion chemical computers in relation to Voronoi diagram and its inversion

A reaction-diffusion chemical computer in this context is a planar uniform chemical reactor, where data and results of a computation are represented by concentration profiles of reactants and the computation itself is implemented via the spreading and interaction of diffusive and phase waves. This class of chemical computers are efficient at solving problems with a 'natural' parallelism where data sets are decomposable onto a large number of geographically neighboring domains which are then processed in parallel. Typical problems of this type include image processing, geometrical transformations and optimisation. When chemical based devices are used to solve such problems questions regarding their reproducible, efficiency and the accuracy of their computations arise. In addition to these questions what are the limitations of reaction-diffusion chemical processors-what type of problems cannot currently and are unlikely ever to be solved? To answer the questions we study how a Voronoi diagram is constructed and how it is inverted in a planar chemical processor. We demonstrate that a Voronoi diagram is computed only partially in the chemical processor. We also prove that given a specific Voronoi diagram it is impossible to reconstruct the planar set (from which diagram was computed) in the reaction-diffusion chemical processor. In the Letter we open the first ever line of enquiry into the computational inability of reaction-diffusion chemical computers. (C) 2003 Elsevier Science B.V. All rights reserved.