Amorphous Shape Mapping

The complete thesis is available as: PDF and text.
If these don't work for you, email me and I can generate a new format or send you a paper copy.

The shapsim simulator and analysis software, compilable under Unix, is available as a gzipped tarball.

Abstract

Research in amorphous computing studies asynchronous, identically programmed, and decentralized agents performing computations. Research in this area has produced methods for taking existing descriptions of arbitrary shapes and amorphously regrowing the approximated shape. These methods assume descriptions of shapes to be in a form accessible to traditional computers; however, using traditional computers to produce such descriptions of shapes in the physical world is a problematic and generally difficult task.

The objectives of this thesis project were to develop and analyze a method of generating a description, accessible to traditional computers, of an arbitrary two-dimensional shape by amorphously mapping the desired shape. Three interesting types of shape descriptions generatable from an amorphous shape mapping computer, connectivity, point sampling, and polygonal, are presented and discussed. With intended descriptions and uses in mind, the developed method's assumptions are stated and discussed and the primitive cell actions are given. The developed cell program's three stages are then detailed: placing the cells, mapping the region, and transferring the gathered data to a transferring computer. This thesis project's focus is mapping the given region.

Simulations of the three types of shape descriptions are described and results presented and described. Analytical results were derived for ensuring complete region description. The developed amorphous shape mapping method is able to accurately map the tested shapes using relative cell location information obtained as cells receive messages from other nearby cells. Experiments show that even cells without relative location sensing abilities can produce descriptions of the mapped shapes.

Maintained by frost@cs.virginia.edu
Last Modified: May 19, 2004