Amorphous computing and MEMs research will enable novel applications of computing coupled with the environment. For example smart paint that detects shadows on a wall, bridge surfaces that detect load, sensors that monitor chemical concentrations in the soil, or an airplane wing covered with sensors and actuators that reduce. In such environments an important goal is to self-organise global information through collaboration between large number of elements, each of which has limited resources and little global knowledge.

For many such applications, coordinates are required to implement sophisticated control laws. A coordinate system can also assist in pattern generation and shape detection. In addition, a coordinate system can also provide global naming and routing to aid in non-local communication. However since the processors have no knowledge of their location or the orientation of their neighbors, the challenge is for the processors to self organise a logical coordinate system that maps, under some affine transformation, to the physical placement of the processors.

A point on a 2-dimensional plane can be uniquely described by its distance from 3 non-colinear reference points. We use this idea of triangulation to form a coordinate system on an amorphous computer. Three non-colinear anchors are chosen and processors determine their distances from each of these anchors.

In an amorphous computer the processors are distributed randomly and
densely on a surface, in this case we consider a 2-d plane. Each
processor can communicate with a small neighborhood of processors
within distance *r* communication radius. Thus there is a maximum
distance associated with a communication hop.

The distance from a source point can be calculated by generating a
**gradient wave**. The source initiates
the wave by sending its neighbors a message with a counter set to
zero. Each recipient remembers the value of the counter and forwards
the message to all its neighbors with the count incremented by
one. Hence a wave of messages propagates outwards from the source.
The wave is prevented from travelling backwards by maintaining the
minimum counter value received and ignoring subsequent messages
containing larger values. This distance wave is essentially a
breath-first-search tree that calculates the shortest path (in hops)
from the source to each processor. However in an Amorphous computer,
we see that the shortest path is usually along the shortest distance
if the average neighborhood size is higher than 15. Hence, as shown in
the picture, the wave forms concentric circles around the source and
the hop count gives a good (albeit coarse) estimate of distance from
the source.

This estimate can be refined through a **
smoothing** step. Each processor computes an average of its
neighbor values and itself. In the 1-d case, a distance wave looks
like a staircase function and smoothing results in the straight line
that passes through the center of the staircase. Other smoothing
functions are being considered. Smoothing (unlike the distance wave)
is very sensitive to local variations in the random distribution.

The three anchors can be chosen by an external stimulus or they can select themselves in a distributed manner - like creating a triangle with a compass. Modifications to the algorithms allow for asynchronicity and bounds on the running time and expected error can be derived.

The error in the measurement stems from three sources - errors in
measuring distance using gradients due to average density, errors
in smoothing due to variations in density and the inherent discrete
nature of the problem. However as we see from the pictures the error
also has a * spatial* component to it. This is because the errors
in the distance from the three anchors does not combine
linearly. Rather the error has a large effect outside the triangle
especially behind triangle vertices. But it has less effect along the
bisectors of the triangle sides and little to no effect at the
centroid of the triangle. This can be derived from the formula for
computing the position from the three distances. On the whole however
the average error is small (less than half the communication radius)
within the triangle. Other methods are also being explored (see paper
by Daniel Coore) and seem to have similar average errors.

The lines represent the error between the logical and actual positions before smoothing. The error (length of the lines) increases outside the triangle. The error inside the triangle is small. This is inspite of the fact that the error in computed distances on average is the same for points inside and outside the traingle. | Therefore increasing the size of the triangle enclosed by the anchors reduces the overall error. However we can see that the resolution is coarse. The lines look like fans - that means many processors believe that they have the same position relative to the anchors |

After smoothing the resolution improves dramatically. However the larger errors (possibly due to edge effects) can not be corrected by smoothing. |
This pictures plots the level curves of function (max (floor absolute x) (floor absolute y)) |