World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

DEVELOPING PROXIMITY GRAPHS BY PHYSARUM POLYCEPHALUM: DOES THE PLASMODIUM FOLLOW THE TOUSSAINT HIERARCHY?

    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): NNGMSTRNGGGDT. 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 NNGMSTRNGGGDT, corresponding to inclusion of the proximity graphs.

    References

    • A. Adamatzky, 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
    • A. Adamatzky, Kybernetes: The International Journal of Systems & Cybernetics 37, 258 (2008). Crossref, ISIGoogle Scholar
    • A.   Adamatzky et al. , Unconventional Computing 2007 ( Luniver Press , 2007 ) . Google Scholar
    • A. Adamatzky, Parallel Processing Letters 17, 455 (2007). LinkGoogle Scholar
    • A. Adamatzky, B. De Lacy Costello and T. Shirakawa, Int. J. Bifurcation and Chaos  (2008). Google Scholar
    • S. G. Akl, Parallel Processing Letters 16, 19 (2006). LinkGoogle 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 Scholar
    • M. 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
    • M. Burgin, Notices of the Academy of Sciences of the USSR 270, 1289 (1983). ISIGoogle Scholar
    • M. Burgin, Notices of the Academy of Sciences of the USSR 299, 530 (1988). ISIGoogle Scholar
    • Delaunay B. Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7 (1934) 793-800 . Google Scholar
    • M. J. Fuerstmanet al., Langmuir 19, 4714 (2003). Crossref, ISIGoogle Scholar
    • K. R. Gabriel and R. R. Sokal, Systematic Zoology 18, 259 (1969). CrossrefGoogle Scholar
    • J. W. Jaromczyk and G. T. Toussaint, Proc. IEEE 80, 1502 (1992). Crossref, ISIGoogle Scholar
    • D. G. Kirkpatrick and J. D. Radke, Computational Geometry, ed. G. Toussaint (1985) pp. 217–248. CrossrefGoogle Scholar
    • D. W. Matula and R. R. Sokal, Geographical Analysis 12, 205 (1984). Crossref, ISIGoogle 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
    • T. Nakagakia, H. Yamada and T. Ueda, Biophysical Chemistry 84, 195 (2000). Crossref, ISIGoogle Scholar
    • T. Nakagaki, H. Yamada and A. Toth, Nature 407, 470 (2000). Crossref, ISIGoogle Scholar
    • T. Nakagaki, Research in Microbiology 152, 767 (2001). Crossref, ISIGoogle Scholar
    • T. Nakagaki, H. Yamada and A. Toth, Biophysical Chemistry 92, 47 (2001). Crossref, ISIGoogle Scholar
    • J. Nesetril, E. Milkova and H. Nesetrilova, Discrete Mathematics 233, 3 (2001). Crossref, ISIGoogle Scholar
    • M. S.   Paterson and F. F.   Yao , Automatica, Languages and Programming   416 . Google Scholar
    • F. P.   Preparata and M. I.   Shamos , Computational Geometry ( Springer-Verlag , 1985 ) . CrossrefGoogle Scholar
    • http://www.processing.org/ . Google Scholar
    • T. Shirakawa and Y. -P. Gunji, 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
    • G. T. Toussaint, Pattern Recognition 12, 261 (1980). Crossref, ISIGoogle 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
    • S. Tsuda, M. Aono and Y.-P. Gunji, BioSystems 73, 45 (2004). Crossref, ISIGoogle Scholar
    • S. Tsuda, K. P. Zauner and Y. P. Gunji, Biologically Inspired Approaches to Advanced Information Technology, eds. A. J. Ijspeert, T. Masuzawa and S. Kusumoto (Springer, 2006) pp. 20–32. CrossrefGoogle Scholar
    • R. B. Urquhart, Electronics Letters 16, 556 (1980). Crossref, ISIGoogle Scholar