CALCULATING VORONOI DIAGRAMS USING SIMPLE CHEMICAL REACTIONS

Oct 26, 2026

The paper surveys how simple chemical reactions can compute Voronoi diagrams and related geometric constructs. It argues that specialised chemical processors behave like parallel processors: adding complexity to inputs within an area does not raise computation time, and multiple Voronoi diagrams can be calculated simultaneously. Using reaction specifics and cross-reactivity, the same systems can also compute diagrams sequentially from distinct chemical inputs.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages27

Reading Time1 h 8 min

AccessFree to download

Abstract

1. Introduction

Weighted Voronoi diagrams and key definitions

Chemical implementations and prior work

CALCULATING VORONOI DIAGRAMS USING SIMPLE CHEMICAL REACTIONS BEN DE LACY COSTELLO Unconventional Computing Centre, University of the West of England, Bristol, UK, BS161QY [E-mail](E-mail Ben.DeLacyCostello@uwe.ac.uk)[ ](E-mail Ben.DeLacyCostello@uwe.ac.uk)[Ben.DeLacyCostello@uwe.ac.uk](E-mail Ben.DeLacyCostello@uwe.ac.uk) Received Revised Communicated by ABSTRACT This paper overviews work on the use of simple chemical reactions to calculate Voronoi diagramsand undertake other related geometric calculations. This work highlights that this type of specialised chemical processor is a model example of a parallel processor. For example increasing the complexity of the input data within a given area does not increase the computation time. These processors are also able to calculate two or more Voronoi diagrams in parallel. Due to the specific chemical reactions involved and the relative strength of reaction with the substrate (and crossreactivity with the products) these processors are also capable of calculating Voronoi diagrams sequentially from distinct chemical inputs. The chemical processors are capable of calculating a range of generalised Voronoi diagrams (either from circular drops of chemical or other geometric shapes made from adsorbent substrates soaked in reagent) , skeletonisation of planar shapes and weighted Voronoi diagrams (e.g. additively weighted Voronoi diagrams, Multiplicitavely weighted Crystal growth Voronoi diagrams) . The paper will also discuss some limitations of these processors. These chemical processors constitute a class of pattern forming reactions which have parallels with those observed in natural systems. It is possible that specialised chemical processors of this general type could be useful for synthesising functional structured materials. Keywords: Voronoi diagram, precipitating chemical reaction, chemical processor 1. Introduction Voronoi diagrams are used to partition space into spheres of influence in many branches of science and can be observed in numerous natural systems. They find uses in many fields such as astronomy (galaxy cluster analysis[1]), biology (modelling tumour cell growth [2]), chemistry (modelling crystal growth [3]), ecology (modelling competition [4]) and computational geometry (solving nearest neighbour problems [5]) . In addition to standard and generalised Voronoi diagrams weighted diagrams are commonly used for example to model crystal growth [6]. In simple terms an Additively weighted Voronoi diagram (AWVD) is where all sources grow at the same rate but some start at different times. A Multiplicatively weighted Voronoi diagram (MWVD) is where all sources start growing at the same time but some grow with different rates. The multiplicatively weighted crystal growth Voronoi diagram (MWCGVD) [6] is an extension of the MWVD and overcomes the problem of disconnected regions which are not possible in growing crystals (or expanding chemical fronts). Therefore, in the MWCGVD when regions with large growth rates meet regions with lower growth rates they can “wraparound” these regions to form a connected Voronoi diagram of the plane. The bisectors of weighted Voronoi diagrams are hyperbolic segments rather than straight lines. For a more in depth description and mathematical treatment of Voronoi diagrams and weighted derivatives see references [6,7] In addition to their many uses in modeling, Voronoi diagrams can be observed in nature, for example, in animal coat markings [8] between interacting bacterial, fungal or slime mould colonies [9,10] between growing crystals and even in universal structures such as gravitational caustics [11] . They were also observed in Gas discharge systems [12] . The formation of Voronoi diagrams in chemical systems with one reagent and one substrate was first reported in [13] . This and similar reactions were utilised as chemical processors for the computation of the shortest obstacle free path [14], skeltonisation

FAQs

How can chemical reactions be used to calculate Voronoi diagrams?

By employing specialised chemical processors where reacting solutions and substrates form patterns that correspond to Voronoi structures. The paper explains that these reactions can also support other geometric calculations.

What makes these chemical processors efficient in computation time?

Increasing the complexity of the input data within a given area does not increase computation time. The processors also support parallel computation of two or more Voronoi diagrams.

Can the processors perform sequential Voronoi calculations?

Yes. Due to the specific chemical reactions, relative reaction strength with the substrate, and cross-reactivity with products, the systems can calculate Voronoi diagrams sequentially from distinct chemical inputs.

Oct 26, 2026

Upload by naya.afterrain