DEVELOPING PROXIMITY GRAPHS BY PHYSARUM POLYCEPHALUM: DOES THE PLASMODIUM FOLLOW THE TOUSSAINT HIERARCHY?
Abstract
Plasmodium of Physarum polycephalum spans sources of nutrients and constructs varieties of protoplasmic networks during its foraging behavior. When the plasmodium is placed on a substrate populated with sources of nutrients, it spans the sources with protoplasmic network. The plasmodium optimizes the network to deliver efficiently the nutrients to all parts of its body. How exactly does the protoplasmic network unfold during the plasmodium's foraging behavior? What types of proximity graphs are approximated by the network? Does the plasmodium construct a minimal spanning tree first and then add additional protoplasmic veins to increase reliability and through-capacity of the network? We analyze a possibility that the plasmodium constructs a series of proximity graphs: nearest-neighbour graph (NNG), minimum spanning tree (MST), relative neighborhood graph (RNG), Gabriel graph (GG) and Delaunay triangulation (DT). The graphs can be arranged in the inclusion hierarchy (Toussaint hierarchy): NNG⊆MST⊆RNG⊆GG⊆DT. We aim to verify if graphs, where nodes are sources of nutrients and edges are protoplasmic tubes, appear in the development of the plasmodium in the order NNG→MST→RNG→GG→DT, corresponding to inclusion of the proximity graphs.
References
- Neural Network World 6, 335 (1991). Google Scholar
-
A. Adamatzky , B. De Lacy Costello and T. Asai , Reaction Diffusion Computers ( Elsevier , 2005 ) . Google Scholar -
A. Adamatzky and C. Teuscher , From Utopian to Genuine Unconventional Computers ( Luniver Press , 2006 ) . Google Scholar - Kybernetes: The International Journal of Systems & Cybernetics 37, 258 (2008). Crossref, ISI, Google Scholar
-
A. Adamatzky , Unconventional Computing 2007 ( Luniver Press , 2007 ) . Google Scholar - Parallel Processing Letters 17, 455 (2007). Link, Google Scholar
- Int. J. Bifurcation and Chaos (2008). Google Scholar
- Parallel Processing Letters 16, 19 (2006). Link, Google Scholar
M. Aono and Y.-P. Gunji , Resolution of infinite-loop in hyperincursive and nonlocal cellular automata: Introduction to slime mold computing, Computing Anticiaptory Systems, AIP Conference Proceedings718 (2001) pp. 177–187. Google ScholarM. Aono and Y.-P. Gunji , Material implementation of hyper-incursive field on slime mold computer, Computing Anticipatory Systems, AIP Conference Proceedings718 (2004) pp. 188–203. Google Scholar- Notices of the Academy of Sciences of the USSR 270, 1289 (1983). ISI, Google Scholar
- Notices of the Academy of Sciences of the USSR 299, 530 (1988). ISI, Google Scholar
- Delaunay B. Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7 (1934) 793-800 . Google Scholar
- Langmuir 19, 4714 (2003). Crossref, ISI, Google Scholar
- Systematic Zoology 18, 259 (1969). Crossref, Google Scholar
- Proc. IEEE 80, 1502 (1992). Crossref, ISI, Google Scholar
- , Computational Geometry, ed.
G. Toussaint (1985) pp. 217–248. Crossref, Google Scholar - Geographical Analysis 12, 205 (1984). Crossref, ISI, Google Scholar
- Mills J. The nature of the Extended Analog Computer. In: Teuscher C., Nemenman I.M., and Alexander F. J. (Eds). Physica D. Special Issue: Novel Computing Paradigms: Quo Vadis? (2008), in press . Google Scholar
- Biophysical Chemistry 84, 195 (2000). Crossref, ISI, Google Scholar
- Nature 407, 470 (2000). Crossref, ISI, Google Scholar
- Research in Microbiology 152, 767 (2001). Crossref, ISI, Google Scholar
- Biophysical Chemistry 92, 47 (2001). Crossref, ISI, Google Scholar
- Discrete Mathematics 233, 3 (2001). Crossref, ISI, Google Scholar
- Automatica, Languages and Programming 416 . Google Scholar
-
F. P. Preparata and M. I. Shamos , Computational Geometry ( Springer-Verlag , 1985 ) . Crossref, Google Scholar - http://www.processing.org/ . Google Scholar
- Int. J. Unconventional Computing (2008). Google Scholar
- Shirakawa T., Adamatzky A., Gunji Y.-P., Miyake Y. On simultaneous construction of Voronoi diagram and Delaunay triangulation by Physarum polycephalum (2008), submitted . Google Scholar
A. Takamatsu , Mobiligence in an amoeboid cell, Plasmodium of Physarum polycephalum 2nd International Symposium on Mobilgence (2007) pp. 48–51. Google Scholar- Pattern Recognition 12, 261 (1980). Crossref, ISI, Google Scholar
-
G. T. Toussaint , Some unsolved problems on proximity graphs , 1st Workshop on Proximity Graphs ( 1989 ) , http://cgm.cs.mcgill.ca/~godfried/publications/openprox.pdf . Google Scholar - BioSystems 73, 45 (2004). Crossref, ISI, Google Scholar
- , Biologically Inspired Approaches to Advanced Information Technology, eds.
A. J. Ijspeert , T. Masuzawa and S. Kusumoto (Springer, 2006) pp. 20–32. Crossref, Google Scholar - Electronics Letters 16, 556 (1980). Crossref, ISI, Google Scholar


