Sandra L. Arlinghaus

The University of Michigan

and

William C. Arlinghaus

Lawrence Technological University

**BACKGROUND**

Background is important not only in color visualization but also in fostering a deep understanding of a variety of abstract concepts. One place to begin any background study of color is with the four-color problem (now, "theorem;" Appel and Haken, 1976). For centuries, mathematicians have concerned themselves with how many colors are necessary and sufficient to color complicated maps of many regions. (Two regions are said to be adjacent, and therefore require different colors, if and only if they share a common edge; a common vertex, alone, is not enough to force a new color.) The answer depends on the topological structure of the surface onto which the map is projected. When the map is on the surface of a torus (doughnut) seven colors are always enough. Surprisingly, perhaps, the result was known on the torus well in advance of the result for the plane (then again, the plane is unbounded and the torus is not). The same number of colors that work for the plane will also work for the sphere (viewing the plane as the sphere with one point removed). However, it was not until the last half of the twentieth century, aided by the capability of contemporary computing equipment to examine large numbers of cases, that the age-old "four color problem" became the "four color theorem." Appel and Haken (1976) showed that four colors are always enough to color any map in the plane (hence the University of Illinois postage meter stamp of "four colors suffice" announcing this giant result).

The world of creating paper maps and publishing them has traditionally been one that is black and white: color processing is expensive and often has been prohibitive. Nonetheless, cartographers, photographers, and others have developed a number of strategies for considering color, independent of how many colors suffice to color a map in the plane. Indeed, Arthur Robinson noted (Robinson, 1960, p. 228),

Thus, color choice and use is typically tailored to "standard" reactions, by a typical observer, to color. The effect of color on an observer is often captured using the following terms as primitive terms: hue, saturation, and luminosity.

- Hue is the term used to describe basic color. Blue, red, and green are all hues. White light passing through a prism is broken up into the spectrum of the rainbow composed of a variety of hues. The basic hues evident in this process are often referred to as spectral hues and these can be used to generate a progression of interstitial hues to fill in between the evident hues.
- Saturation is a measure of the amount of hue in a color; it is also referred to as intensity. Thus brilliant colors are more intense than are light pastels.
- Luminosity is a measure of relative lightness or darkness of a color. Color can be matched against a gray scale to make this measurement. One would expect, for example, that most shades of yellow are lighter than most shades of red.

**COLOR STRAWS AND COLOR VOXELS**

One obvious way to look at color, given two sets of primitives each with three elements, is as an ordered triple in Euclidean three-space. Indeed, that is how color maps are set up in contemporary software such as Netscape, Microsoft Office, and so forth. Hue is measured across a horizontal x-axis (Figure 2) and saturation is measured along a vertical y-axis (Figure 3). The result is a square or rectangle with vertical strips of color corresponding in order to the pattern on the color wheel. A third axis of luminosity (a gray scale) is often seen as a strip to the right of this square (Figure 4). It serves to match the selected color against light/dark values.

Figure 3. Animated color map: shows change in resulting saturation as one moves along the y-axis.

Figure 4. Animated color map: shows change in resulting luminosity as one moves along the z-axis.

An alternate way to visualize all of this is to think of a cube (in 3-space) of 256 units on a side. Label the x-axis as hue, the y-axis as saturation, and the z-axis as luminosity. Then, draw a plane parallel to the base plane (bottom of the cube) at height 120. Fix lines at 180 within that plane: one with hue=180 and one with saturation=180. These two lines trace the paths of the crosshairs, respectively, in Figures 2 and 3. What the cube approach also shows clearly is that there are really a set of voxels (volume pixels) making up the cube: there are 256 straws available for each of the three variables. Since 256=2^8, there are therefore 2^8 * 2^8 * 2^8 = 2^24 = 16,777,216 voxels within the color cube (note the reliance on discrete mathematics and discrete structuring of a normally continuous object).

