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 log2(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 Θ(log2 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 log2(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.
|Copyright © 2005-2016 Quentin F. Stout|