Quentin F. Stout

EECS Department, University of Michigan

**Abstract:**
This paper gives an optimal algorithm for drawing a digital straight line
through two given points in a digitized picture, where the picture is
stored one pixel per processor in the base of a *pyramid cellular
automaton* (PCA). A PCA with an *n x n* base, where *n* is
a power of 2, is a complete 4-ary tree of height log_{2}(n)
where each level
is a two-dimensional mesh. At each node of this pyramid there is a
finite state automaton, where the state of an automaton at time
*t+1* is determined by its state and that of its neighbors at time
*t*. This paper shows that in such a PCA, the straight line can be
marked in Θ(log n) time. Earlier work of Sakoda had produced
an approximate line in Θ(log^{2} n) time.

Note that this problem could be easily solved in the given time if each
processor could store its coordinates and perform arithmetic on numbers
of log_{2}(n) bits in logarithmic time.
The core of the solution is the use
of a new self-organizing data structure, called a *clerk*, in which
Θ(log n) adjacent automata in the base cooperate to simulate
a single processor capable of performing arithmetic on numbers of
Θ(log n) bits in Θ(log n) time.

**Keywords:**
parallel computer, finite state automata, pyramid computer, digital line,
self-organizing, parallel algorithms

Complete paper.
This paper appears in *Information Processing Letters*
**15** (1982), pp. 233-237.

- The primary reference for clerks and another paper utilizing them. Both of these concern cellular automata arranged in a grid.
- My papers in parallel computing, and an overview of my research
- An explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources

Copyright © 2005-2016 Quentin F. Stout |