ON SIMULTANEOUS CONSTRUCTION OF VORONOI DIAGRAM AND DELAUNAY TRIANGULATION BY PHYSARUM POLYCEPHALUM
ON SIMULTANEOUS CONSTRUCTION OF VORONOI DIAGRAM AND DELAUNAY TRIANGULATION BY PHYSARUM POLYCEPHALUM
复制标题
DOI：
10.1142/s0218127409024682
复制
发表时间：
2009-09-01
影响因子：
2.2
通讯作者：
Miyake, Yoshihiro
中科院分区：
文献类型：
--
作者：
Shirakawa, Tomohiro;Adamatzky, Andrew;Miyake, Yoshihiro
我们的实验表明，Voronoi图和它的对偶图Delaunay三角同时构建-特定的条件-在培养的疟原虫，多头绒泡菌的营养状态。给定平面数据集的每个点都由一个微小的疟原虫团表示。疟原虫从它们的初始位置传播，但在某些条件下，当它们遇到来自不同位置的疟原虫时，停止传播。因此，未被原质团占据的空间轨迹表示给定平面集的Voronoi图的边缘。同时，起源于相邻位置的原质团形成合并的原生质管，其中最强的管近似于给定平面集的Delaunay三角剖分。疟原虫只解决了有限的数据集的问题，但提出的结果奠定了良好的基础，为进一步的调查。
We experimentally demonstrate that both Voronoi diagram and its dual graph Delaunay triangulation are simultaneously constructed - for specific - conditions - in cultures of plasmodium, a vegetative state of Physarum polycephalum. Every point of a given planar data set is represented by a tiny mass of plasmodium. The plasmodia spread from their initial locations but, in certain conditions, stop spreading when they encounter plasmodia originated from different locations. Thus space loci not occupied by the plasmodia represent edges of Voronoi diagram of the given planar set. At the same time, the plasmodia originating at neighboring locations form merging protoplasmic tubes, where the strongest tubes approximate Delaunay triangulation of the given planar set. The problems are solved by plasmodium only for limited data sets, however the results presented lay a sound ground for further investigations.