The notion of looking only at voxel subsets within a single plane parallel to a face of the cube is limiting within this large, but finite, set of possibilities. In choosing sequences of color there may well be reason to follow a diagonal, to tip a plane, or to find various other ways of selecting subsets of color, as a smoothed color ramp, from this vast array. It is to these possibilities that we now turn.

**COLOR RAMPS: ALTERNATE METRICS**

The problem of finding color ramps linking
one color to another can be captured simply as follows. To find a
ramp joining two colors, A and B, first represent each of A and B as an
ordered triple in color voxel space. Then, the problem becomes one
of find a path from A to B. Because one is limited to integer-only
arithmetic, divisibility of distances often will not be precise; thus,
one is thrown from the continuous realm of the Euclidean metric into considering
the non-Euclidean realm of the Manhattan metric (of square pixel/cubic
voxel space). Algorithms for finding shortest paths between two arbitrary
points using integer-only arithmetic will therefore apply to colors mapped
in color space as well as to physical locations mapped on city grids.
To see how these ideas might play out with colors, we consider an example
that will lead to an animated color ramp.

Find a path through color voxel space from (80, 100, 120), shown below
as a medium green

to (200, 160, 60), shown below as a fairly deep purple.

One set of points through which to pass, spaced evenly (not always possible),
is given in the table below. The left-hand column shows values of
hue, the middle column values of saturation, and the right-hand column
values of luminosity.

80 | 100 | 120 |

90 | 105 | 115 |

100 | 110 | 110 |

110 | 115 | 105 |

120 | 120 | 100 |

130 | 125 | 95 |

140 | 130 | 90 |

150 | 135 | 85 |

180 | 140 | 80 |

170 | 145 | 75 |

180 | 150 | 70 |

190 | 155 | 65 |

200 | 160 | 60 |

Figure 5 shows an animation using the path outlined
in the table above. The crosshairs show the movement along the path
while the flashing color in the rectangle below the color map shows the
associated color ramp. Clearly, the choice of path is not unique:
geodesics are not unique in Manhattan space. From this analysis,
we see that the following theorem will hold.

Theorem.

The determination of color ramps joining two colors is abstractly equivalent to finding paths in Manhattan space between two arbitrary points (where geodesics are not unique).

One might wonder what would happen when other color characterization schemes are considered. We suspect that a similar analysis will follow. For, in a related, but not identical, manner the RGB scheme may also be represented as describing color using 3-space. In that scheme, the gray scale comes out as a 45 degree diagonal. Computer scientists offer a color code containing six alpha-numeric characters, appearing in pairs of hexadecimal code that also serve as a 3-space. Generally, though, the various schemes offer only visual slices through this three-dimensional color space along axes or in other "expected" ways. Different vantage points offer different perspectives, however. Pantone color formula guide books offer one physical set of straws by which to probe 3D color space. The theorem above offers a comprehensive mathematical set.

Appel, K., and Haken, W. A proof of the 4-color theorem. *Discrete
Mathematics*, 16, 1976, no. 2 (and related references).

Arthur H. Robinson, *Elements of Cartography*, 2^{nd} Edition,
1960. New York: Wiley.

**RELATED LITERATURE**

Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.
The Hedetniemi Matrix Sum: An Algorithm for Shortest Path and Shortest
Distance, *Geographical Analysis*, Vol. 22, #4, Oct. 1990, pp. 351-360.

Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.
The Hedetniemi Matrix Sum: A Real-world Application, *Solstice*,
Vol. I, No. 2, 1990. http://www.imagenet.org

Sandra L. Arlinghaus, William C. Arlinghaus, John D. Nystuen.
Discrete Mathematics and Counting Derangements in Blind Wine Tastings,
*Solstice*,
Vol. VI, #1, 1993. http://www.imagenet.org

Sandra L. Arlinghaus, William C. Arlinghaus, Frank Harary, John D. Nystuen. Los Angeles 1994--A Spatial Scientific Study, Solstice, Vol. V, #1, 1994. http://www.imagenet.org