%Return-Path: gromov
%Date: Fri, 25 Dec 1998 22:48:59 +0100 (MET)
%From: Misha Gromov
%To: ilan
%Subject: titles.tex~
\documentstyle[12pt]{article}
\begin{document}
\vspace*{3in}
\begin{center}
{\em Dedicated to the memory Paul Green}
\end{center}
\pagebreak
\begin{center}
{\sc Preface}
\end{center}
\vspace{.4in}
\begin{flushright}
\begin{verse}
Tyger! Tyger! burning bright
In the forests of the night,
What immortal hand or eye
Could frame thy fearful symmetry?
\end{verse}
\smallskip
William Blake
\end{flushright}
\vspace{.2in}
To make the science of patterns into a true science one must start by
giving a precise definition of pattern. However, this seems neither
feasible nor desirable. It is not feasible because every aspect of human
perception is based on patterns and we can never be sufficiently
detached to give an objective definition. It is not desirable because
any precise definition would only serve to limit ourselves
unnecessarily. However, we will still try to address nontrivial
questions:
{\em Do patterns reflect the reality of the world?} Patterns are
inherent to our mental processes so it is not even clear whether they
have an existence independent of our own perception--to what extent
are we under collective hypnosis, tricked by a visual system eager to
see Pegasus and Pisces in the Poisson distribution of stars?
By simply opening our eyes we are overwhelmed by the presence of
patterns, so we can avoid overloading the brain by closing them and
looking at the universe through the eye of a physicist. At the largest
scales we see Lorentzian space--time gently curving according to
twenty tensorial components and the Newtonian clockwork of stars and
planets. At the smallest scales we see Hilbert spaces of quantum
fields and 10 dimensions of superstrings. Here our analytical
brain scores highest--mathematics, to the delight of Platonists, is
able to capture the evanescent nature of matter.
Encouraged by such success we retain the framework of physics and look
at patterns such as clouds in the sky, water flowing in a river, sand
hills on a beach, and ice crystals on a frosty glass. We then try to
describe what we see. Even in this limited context, human intellect is
put to shame! We cannot precisely describe what we are
perceiving, nor do we have a clear understanding of rules governing
these common patterns. A satisfactory analysis based on the
fundamental laws of physics and probability theory seems a long way
off. Yet these patterns can still be interpreted as physical
phenomena, so their complexity might eventually be understood in terms
of the deep mathematical interaction between local and global dynamics
of matter. Yet the foliage of a tree, the concept of chair, or the
face of a human being seem hopelessly beyond pure physical modeling.
``Local to global'' is a key geometric principle and in
representations of the world it often arises computationally in the
form of partial differential equations (PDE's). Ubiquitous in
physics, these equations were imported into biology by Allan Turing
shortly after he helped win World War~II. Turing envisioned how
simultaneous diffusion of several interacting chemical substances
might cause mosaic patterns on animals, from zebras and tigers to sea
shells and fruit flies larvae [Meinhardt] [Coullet].
\footnote{This might look paradoxical at first since chemical
reactions and diffusion drive the system down an energy well towards
equilibrium, and, moreover, nothing visually interesting occurs in
most chemical reactions. Yet, given two or more degrees of freedom,
equilibrium (i.e., a fixed point of a vector field) is not necessarily
approached along a straight line, but possibly along a spiral in
configurations space and such a spiral orbit might easily generate
regular oscillating behavior when projected back to space--time, a
well known phenomenon in physics. This was discovered in chemistry by
Belousov and Zhabotinski in 1951, a time when every self--respecting
chemist would refuse even to consider such nonsense as oscillatory
chemistry.} Turing's phenomenon has been observed in bacteria which can
display organized collective behavior driven by certain biochemical
interactions [Budrene].
Such models possess symmetry, but what is actually observed is {\em
broken symmetry,} in other words, partial symmetry (if any). In
particular, the PDE's underlying this model are invariant under
translation, and if they are also {\em linear,} the singularities of
their Fourier transform determine the frequencies of observable
periodicities, i.e., solutions which exhibit symmetry which is smaller
than the full symmetry of the underlying equation which, in fact, can
only admit constants as solutions. The full richness of what we
observe is ultimately a result of nonlinearity.
``Broken symmetry'' does not evoke images of beauty, but aesthetically
pleasing products of nature such as flowers but one can trace their
allure to human sensibility to a type of broken symmetry. In fact,
many flowers have finite but not full circular symmetry. According to
Paul Greene [Transduction to generate plant form and pattern: an essay
on cause and effect, {\em Annals of Botany} {\bf 78}:269--281, 1996.]
petals grow layer--by--layer with each consecutive layer taking on a
symmetric arrangement determined by the lowest eigenfunction of an
elasticity problem constrained by the previous stage of morphogenesis.
Similar models were also used by Greene to model phyllotaxis, the
appearance of Fibonacci numbers in the spiral patterns of seeds in
sunflowers and pine cones. Alternative models of phyllotaxis using
finite nonlinear dimensional dynamics rather than by PDE's are given
by [Couder]. In general, PDE's become relevant if we go beyond average
properties of a system and look at geometric properties, those which
depend on shape not just size, e.g., the dynamics of coral reef
formation [Kaandorp, Sloot].
{\em Is everything is a PDE?} Is the development of
all macroscopic patterns, from galactic formation to animal growth,
driven by PDE's? Richard Feynman suggested the answer: ``yes'' with an
eye on the Navier--Stokes equation governing the flow of viscous
incompressible fluids, perhaps because the simple principles
underlying these equations result in a bewilderingly rich set of
patterns such as vortices and Bernard cells.
A biologist knows better than to stick to PDE's and even the
physicist's toolkit of nonlinear dynamics used in developmental
biology, ecology, and the physiology of the brain, does not appear
sufficient to him. Thus the molecular factories of cells are not run
by PDE's because, though the underlying biochemistry is local, it is
not locally linear. It seems hopeless to model global cellular
behavior directly from its underlying biochemistry. However, we can
focus on specific phenomena: division, growth, differentitation.
Imagine a geometric entity composed of billions of cells one can then ask:
{\em What kind of local division rules generate stable global
patterns?} Which rules preserve features during growth? Which rules
ensure an increase in complexity in morphogenesis? As yet, there is no
model for cell division comparable to PDE's in its universality. A
mathematically simple model of cellular growth is given by {\em
cellular automata.} The idea, due to Ulam, is to fix the spatial
structure by placing cells on a regular grid, and then prescribe a
local rule by which each cell changes with time: the type of a cell at
each generation is determined only by the types of its neighbors at
the previous moment of time. This may simply seem to be a na\"{\i}ve
discrete version of PDE's, but in fact, it produces a bewildering
variety of examples. The most popular example is Conway's {\em Game of
Life}, where cells can be thought of as squares on an infinite
chessboard and each square touches eight neighbors. The update rule
is: a cell wich is either {\em dead\/} or {\em alive\/} remains dead
unless exactly three of its neighbors are alive and remains alive
exactly when two or three of its neighbors are alive. This model is
deterministic, i.e., the initial state of a configuration determines
its evolution for all time. Though the update rule is simple, anything
conceivable can happen given enough time and space! Formally speaking,
it was proved by Conway and Gosper that a universal Turing machine can
be implemented in the Game of Life. Whether such behavior is generic
in a probabilistic sense is unclear. This question appears
to be significant in the modeling of biochemical life.
Numerous variations of the Game of Life have been proposed to mimic
growing colonies of bacteria and natural textures which may be hard to
simulate by other mathematical means [Yaroslavsky].
Some cellular automata exhibit configurations which do not change with
time. Such stationary solutions are essentially equivalent to {\em
tilings,} partitions of a plane region by translates of a
few shapes, e.g., a chessboard tiled by 64 squares. Here again the
deceptively simple definition leads to unexpected beauty such as
honeycombs and Penrose tilings. One also rapidly encounters complex
questions:
{\em Can one decide whether a finite number of plane figures can tile
the plane?} It has been shown that for special sets of tiles large
regions of the plane may be tiled without there being a tiling of the
whole plane, in fact, the problem is undecidable. The point is that a
universal Turing machine can be encoded into a suitable tiling,
just as for cellular automata [Kari].
\smallskip
Another model of cell growth and division was given by
Lindenmeyer. This consists of a finite configuration of cells
connected to each other according to certain well defined rules and a
cell division law which preserves the connection conditions. Once
again, this model may be inherently complicated, though it has not yet
been shown that it can emulate a universal Turing machine
[Cannon, Floyd, Parry]. However,
Lindenmeyer discovered that there are rules which lead to orderly
growth remarkably similar to the development of plants. In
particular, taking a single cell, dividing it in two and joining each
child with its parents yields the standard binary tree, which can be
made to look lifelike by randomly curving its branches.
The Lindenmeyer models produce marvels of computer graphics but their
exponential growth makes them difficult to fit into Euclidean space
(as opposed to hyperbolic space) in which actual plants live. The
dichotomy between unlimited growth and the limitation of space leads
to mechanical stress in growing plants which somehow regulates the
cell division process [Nakielski] [Hejnowicz].
In fact, not all cells can divide indefinitely,
only {\em meristematic\/} ones, those which did not differentiate in
the course of ontogeny [Zag\'orska--Marek].
Besides, when cells divide, they follow
intricate geometric and combinatorial rules reminiscent of the
combinatorial games played in the topology of three dimensional manifolds
[Barlow, L\"uck].
Though this appears complicated it is simple compared to what happens
in a cell. DNA, RNA, proteins, move in harmony tuned by billion years
of evolution. We cannot hope to completely model this incredible
factory but we can attempt to use some of its machinery. For example,
bacteria produce restriction enzymes which cut invading viral DNA at
prescribed locations and by using this process, we can split DNA then
reassemble it back into new forms and topological shapes: lines,
circles, knots, links, graphs [Seeman] [Jonoska] [Head].
The actual process is more involved,
but more and more delicate genetic engineering constructions are
continually being developed--a new technological world of biochemical
geometry is being created. In principle one can encode everything,
once again the universal Turing machine [Paun]. The ``biological computer''
seems within reach and perhaps ultimately, biological nanotechnology
[Seeman].
In our informal investigation of the emergence of patterns we have
discussed a number of problems without touching on a fundamental
question:
{\em Does what we see really exist?} How does the brain
perceive shapes? How do human beings perceive elementary components
in visual stimuli and what are the laws governing how these components
are integrated into a visual whole?
Such questions were addressed at the beginning of this century by the
Gestalt school of psychology. It proposed an analysis of human
perception in which the main factors favoring perceptual grouping are
similarity, contrast, continuation, shapes, proximity, convexity,
symmetry, orientation, and parallelism. These concepts might seem
rather vague but they turn out to capture a number of important
effects both in visual and auditory recognition. The main thrust of
the Gestalt school was a list of criteria leading to a partition of
visual stimulus into $n$ (or even $\log n$) parts, whereas a
na\"{\i}ve division of an image might instead lead to exponentially
many components.
\smallskip
{\em Are the above grouping rules still valid when motion is
considered?} There are indications supporting the fact that dynamic
perception seems to influence the sense of spatial continuity,
chromatic identity, and uniformity of speeds and trajectories as
perceived in static images [Ninio]. It is here that a more subtle study of
orientation, perceptual geometry, and stereoscopy come into play.
Shapes determined during motion must agree with statically determined
shapes and the brain seems to perform a process of
{\em correction\/} to adapt to both perceptions, as well as a process of
{\em synthesis\/} leading to the representation of a global shape
starting from a small number of clues derived from the visual input.
\smallskip
{\em What can we say about the way our brain groups similar objects?}
For example, how does the brain visually characterize animals versus
means of transportation? It seems plausible that there might be a
simple mechanism as opposed to the complex linguistic division that
we use [Thorpe].
{\em What is the information content of a natural image?} How much
does an image tell us? From the point of view of Shannon's
information theory, a fully randomized picture, where the color and
intensity of each pixel in the screen is chosen randomly, carries
maximal information so cannot be compressed. Yet in some sense, such
an image can be described completely by simply stating that it is
``fully randomized.'' More generally, one can introduce equivalence
relations between images which are indistinguishable with respect to a
certain class of observations. Examples are the different equivalence
classes of pictures indistinguishable to human beings in less than one
second and less than five minutes. According to these relations one
can isolate essential patterns in images: those seen instantaneously,
and those seen after several minutes of staring. The first type of
patterns are the most pronounced and are analogous to singularities of
smooth maps which correspond in some sense to the patterns classified
by the Gestalt school. These local forms in conjunction with spline
interpolation and texture generation mechanisms allow up to
$1:15-1:50$ ratio of compression of natural images. This often
surpasses more traditional techniques such as wavelet decomposition
[Briskin, Elichai, Yomdin].
\medskip
This preface does not pretend to be an exhaustive treatment of the
numerous directions of pattern formation, but is rather an
introduction to the articles presented in this collection. We would
like to thank all the speakers who participated in the conference ``La
Formation des Motifs,'' Bures--sur--Yvette, France, on December 2--6,
1997. We are grateful to those speakers who contributed an article to
this volume and especially for writing an expository paper accessible
to a wide audience. Finally, we would like to thank Jean--Michel Morel
and Stephen Semmes for their encouragement and stimulating presence,
and Helga Dernois and Maya Schirmann for their help in the production
of this volume.
\vspace{1in}
\begin{flushright}
Alessandra Carbone\\
Misha Gromov\\
Przemyslaw Prusinkiewicz
\end{flushright}
\begin{flushleft}
{\em Paris, December 30, 1998}
\end{flushleft}
\pagebreak
\begin{center}
{\bf Contents}
\end{center}
\vspace{.5in}
\bigskip
\noindent
{\sc Growth and Form}
\bigskip
\noindent
{\em ?}\\
Przemyslaw Prusinkiewicz
\medskip
\noindent
{\em Growth and form of sponges and corals in a moving fluid}\\
Jaap~A.~Kaandorp and Peter~M.A.~Sloot
\medskip
\noindent
{\em From pseudo-random numbers to stochastic growth models and
texture images}\\
Leonid~P.~Yaroslavsky
\medskip
\noindent
{\em Crystal growth, biological cell growth, and geometry}\\
James~W.~Cannon, William~J.~Floyd and Walter~R.~Parry
\medskip
\noindent
{\em Recent results in aperiodic Wang tilings}\\
Jarkko Kari
\bigskip
\noindent
{\sc DNA and Genetic Control}
\medskip
\noindent
{\em DNA Nanotechnology: from topological control to structural control}\\
Nadrian~C.~Seeman
\medskip
\noindent
{\em 3D DNA patterns and computation}\\
Nata\v{s}a Jonoska
\medskip
\noindent
{\em Circular suggestions for DNA computing}\\
Tom Head
\medskip
\noindent
{\em DNA computing by matching: sticker systems and Watson-Crick automata}\\
Gheorghe P\v{a}un
\bigskip
\noindent
{\sc Reaction Diffusion and Beyond}
\medskip
\noindent
{\em Biological pattern formation as a complex dynamic phenomenon}\\
Hans Meinhardt
\medskip
\noindent
{\em ?}\\
Pierre Coullet
\medskip
\noindent
{\em ?}\\
Elena Budrene
\medskip
\noindent
{\em ?}\\
Yves Couder
\bigskip
\noindent
{\sc Cellular Patterns}
\medskip
\noindent
{\em ?}\\
Peter Barlow and Jacqueline L\"uck
\medskip
\noindent
{\em Plant meristems and their patterns}\\
Beata Zag\'orska--Marek
\medskip
\noindent
{\em Mechanical stress patterns in plant cell walls and their
morphogenetical importance}\\
Zygmunt Hejnowicz
\medskip
\noindent
{\em Tensorial model for growth and cell division in the shoot apex}\\
Jerzy Nakielski
\bigskip
\noindent
{\sc Images and Perception}
\medskip
\noindent
{\em Aspects of human shape perception}\\
Jacques Ninio
\medskip
\noindent
{\em ? }\\
Simon Thorpe
\medskip
\noindent
{\em How can singularity theory help in image processing?}\\
M.~Briskin, Y.~Elichai and Y.~Yomdin
\end{document}