Basic Principles of the CircleNetwork Representation
Suppose that we construct a network of partiallyoverlapping circles, in which every circle stores a representation of the relative positions of directlyadjacent circles. In this event, instructing any one of these circles to recursively grow its adjacent circles would result in the emergence of the desired global structure. We can imagine how the process of growing circles at specified locations might be accomplished by cells: first, a particular cell would grow a circle around itself to a specified radius; next, cells in this circle that are destined to become centers of adjacent circles would grow circles around themselves as well. The desired global shape would emerge from this recursive behavior.
ThreeStep Compilation
The compilation procedure involves three phases:
I. Finding an efficient circle covering (initial network)
II. Constructing a tightlylinked network of circles by introducing intermediate circles
III. Specifying position information in terms of gradient ratios
I. Finding an Efficient Circle Covering
This first step involves specifying a set of partiallyoverlapping circles that completely cover the input shape. I have implemented two methods for selecting circles: Method #1: Tiling This method first imposes a gridlike structure ("tiling") on the input shape. The tiling algorithm essentially locates the largest squares whose circumscribed circle would fit entirely within the shape, and later produces smaller squares in order to completely cover the shape. The circle network is then comprised of each internal square's corresponding circumscribed circle. Method #2: Hill Climbing The second method uses a hillclimbing algorithm to locate circles. Given a random point in shape, the heuristic function is a measure of how much previouslyuncovered area that the largest possible circle (centered at this point) will cover. As expected, the second method is significantly more efficient.

Circles found by method #2.The input shape is

The process of amorphous circle growth proceeds outward from a designated center cell. However, in the network generated by the first step, the center of an adjacent circle may not lie in the interior of a previouslygrown circle. This introduces difficulties, given the system of triangulation and gradientmessaging among the cells. Therefore, at this stage sequences of intermediate circles are inserted between each pair of circles found in the previous step. The center of each circle in the sequence is constrained to lie within an adjacent circle. We have created, in effect, a bridge between the main circles that facilitates connected growth.
III. Representing Positions of Adjacent Circles
Lastly, we reach the question of encoding the relative positions of adjacent circles in the network. Communication between cells is accomplished via a form of messaging that bears similarities to the spread of chemicals whose concentrations relate distance information during biological growth. Therefore, it is helpful to specify position as a set of gradient values exuded from particular cells ("reference cells") in a circle.
In this step we introduce four reference cells, cells whose primary task is to exude a gradient. These cells essentially provide a coordinate system for each circle, allowing us to specify positions within a circle in terms of distances from each reference cell. The positions of an adjacent circle's center and two reference points are indeed specified in this manner.
Qualities
The circlenetwork representation exhibits the qualities of scale and rotation independence, as all directional and position information is specified in a purely relative manner. In addition, the bidirectional, tightlyconnected network promotes the regeneration of missing areas should cell disappearance occur during or after the growth process. As all information necessary for growing the entire shape is encoded within the network, persistent attempts of circles to recursively grow their adjacent circles ensures that the structure will be maintained.
<back
next>