# Dotting the dot map, revisited.

Introduction

Cartographers make dot maps to show details in the spatial variation of geographic phenomena such as human populations or agricultural crops. Dot maps show the geographic distribution of a phenomenon by placing dots representing a certain quantity of the phenomenon where they are most likely to occur. The fundamental steps in dot mapping are selecting the dot size, determining the dot unit value (the quantity of phenomenon represented by a dot), and placing the correct number of dots in a manner that accurately reflects density differences within the geographic distribution.

Selecting dot size is a subjective decision based on visual perception limits and aesthetics. Robinson et al. (1995, p. 498) note that dots too small make the distribution appear sparse and insignificant, whereas dots too large give an equally erroneous impression of excessively high density. Once a dot size has been selected, the dot unit value can be selected either by trial and error, or with the aid of a nomograph devised sixty years ago by J. Ross Mackay (1949) in an article titled Dotting the Dot Map. The 1949 nomograph (Figure 1) is in English measurement units, although cartographers may be more familiar with the more recent metric-unit homograph published in the Elements of Cartography (Robinson et al. 1995, pp. 499-500) and Thematic Cartography and Geovisualization (Slocum et al. 2008, pp. 331-332).

Cartographers use the Mackay nomograph to find the number of dots per square inch (or [cm.sup.2]). This requires three steps. First, draw a straight line from the origin to the selected dot diameter in inches (or cm) found on the radial scale of dot diameters. Next, mark where the line crosses the "zone of coalescing dots." Finally, draw a line vertically downward from this mark to the horizontal axis showing the number of dots per square inch (or [cm.sup.2]) that will begin to coalesce for the selected dot size. For example, 2-point dots with 0.028-inch (0.71 mm) diameters begin coalescence at 750 dots per square inch (116 dots per [cm.sup.2]). This dot density value is used with the map area of the highest density data collection unit and the total quantity in this unit to determine the dot unit value. For instance, 0.028-inch dots would coalesce in a 0.25 [in.sup.2] data collection unit with 187,500 people if the dot unit value were 187,500 people / (750 dots per [in.sup.2] x 0.25 [in.sup.2]) = 1000 people per dot.

The Mackay nomograph has guided cartographers for 60 years of creating maps manually, but it has serious drawbacks in the modern age of computer cartography. The first limitation is the range of dot diameters given on the radial scale. Dot sizes available in ESRI ArcMap software, for example, range from 0.5 to 11 Postcript points, where a Postscript point is exactly 1/72nd (0.0139) inch (.353mm). Dots of 0.5-points and those larger than 5 points are rarely used in dot mapping, but commonly used 1-point dots fall off the lower right side of the nomograph completely below the "zone of coalescing dots." The issue here is that 1.0 point and smaller dots were very difficult to create manually in a consistent manner with ink pens, a non-issue in the world of digital creation of scalable circles by computer software.

[FIGURE 1 OMITTED]

The second drawback to the nomograph is the nature of the "zone of coalescing dots" shown on it. One would expect a zone to be shown by a gray-tone area or something similar on the nomograph, but only a wave-like line of text demarcates the zone. The irregular undulations in the curving text are also puzzling. Mackay explains in a footnote that he determined the "zone of coalescing dots" by drawing dots in squares so that each dot was placed in the largest available space until the entire square was filled with dots that just began to coalesce. This type of space filling method suggests a much smoother curve for the "zone of coalescing dots" text, since the number of dots required to fill the space should quadruple as the dot diameter is halved.

The third and perhaps most serious drawback to the nomograph is its mathematical basis. Mackay does not discuss how he derived the two axes and radial scale that comprise the nomograph, but its mathematical basis can be seen by closely studying values found on it. For example, a 0.098-inch diameter dot has an area of 0.000616 [in.sup.2], which, when multiplied by 750 dots per [in.sup.2], gives an area of 0.46 [in.sup.2], the aggregate area of dots found by extending a horizontal line from the mark at the "zone of coalescing dots" leftward to the vertical axis. Since the vertical and horizontal scales are linear and the lines from the origin to the radial scale are drawn straight, any point on a radial line relates dot density and aggregate area of dots by the equation: dot area x dot density = aggregate area in dots. The nomograph, then, is a graphical representation of this equation, with a "zone of coalescing dots" overlaid.

The notable thing about the equation defining the nomograph is that it is valid only if no dots overlap. Digital implementations of Mackay's method of dot placement, such as Lavin's (1986) quasi-random dot placement algorithm, create a set of non-overlapping dots that appear placed in a random manner. This is not, however, how dots are placed using computer mapping algorithms--such as Dutton's (1978) pioneering effort--which determine the coordinates of dot centers based on random numbers. Consequently, the Mackay nomograph is not appropriate for determining the dot unit value when dot placement is based on computer-generated random numbers that result in overlapping dots if the numbers truly are random.

The purpose of this paper is to revisit Dotting the Dot Map and develop a method to determine dot density and aggregate dot area for computer-generated, randomly placed dots that may overlap. A new graphical aid for selecting dot unit value results when these dot densities and aggregate areas are plotted for dots of different sizes. The method relies on modeling the aggregate area of dots and amount of dot overlap using basic equations from probability theory.

Random Dot Placement and Probability Theory

Dotting the dot map randomly is similar to the random packing of circles in a square (Solomon 1967). Imagine randomly dropping, one by one, identical circular coins into a unit square, say 10 by 10 inches or 10 x 10 cm in area. The problem is finding the total aggregate area covered by coins, knowing that some of the coins dropped less than a diameter apart will overlap. In probability terms, the unit square is a probability of 1.0, and each coin is an identical probability event [E.sub.i] whose area as a proportion of the unit square is its probability of occurrence P([E.sub.i]). Randomly dropping each of n coins can be thought of as an independent probability event, so that the aggregate area is the union of independent probability events with the same chance of occurrence P([E.sub.i]) = P([E.sub.j]) = ... = P([E.sub.n]). The union of n events is given by the unification equation for independent probability events (Suhov and Kelbert 2005):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The first term in the equation is the sum of the n event probabilities. The second term is the sum of the intersections of the number of combinations of events taken two at a time (by analogy, the overlap area of pairs of coins), and so on until the last term, which is the intersection probability for the entire n events.

Turning the coins into n identical dots whose area relative to a 1.0 x 1.0 cm unit square is the probability of occurrence p = [E.sub.i], the aggregate dot area is predicted by the unification equation rewritten as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [n.summation over (i=1)] p = np and the number of combinations in each summation are given by n!/k!(n - k)!

so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The unification equation expands with the number of dots, but raising small numerical values of p to very large powers is computationally unstable. Additionally, it is unlikely that a large number of dots will overlap simultaneously. For these reasons, the full unification equation was truncated to 10 terms:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This truncated equation does not affect the values computed for (95 percent of area covered by dots) for up to 1000 points.

Using the Unification Equation with Different Dot Sizes

A C-language program was written to calculate aggregate area in dots from the truncated unification equation for the nine dot sizes listed in Table 1. The p value (dot area) for each dot size was held constant as the number of dots was increased in increments of ten until either an aggregate dot area of 0.9 (90 percent covered by dots) or a maximum number of 1000 dots was reached. The aggregate areas predicted with increasing numbers of dots are graphed as data points in Figure 2 for the nine dot sizes ranging in diameter from 1 to 5 points. Drawing straight lines between data points shows the smooth curves produced by the truncated unification equation.

This new dot-density selection graph is similar to the Mackay nomograph in that dot density, aggregate dot area, and dot size are being related quantitatively, but there is no "zone of coalescing dots." The white horizontal and vertical lines in Figure 2 show how the graph is used to obtain dot densities for 1, 1.5, and 2 point dots with an aggregate area in dots of 0.46 (46 percent).

Notice that for a 2-point dot size about 160 dots per [cm.sup.2] are needed to reach this aggregate area, whereas the Mackay nomograph shows that 116 non-overlapping dots have this same aggregate area. This difference of 44 dots gives an indication of the amount of dot overlap that occurs when dots are placed randomly in an area. Also, notice that almost exactly four times the number of dots (154 and 627) is needed to obtain the same aggregate area of 0.46 when the dot diameter is halved from 2 to 1 point. Since the smaller dot is one-quarter the area of the larger, an inverse proportionality between dot density and dot area should exist for all dot sizes and aggregate dot areas.

Replacing the more nebulous "zone of coalescing dots" that guides dot density selection on the Mackay nomograph with a quantitative measure of dot coalescence improves the graph in Figure 2. Adding the amount of dot overlap for different aggregate dot areas is one possibility that is easy to implement. The proportion of dot overlap for n dots of the same size is simply the area covered by the dots with no overlaps minus the aggregate dot area computed from the truncated unification equation. Multiplying this difference by 100 gives the dot overlap percentage, expressed mathematically:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 2 OMITTED]

The percent-dot overlap equation was programmed in the same manner as the unification equation. The p value (dot area) for each dot size was held constant as the number of dots was increased in increments of ten until either a 100 percent dot overlap or a maximum number of 1500 dots was reached. Dot overlap percentages predicted with increasing numbers of dots are graphed as data points in Figure 3 for the nine dot sizes ranging in diameter from 1 to 5 points. Notice that, like the aggregate area data, four times the number of dots is needed to obtain the same percent dot overlap when the dot diameter is halved from 2 to 1 point. Once again, an inverse proportionality between dot density and dot area should exist for all dot sizes and aggregate dot areas since the smaller dot is one-quarter the area of the larger.

[FIGURE 3 OMITTED]

Because the two equations and their graphs share this inverse proportionality between dot density and aggregate dot area, the horizontal lines of white squares on the dot overlap graph should be horizontal lines when overlaid on the aggregate dot area graph, as is seen in Figure 4. We can see this mathematical constancy by examining the dot density values in Figures 2 and 3 over a range of dot diameters for a given percent dot overlap. For example, looking at the dot density values in Figure 3 for a 40 percent dot overlap and dot diameters of 1.5, 2.0, 2.5, and 3.0 points, the graph shows that approximately 480, 275, 175, and 125 dots per square centimeter are required to achieve a 40 percent dot overlap. Turning to Figure 2, we see that the aggregate area of dots for each of these dot densities is very close to 0.63. The horizontal line in Figure 4 at 0.63 for a 40 percent dot overlap is a graphic expression of this constancy. One can now select a dot density based upon a desired percent overlap with a corresponding aggregate dot area. The more mathematically precise measure of dot coalescence replaces the "zone of coalescing dots" on the Mackay homograph.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Testing the Aggregate Dot Area and Dot Overlap Equations

A method was developed to place specific numbers of randomly placed black dots of a certain diameter into a unit square so that the aggregate area in dots could be measured and later compared with the aggregate area predicted by the truncated unification equation. Figure 5 shows the steps involved in creating the dots and measuring their aggregate area.

* A C-language program was written to generate random (x,y) coordinates for dot centers. The system clockwas used as the seed value for each set of coordinates, and the numbers generated were scaled from 0 to 10.0 mm to obtain high-precision coordinates falling within a 1 x 1 cm unit square.

[FIGURE 6 OMITTED]

* The computed random dot center point coordinates were imported into a Microsoft Excel spreadsheet in separate columns for the x and y coordinates. The two columns were used to create a scatterplot of the dot coordinates, such as for the 250 dots shown by small diamonds.

* The Excel scatterplot was copied into Macromedia Freehand 10, where the diamond symbols were converted to black dots of the desired diameter, scaled exactly to a 1 x 1 cm unit square. Dots extending outside the edge of the square were duplicated and wrapped around the opposite side of the square (this step is not shown in Figure 5) so that the entire dot fell within the square, with possible overlap from other dots at the edge of the square.

* The Freehand drawing with the wrapped dots was imported into Adobe Photoshop as a raster image file. The raster drawing was clipped to the edges of the unit square, as indicated by the partial dots seen along the edges. The Histogram function in Photoshop was then used to determine the percentage of the drawing that was not the white background. Dots were displayed almost entirely in black, but with a few lighter gray edge pixels. Consequently, the percentile of the lightest gray tone on the image was used as the value for the aggregate dot area. For example, the lightest gray tone for the circular dots in the unit square shown at the bottom of Figure 5 had a value of 191, and 79.14 percent of the pixels in the square were at or lower than (darker than) this value.

The accuracy of the truncated unification equation was investigated by using the above method to measure the aggregate dot areas for unit squares containing the number of dots predicted to overlap by 10 percent, 20 percent, 30 percent, 40 percent, and 50 percent for each of the nine dot sizes randing diameter from 1 to 5 point. The small white squares in Figure 3 are these 45 combinations of dot overlap and dot size. The number of dots for each of the 45 unit squares was read from the horizontal axis of Figure 3. These values are printed in Figure 6, at the top of each unit square. In addition to serving as the basis for aggregate dot area measurement, this diagram serves as a second form of dot selection guide.

Figure 4 shows the simple linear mathematical relationship between predicted percent dot overlap and aggregate area in dots. The horizontal white lines of constant percent dot overlap have been redrawn in Figure 7 as horizontal black lines placed on the vertical axis of aggregate dot area as in Figure 4. Measured aggregate dot areas for each of the 45 unit squares in Figure 6 are plotted as colored dots in Figure 7, with a different color for each percent dot overlap level. The measured aggregate area in dots appears to agree closely with the predicted aggregate areas for small dot diameters having large numbers of dots in the unit square. Conversely, predicted and measured aggregate dot areas diverged by up to five percent as the dot diameter increased and fewer dots were placed in the unit square.

[FIGURE 7 OMITTED]

The noticeable variation between measured and predicted aggregate dot areas for larger diameter dots may indicate the degree of inaccuracy in the truncated unification equation since the equation is deterministic, yet based on probability. Alternatively, the differences may be an indication of variation in the sets of random numbers generated. To investigate if one, or both, possibilities are at play, 25 sets of 55 random coordinates were generated, made into a scatterplot in Excel, and converted in Freehand to 3-point-diameter dots in a unit square (Figure 8). The only deviation from the aggregate dot area measurement method used above was that dots extending outside the unit square were not wrapped to the opposite side, due to the effort involved in doing so, as well as the minimal effect (a few tenths of a percent) of not doing so on the aggregate dot areas. Aggregate areas measured from the dots in Figure 8 should be only slightly higher than if the protruding edge dots were wrapped, since a very small amount of the wrapped pieces of dots overlap with other dots close to the edge of the unit square.

Aggregate dot areas as a proportion of the unit square are printed at the top of each square. The 25 aggregate area proportions vary from 0.363 to 0.406, with an average area proportion of 0.389. This is very close to the 0.385 aggregate dot area proportion predicted by the truncated unification equation. It is possible that if the protruding portions of edge dots in each square were wrapped to the opposite edge, the measured and predicted aggregate dot areas would match within one-tenth of a percent. Consequently, the 0.42 aggregate dot area in Figure 7 is anomalously high relative to the 25 unit squares created to obtain an average aggregate dot area. Equally important, the variation in measured aggregate dot area among the unit squares shows that the truncated unification and similar probability-based deterministic equations are highly accurate only if the predicted aggregate area is compared with the average aggregate area for a large number of unit squares.

Pseudo-Random Dot Placement

The dot-density selection graph in Figure 2 and dot density examples in Figure 4 give mapmakers tools for wise selection of dot densities for different dot sizes when dot placement is completely random. However, there is an important issue with truly random dot placement--cartographers historically have not placed dots in a true random manner when creating dot maps manually. Mackay was correct in noting that dots were placed manually to fill an area with dots that did not overlap. This dot placement method can be termed pseudo-random placement with a maximum dot overlap constraint.

The Mackay nomograph was devised for pseudorandom dot placement with zero dot overlap, which in probability terms is mutually exclusive random dot placement. The aggregate area in dots can be thought of as the union of n identical, mutually exclusive events with probability p equal to the proportion of the dot area relative to a unit square, or n x p. It is also possible to have pseudo-random dot placements with maximum dot overlaps intermediate between mutually exclusive and completely random, as shown in Figure 9. Maximum dot overlap could be set to 10 percent, for example, meaning that 10 percent or less of the area of one dot overlaps a second dot. Notice that small clusters of overlapping dots become more numerous as the maximum dot overlap increases.

[FIGURE 8 OMITTED]

Implementing a maximum dot overlap constraint depends on finding the relationship between overlap area and the distance between dot centers. The mathematical problem is finding the lens area for two circles of radius R whose centers are separated by distance d (Figure 10). The following is the lens area equation giving the proportion of dot overlap for the circles (Weisstein 2008):

[Area.sub.Lens] = 2[R.sup.2] [cos.sup.-1] (d/2R) - 1/2 d[square root of 4[R.sup.2] - [d.sup.2]]

which is mathematically similar to the equation used in Lavin's (1986) circle segment overlap computation procedure. If a unit circle (R = 1.0) is used and d is given as a proportion of the circle radius, the equation simplifies to:

[Area.sub.Lens] = 2[cos.sup.-1] (d/2) -1/2 d[square root of 4 - [d.sup.2]]

where d ranges from 0 (complete overlap) to 2 (complete separation). When d = 0, the computed lens area is [pi], so that the proportion of a dot covered by the lens (the dot overlap proportion) is

[Area.sub.Lens]/[pi]

and the dot overlap percentage is

[Area.sub.Lens]/[pi] x 100

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

Dot overlap proportions for dot center spacings (d) from 0 to 2 are graphed in Figure 11. The line shows an essentially constant decrease in dot overlap with equal increases in dot spacing for d values from 0 to around 1.4. As the dot center spacing increases from 1.4 to 2.0, the dot overlap proportion decreases nonlinearly, with progressively larger increases in dot spacing producing constant decreases in dot overlap proportion. For example, the dot center spacing is 1.0 for a dot overlap proportion of 0.4, 1.2 for a 0.3 overlap, 1.4 for a 0.2 overlap, but 1.63 for a 0.1 overlap proportion and 2.0 for 0 dot overlap.

The dot center spacing values read from the graph were central to the creation of a pseudo-random dot placement method as a modification of determining dot center coordinates in a strictly random manner using a random number generator. The computer algorithm for pseudo-random dot coordinate calculation with a maximum dot overlap constraint involves the following steps:

* Define the total number of dots needed and the minimum separation distance (d) between dot centers.

* Create two initially empty arrays to hold the x and y coordinates to be generated.

* Use a random number generator to create the (x,y) coordinate for the first dot center and store the x and y values in the first row of the arrays.

* Generate a second (x,y) coordinate and use the Pythagorean Theorem to compute the distance between the two coordinates.

* If the computed distance is greater than d, place the x and y values in the second row of the arrays. If the computed distance is less than d, delete the coordinate and generate a new second coordinate. Repeat the minimum distance check until a coordinate is found with a separation distance greater than d. Place the x and y values in the second row of the arrays.

* Repeat the minimum separation distance check for the third and additional coordinates generated, checking that the minimum separation is maintained for all coordinates previously placed

in the arrays. Stop the procedure when the desired number of dot coordinates are found, or when a maximum number of tries (new dots generated) is reached.

* A C-language program was written to implement the pseudo-random dot placement algorithm for dot sizes from 1 to 2.5 points and maximum dot overlap proportions of 0, 0.1, 0.2, and 0.3. This program created data on the relationship between dot density and aggregate area in dots as the maximum allowable dot overlap increases. The number of dots was incremented in steps of 25 or 50, and a maximum of 32,000 tries was set for each program run. Once the arrays of pseudorandom center coordinates were filled with the desired number of dots, distances from each dot to all others were computed, and the lens area and then the dot overlap proportion were calculated for all separation distances less than the dot diameter. Summing the computed dot overlap proportions gave the total dot overlap area from which the aggregate proportion or percentage of area covered by dots could be calculated. The calculations were based on dot pair overlaps, with the assumption that triple, quadruple or higher dot overlaps were insignificant.

[FIGURE 11 OMITTED]

[FIGURE 12 OMITTED]

Figure 12 shows aggregate dot areas computed for 1 point dots in increments of 50 with maximum dot overlaps of 0 percent (mutually exclusive dots), 10 percent, 20 percent, and 30 percent, along with completely random dots in increments of 25. Each data point is the average aggregate area in dots for 30 repetitions of the dot placement method, where the desired number of dots was obtained for each repetition in less than 32,000 tries.

The aggregate dot area data points for mutually exclusive dots form a straight line as there is no dot overlap. Data for dots placed with the 10 percent, 20 percent, and 30 percent maximum dot overlap constraint form smooth curves increasing in curvature with greater maximum dot overlap. Presumably, the curvature will increase with maximum dot overlaps greater than 30 percent until the totally random dot placement curve is reached with 100 percent allowable dot overlap.

Notice that the aggregate area in dots obtained in less than 32,000 tries increases from about 0.45 to 0.85 as the maximum dot overlap increases from 0 to 30 percent. The maximum aggregate dot areas for mutually exclusive placements were examined further by graphing different dot densities against the average number of tries for 30 repetitions of the method required to obtain dot densities from 25 to 475 dots per [cm.sup.2] in increments of 25 dots (Figure 13). The data points form an exponential curve that appears to reach a limit of 0.5 aggregate dot area at a dot density of 500 dots per [cm.sup.2]. This 0.5 aggregate dot area limit for mutually exclusive dot placement helps explain the "zone of coalescing dots" on the Mackay nomograph, as the words were placed just above and below the tick mark at 0.5 aggregate area in dots for 2 point and larger dots. This similarity between maximum dot density and the placement of the "zone of coalescing dots" is not surprising as Mackay based his nomograph on mutually exclusive dot placement. That the "zone of coalescing dots" rapidly decreases to an aggregate dot area of around 0.25 for smaller dots is surprising in light of the 0.5 aggregate dot area limit found for 1-point dots.

[FIGURE 13 OMITTED]

The four graphs in Figure 14 show the result of applying the pseudo-random dot placement method to 1, 1.5, 2, and 2.5-point size dots. The horizontal dot density axis has been scaled in each graph to illustrate the similarity in the curves formed by the data for the five different degrees of maximum individual dot overlap from mutually exclusive to completely random. That the curves are essentially identical when scaled in this manner becomes apparent when relative dot area, dot density, and aggregate dot area is compared for different dot sizes. For example, 2-point dots have four times the area as 1-point dots, and the graphs for these dot sizes show that it takes four times the number of 1-point dots to obtain the same aggregate dot area. This relationship is true regardless of the maximum amount of individual dot overlap, and similar proportionalities exist for 1.5 and 2.5 point dots. These graphical similarities and proportionalities suggest that a general equation can be devised relating dot size, dot density, and maximum individual dot overlap. Such an equation predicting aggregate dot area allows us to specify the proportion of an area covered by dots for a given dot density and maximum allowable dot overlap proportion. The ability to mathematical predict aggregate area in dots in a single equation is crucial to developing software that will perform dot mapping in a pseudo random manner.

A general equation predicting aggregate area in dots for mutually exclusive, pseudo-random, and completely random placement of different size dots should be a combination of the equations for mutually exclusive and completely random dot placement, that is:

[Area.sub.Agg]. = np

and

[Area.sub.Agg] = np - n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10]

One possibility is that the general equation is a weighted combination of the two equations above, or:

[Area.sub.Agg] = knp + (1 - k){np - n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10])

where k is a weight ranging from 0 (completely random dot placement) to 1 (mutually exclusive dot placement). This equation simplifies to:

[Area.sub.Agg] = np + (1 - k)(- n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10])

[FIGURE 14 OMITTED]

However, to what is the weight k proportional? Two possibilities related to the maximum allowable individual dot overlap come to mind. The first is that k is directly proportional to the maximum allowable dot overlap, or k = 1.0--maximum dot overlap proportion. A second possibility is that k is proportional to the minimum spacing d between dot centers for the maximum allowable dot overlap. In this case, k ranges from 0.0 for randomly placed dots with a minimum spacing of 0, to 1.0 for mutually exclusive dots with centers separated by a minimum of one dot diameter. To the author's knowledge, neither possibility has a firm basis in probability theory, but the second was found to fit the data points better (about twice as good a fit overall).

[FIGURE 15 OMITTED]

Figure 15 shows the closeness of fit between aggregate areas in dots predicted by the general equation and measured for four dot sizes from 1 to 2.5 point and for five maximum allowable dot overlaps from 0 (mutually exclusive) to 100 percent (totally random). The exact fit of equation and data for mutually exclusive dot placement is expected since the aggregate dot area for n dots placed in a mutually exclusive manner is predicted exactly by the linear equation [Area.sub.Agg]. = np. The extremely close fit between average aggregate dot area for many runs of the program to fill a unit square with completely random dots and the aggregate area predicted by the truncated unification equation was described previously. Notice the very close fit between the average measured aggregate dot areas and those predicted by the general equation for 10 and 20 percent maximum dot overlaps. This very close correspondence is also found for the 30 percent maximum dot overlap data for up to 0.6 aggregate area in dots, after which there is a progressively larger difference between predicted and measured aggregate areas.

Piecewise and Continuous Pseudo-Random Dot Placement

The aggregate area in dots data graphed in Figure 15 show maximum achievable aggregate areas of around 0.5 for mutually exclusive dot placement, around 0.6 for placement with a 10 percent maximum dot overlap constraint, around 0.8 with a 20 percent maximum dot overlap constraint, and around 0.85 with a 30 percent maximum dot overlap constraint. The fact that up to 85 percent of an area can be covered by dots that overlap by no more than 30 percent suggests a piecewise approach to pseudorandom dot placement where high aggregate dot areas can be created with fewer dots and less dot clustering than when using completely random dot placement to achieve the same aggregate dot areas. The basic idea is to determine a range of aggregate dot areas that can be achieved with a reasonable number of tries for a limited number of maximum dot overlap increments.

One approach to defining the steps in a piecewise approach to dot placement is to create graphs relating dot density and the average number of tries needed to reach the dot density. Graphs of these data for 1-point dots with 0 percent, 10 percent, 20 percent, and 30 percent maximum dot overlap are shown in Figure 16. A 5,000-try limit for obtaining the dots was used on each graph to insure that dot creation would be rapid. The right vertical yellow line on each graph shows this limit. The left vertical yellow line on the 10 percent, 20 percent, and 30 percent maximum dot overlap graphs is the maximum aggregate area in dots reached with the previous maximum dot overlap constraint.

The dot density ranges between these yellow lines define the steps in a piecewise approach to pseudo-random dot placement. The upper left graph for mutually exclusive dot placement shows that dot densities of up to 440 dots/[cm.sup.2] and corresponding aggregate dot areas of up to 0.44 can be obtained in less than 5000 tries. With a 10 percent maximum individual dot overlap constraint, the dot density obtained in less than 5000 tries increased to 630 dots/[cm.sup.2] and an aggregate dot area of 0.58. Similarly, maximum dot densities of 840 and 1.150 dots/[cm.sup.2] (aggregate dot areas of 0.72 and 0.82)were reached within 5000 tries for dot placement with 20 percent and 30 percent individual dot overlap constraints. These four maximum dot density and aggregate dot area values were the information needed to create for 1-point dots for the piecewise pseudo-random dot density selection guide shown in Figure 17. The density selection guides for the larger-diameter dots were created in the same manner.

The four maximum dot overlap steps used in pseudo-random placement of different size dots suggest that continuous mathematical functions can be found which give a maximum dot overlap for each dot density. Such an equation was found for 1-point dots by first drawing the dot overlap steps from Figure 16 on graph paper as steps ten squares high and the width of their dot density range. A smooth curve was then drawn on the graph paper roughly diagonally through the steps so that the number of tries to reach each dot density was kept less than 5000. Curve fitting software was then used to find the following polynomial equation that best fit the hand-drawn curve relating maximum individual dot overlap (percent) and dot density (N): percent = 0.008N + [0.00002N.sup.2]. This function is graphed as a solid blue line in Figure 18, along with a solid red line showing the aggregate area in dots for each dot density as predicted by the general equation relating dot density and aggregate area in dots. Similar functions can easily be determined for other dot sizes.

Maximum percent dot overlap and aggregate dot area values were read from Figure 18 for 23 dot density steps in increments of 50 dots ranging from 50 to 1150 dots/[cm.sup.2]. These values provided the information needed to make a pseudo-random dot density selection guide for 1-point dots with continuously varying maximum dot overlap (Figure 19). This dot density selection guide and similar guides made for larger dot sizes not only allow map makers to select a desired amount of dot coalescence from a set of example areas, but also provide graphic examples of how pseudo-randomly placed dots will appear in lower-density sections of the dot map.

[FIGURE 16 OMITTED]

[FIGURE 17 OMITTED]

Conclusion

Revisiting Dotting the Dot Map has brought us in a full circle. Carefully studying the Mackay nomograph uncovered several shortcomings related to its use in modern cartography, the most severe being its inappropriateness for computerized dot mapping where dots are placed randomly with no constraint on the amount of individual dot overlap. Investigating the mathematical nature of rigid random packing of circles in a unit square resulted in modeling completely random dot placement with a truncated form of the unification equation from probability theory.

This equation was found to predict the aggregate area in dots for different dot sizes and dot densities accurately. However, the numerous small clusters of dots characteristic of completely random dot placement led to the realization that cartographers have traditionally placed dots on maps in a pseudo-random manner to minimize the overlap between individual pairs of dots.

[FIGURE 18 OMITTED]

[FIGURE 19 OMITTED]

Mackay devised his nomograph for this type of dot placement, and the mathematical nature of pseudo-random packing of circles in a square with maximum overlap constraints was investigated. A general equation was devised to predict the aggregate area in dots for the complete range of maximum dot pair overlaps from mutually exclusive to completely random. The exact mathematical form of this equation was not found in the probability literature. However, it is possible that the general equation is a linear combination of the equations for mutually exclusive and completely random probability events. Further study by probability experts into the mathematical nature of probability for events that grade progressively from mutually exclusive to completely random may give the mathematical insight needed to refine the general Equation (*) Nevertheless, Mackay would undoubtedly find the sequence of pseudo-randomly placed dots in the piecewise and continuous dot density selection guides to look both familiar and appropriate for dot maps created by modern computer mapping and geographic information systems.

REFERENCES

Dutton, G. 1978. DOT MAP program summary and portfolio. Laboratory for Computer Graphics and Spatial Analysis. Cambridge, Massachusetts: Harvard University.

Lavin, S. 1986. Mapping continuous geographical distributions using dot-density shading. American Cartographer 13(2): 140-50.

Mackay, J.R. 1949. Dotting the dot map: An analysis of dot size, number, and visual tone density. Surveying and Mapping 9(1): 3-10.

Robinson, A.H., J.L. Morrison, RC. Muehrcke, A.J. Kimerling, and S.C. Guptill. 1995. Elements of cartography, 6th ed. New York, New York: John Wiley & Sons.

Slocum, T.A., R.B. McMaster, F.C. Kessler, and H.H. Howard. 2008. Thematic cartography and geovisualization, 3rd ed. Upper Saddle Rives, New Jersey: Prentice Hall Series in Geographic Information Science.

Solomon, H. 1967. Random packing density. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Volume 3: Physical Sciences. Berkeley, California: University of California Press. pp. 119-34.

Suhov, Y., and M. Kelbert. 2005. Probability and statistics by example. Volume 1, Basic probability and statistics. New York, New York: Cambridge University Press.

Weisstein, E.W. 2008. "Circle-circle intersection." From MathWorld-A Wolfram Web Resource. [http:// mathworld.wolfram.com/Circle-CircleIntersection. html.]

A. Jon Kimerling, Department of Geosciences, Oregon State University, Corvallis, Oregon, 97331. E-mail: <kimerlia@geo.oregonstate.edu>.

Cartographers make dot maps to show details in the spatial variation of geographic phenomena such as human populations or agricultural crops. Dot maps show the geographic distribution of a phenomenon by placing dots representing a certain quantity of the phenomenon where they are most likely to occur. The fundamental steps in dot mapping are selecting the dot size, determining the dot unit value (the quantity of phenomenon represented by a dot), and placing the correct number of dots in a manner that accurately reflects density differences within the geographic distribution.

Selecting dot size is a subjective decision based on visual perception limits and aesthetics. Robinson et al. (1995, p. 498) note that dots too small make the distribution appear sparse and insignificant, whereas dots too large give an equally erroneous impression of excessively high density. Once a dot size has been selected, the dot unit value can be selected either by trial and error, or with the aid of a nomograph devised sixty years ago by J. Ross Mackay (1949) in an article titled Dotting the Dot Map. The 1949 nomograph (Figure 1) is in English measurement units, although cartographers may be more familiar with the more recent metric-unit homograph published in the Elements of Cartography (Robinson et al. 1995, pp. 499-500) and Thematic Cartography and Geovisualization (Slocum et al. 2008, pp. 331-332).

Cartographers use the Mackay nomograph to find the number of dots per square inch (or [cm.sup.2]). This requires three steps. First, draw a straight line from the origin to the selected dot diameter in inches (or cm) found on the radial scale of dot diameters. Next, mark where the line crosses the "zone of coalescing dots." Finally, draw a line vertically downward from this mark to the horizontal axis showing the number of dots per square inch (or [cm.sup.2]) that will begin to coalesce for the selected dot size. For example, 2-point dots with 0.028-inch (0.71 mm) diameters begin coalescence at 750 dots per square inch (116 dots per [cm.sup.2]). This dot density value is used with the map area of the highest density data collection unit and the total quantity in this unit to determine the dot unit value. For instance, 0.028-inch dots would coalesce in a 0.25 [in.sup.2] data collection unit with 187,500 people if the dot unit value were 187,500 people / (750 dots per [in.sup.2] x 0.25 [in.sup.2]) = 1000 people per dot.

The Mackay nomograph has guided cartographers for 60 years of creating maps manually, but it has serious drawbacks in the modern age of computer cartography. The first limitation is the range of dot diameters given on the radial scale. Dot sizes available in ESRI ArcMap software, for example, range from 0.5 to 11 Postcript points, where a Postscript point is exactly 1/72nd (0.0139) inch (.353mm). Dots of 0.5-points and those larger than 5 points are rarely used in dot mapping, but commonly used 1-point dots fall off the lower right side of the nomograph completely below the "zone of coalescing dots." The issue here is that 1.0 point and smaller dots were very difficult to create manually in a consistent manner with ink pens, a non-issue in the world of digital creation of scalable circles by computer software.

[FIGURE 1 OMITTED]

The second drawback to the nomograph is the nature of the "zone of coalescing dots" shown on it. One would expect a zone to be shown by a gray-tone area or something similar on the nomograph, but only a wave-like line of text demarcates the zone. The irregular undulations in the curving text are also puzzling. Mackay explains in a footnote that he determined the "zone of coalescing dots" by drawing dots in squares so that each dot was placed in the largest available space until the entire square was filled with dots that just began to coalesce. This type of space filling method suggests a much smoother curve for the "zone of coalescing dots" text, since the number of dots required to fill the space should quadruple as the dot diameter is halved.

The third and perhaps most serious drawback to the nomograph is its mathematical basis. Mackay does not discuss how he derived the two axes and radial scale that comprise the nomograph, but its mathematical basis can be seen by closely studying values found on it. For example, a 0.098-inch diameter dot has an area of 0.000616 [in.sup.2], which, when multiplied by 750 dots per [in.sup.2], gives an area of 0.46 [in.sup.2], the aggregate area of dots found by extending a horizontal line from the mark at the "zone of coalescing dots" leftward to the vertical axis. Since the vertical and horizontal scales are linear and the lines from the origin to the radial scale are drawn straight, any point on a radial line relates dot density and aggregate area of dots by the equation: dot area x dot density = aggregate area in dots. The nomograph, then, is a graphical representation of this equation, with a "zone of coalescing dots" overlaid.

The notable thing about the equation defining the nomograph is that it is valid only if no dots overlap. Digital implementations of Mackay's method of dot placement, such as Lavin's (1986) quasi-random dot placement algorithm, create a set of non-overlapping dots that appear placed in a random manner. This is not, however, how dots are placed using computer mapping algorithms--such as Dutton's (1978) pioneering effort--which determine the coordinates of dot centers based on random numbers. Consequently, the Mackay nomograph is not appropriate for determining the dot unit value when dot placement is based on computer-generated random numbers that result in overlapping dots if the numbers truly are random.

The purpose of this paper is to revisit Dotting the Dot Map and develop a method to determine dot density and aggregate dot area for computer-generated, randomly placed dots that may overlap. A new graphical aid for selecting dot unit value results when these dot densities and aggregate areas are plotted for dots of different sizes. The method relies on modeling the aggregate area of dots and amount of dot overlap using basic equations from probability theory.

Random Dot Placement and Probability Theory

Dotting the dot map randomly is similar to the random packing of circles in a square (Solomon 1967). Imagine randomly dropping, one by one, identical circular coins into a unit square, say 10 by 10 inches or 10 x 10 cm in area. The problem is finding the total aggregate area covered by coins, knowing that some of the coins dropped less than a diameter apart will overlap. In probability terms, the unit square is a probability of 1.0, and each coin is an identical probability event [E.sub.i] whose area as a proportion of the unit square is its probability of occurrence P([E.sub.i]). Randomly dropping each of n coins can be thought of as an independent probability event, so that the aggregate area is the union of independent probability events with the same chance of occurrence P([E.sub.i]) = P([E.sub.j]) = ... = P([E.sub.n]). The union of n events is given by the unification equation for independent probability events (Suhov and Kelbert 2005):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The first term in the equation is the sum of the n event probabilities. The second term is the sum of the intersections of the number of combinations of events taken two at a time (by analogy, the overlap area of pairs of coins), and so on until the last term, which is the intersection probability for the entire n events.

Turning the coins into n identical dots whose area relative to a 1.0 x 1.0 cm unit square is the probability of occurrence p = [E.sub.i], the aggregate dot area is predicted by the unification equation rewritten as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [n.summation over (i=1)] p = np and the number of combinations in each summation are given by n!/k!(n - k)!

so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The unification equation expands with the number of dots, but raising small numerical values of p to very large powers is computationally unstable. Additionally, it is unlikely that a large number of dots will overlap simultaneously. For these reasons, the full unification equation was truncated to 10 terms:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This truncated equation does not affect the values computed for (95 percent of area covered by dots) for up to 1000 points.

Using the Unification Equation with Different Dot Sizes

A C-language program was written to calculate aggregate area in dots from the truncated unification equation for the nine dot sizes listed in Table 1. The p value (dot area) for each dot size was held constant as the number of dots was increased in increments of ten until either an aggregate dot area of 0.9 (90 percent covered by dots) or a maximum number of 1000 dots was reached. The aggregate areas predicted with increasing numbers of dots are graphed as data points in Figure 2 for the nine dot sizes ranging in diameter from 1 to 5 points. Drawing straight lines between data points shows the smooth curves produced by the truncated unification equation.

This new dot-density selection graph is similar to the Mackay nomograph in that dot density, aggregate dot area, and dot size are being related quantitatively, but there is no "zone of coalescing dots." The white horizontal and vertical lines in Figure 2 show how the graph is used to obtain dot densities for 1, 1.5, and 2 point dots with an aggregate area in dots of 0.46 (46 percent).

Notice that for a 2-point dot size about 160 dots per [cm.sup.2] are needed to reach this aggregate area, whereas the Mackay nomograph shows that 116 non-overlapping dots have this same aggregate area. This difference of 44 dots gives an indication of the amount of dot overlap that occurs when dots are placed randomly in an area. Also, notice that almost exactly four times the number of dots (154 and 627) is needed to obtain the same aggregate area of 0.46 when the dot diameter is halved from 2 to 1 point. Since the smaller dot is one-quarter the area of the larger, an inverse proportionality between dot density and dot area should exist for all dot sizes and aggregate dot areas.

Replacing the more nebulous "zone of coalescing dots" that guides dot density selection on the Mackay nomograph with a quantitative measure of dot coalescence improves the graph in Figure 2. Adding the amount of dot overlap for different aggregate dot areas is one possibility that is easy to implement. The proportion of dot overlap for n dots of the same size is simply the area covered by the dots with no overlaps minus the aggregate dot area computed from the truncated unification equation. Multiplying this difference by 100 gives the dot overlap percentage, expressed mathematically:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 2 OMITTED]

The percent-dot overlap equation was programmed in the same manner as the unification equation. The p value (dot area) for each dot size was held constant as the number of dots was increased in increments of ten until either a 100 percent dot overlap or a maximum number of 1500 dots was reached. Dot overlap percentages predicted with increasing numbers of dots are graphed as data points in Figure 3 for the nine dot sizes ranging in diameter from 1 to 5 points. Notice that, like the aggregate area data, four times the number of dots is needed to obtain the same percent dot overlap when the dot diameter is halved from 2 to 1 point. Once again, an inverse proportionality between dot density and dot area should exist for all dot sizes and aggregate dot areas since the smaller dot is one-quarter the area of the larger.

[FIGURE 3 OMITTED]

Because the two equations and their graphs share this inverse proportionality between dot density and aggregate dot area, the horizontal lines of white squares on the dot overlap graph should be horizontal lines when overlaid on the aggregate dot area graph, as is seen in Figure 4. We can see this mathematical constancy by examining the dot density values in Figures 2 and 3 over a range of dot diameters for a given percent dot overlap. For example, looking at the dot density values in Figure 3 for a 40 percent dot overlap and dot diameters of 1.5, 2.0, 2.5, and 3.0 points, the graph shows that approximately 480, 275, 175, and 125 dots per square centimeter are required to achieve a 40 percent dot overlap. Turning to Figure 2, we see that the aggregate area of dots for each of these dot densities is very close to 0.63. The horizontal line in Figure 4 at 0.63 for a 40 percent dot overlap is a graphic expression of this constancy. One can now select a dot density based upon a desired percent overlap with a corresponding aggregate dot area. The more mathematically precise measure of dot coalescence replaces the "zone of coalescing dots" on the Mackay homograph.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Testing the Aggregate Dot Area and Dot Overlap Equations

A method was developed to place specific numbers of randomly placed black dots of a certain diameter into a unit square so that the aggregate area in dots could be measured and later compared with the aggregate area predicted by the truncated unification equation. Figure 5 shows the steps involved in creating the dots and measuring their aggregate area.

* A C-language program was written to generate random (x,y) coordinates for dot centers. The system clockwas used as the seed value for each set of coordinates, and the numbers generated were scaled from 0 to 10.0 mm to obtain high-precision coordinates falling within a 1 x 1 cm unit square.

[FIGURE 6 OMITTED]

* The computed random dot center point coordinates were imported into a Microsoft Excel spreadsheet in separate columns for the x and y coordinates. The two columns were used to create a scatterplot of the dot coordinates, such as for the 250 dots shown by small diamonds.

* The Excel scatterplot was copied into Macromedia Freehand 10, where the diamond symbols were converted to black dots of the desired diameter, scaled exactly to a 1 x 1 cm unit square. Dots extending outside the edge of the square were duplicated and wrapped around the opposite side of the square (this step is not shown in Figure 5) so that the entire dot fell within the square, with possible overlap from other dots at the edge of the square.

* The Freehand drawing with the wrapped dots was imported into Adobe Photoshop as a raster image file. The raster drawing was clipped to the edges of the unit square, as indicated by the partial dots seen along the edges. The Histogram function in Photoshop was then used to determine the percentage of the drawing that was not the white background. Dots were displayed almost entirely in black, but with a few lighter gray edge pixels. Consequently, the percentile of the lightest gray tone on the image was used as the value for the aggregate dot area. For example, the lightest gray tone for the circular dots in the unit square shown at the bottom of Figure 5 had a value of 191, and 79.14 percent of the pixels in the square were at or lower than (darker than) this value.

The accuracy of the truncated unification equation was investigated by using the above method to measure the aggregate dot areas for unit squares containing the number of dots predicted to overlap by 10 percent, 20 percent, 30 percent, 40 percent, and 50 percent for each of the nine dot sizes randing diameter from 1 to 5 point. The small white squares in Figure 3 are these 45 combinations of dot overlap and dot size. The number of dots for each of the 45 unit squares was read from the horizontal axis of Figure 3. These values are printed in Figure 6, at the top of each unit square. In addition to serving as the basis for aggregate dot area measurement, this diagram serves as a second form of dot selection guide.

Figure 4 shows the simple linear mathematical relationship between predicted percent dot overlap and aggregate area in dots. The horizontal white lines of constant percent dot overlap have been redrawn in Figure 7 as horizontal black lines placed on the vertical axis of aggregate dot area as in Figure 4. Measured aggregate dot areas for each of the 45 unit squares in Figure 6 are plotted as colored dots in Figure 7, with a different color for each percent dot overlap level. The measured aggregate area in dots appears to agree closely with the predicted aggregate areas for small dot diameters having large numbers of dots in the unit square. Conversely, predicted and measured aggregate dot areas diverged by up to five percent as the dot diameter increased and fewer dots were placed in the unit square.

[FIGURE 7 OMITTED]

The noticeable variation between measured and predicted aggregate dot areas for larger diameter dots may indicate the degree of inaccuracy in the truncated unification equation since the equation is deterministic, yet based on probability. Alternatively, the differences may be an indication of variation in the sets of random numbers generated. To investigate if one, or both, possibilities are at play, 25 sets of 55 random coordinates were generated, made into a scatterplot in Excel, and converted in Freehand to 3-point-diameter dots in a unit square (Figure 8). The only deviation from the aggregate dot area measurement method used above was that dots extending outside the unit square were not wrapped to the opposite side, due to the effort involved in doing so, as well as the minimal effect (a few tenths of a percent) of not doing so on the aggregate dot areas. Aggregate areas measured from the dots in Figure 8 should be only slightly higher than if the protruding edge dots were wrapped, since a very small amount of the wrapped pieces of dots overlap with other dots close to the edge of the unit square.

Aggregate dot areas as a proportion of the unit square are printed at the top of each square. The 25 aggregate area proportions vary from 0.363 to 0.406, with an average area proportion of 0.389. This is very close to the 0.385 aggregate dot area proportion predicted by the truncated unification equation. It is possible that if the protruding portions of edge dots in each square were wrapped to the opposite edge, the measured and predicted aggregate dot areas would match within one-tenth of a percent. Consequently, the 0.42 aggregate dot area in Figure 7 is anomalously high relative to the 25 unit squares created to obtain an average aggregate dot area. Equally important, the variation in measured aggregate dot area among the unit squares shows that the truncated unification and similar probability-based deterministic equations are highly accurate only if the predicted aggregate area is compared with the average aggregate area for a large number of unit squares.

Pseudo-Random Dot Placement

The dot-density selection graph in Figure 2 and dot density examples in Figure 4 give mapmakers tools for wise selection of dot densities for different dot sizes when dot placement is completely random. However, there is an important issue with truly random dot placement--cartographers historically have not placed dots in a true random manner when creating dot maps manually. Mackay was correct in noting that dots were placed manually to fill an area with dots that did not overlap. This dot placement method can be termed pseudo-random placement with a maximum dot overlap constraint.

The Mackay nomograph was devised for pseudorandom dot placement with zero dot overlap, which in probability terms is mutually exclusive random dot placement. The aggregate area in dots can be thought of as the union of n identical, mutually exclusive events with probability p equal to the proportion of the dot area relative to a unit square, or n x p. It is also possible to have pseudo-random dot placements with maximum dot overlaps intermediate between mutually exclusive and completely random, as shown in Figure 9. Maximum dot overlap could be set to 10 percent, for example, meaning that 10 percent or less of the area of one dot overlaps a second dot. Notice that small clusters of overlapping dots become more numerous as the maximum dot overlap increases.

[FIGURE 8 OMITTED]

Implementing a maximum dot overlap constraint depends on finding the relationship between overlap area and the distance between dot centers. The mathematical problem is finding the lens area for two circles of radius R whose centers are separated by distance d (Figure 10). The following is the lens area equation giving the proportion of dot overlap for the circles (Weisstein 2008):

[Area.sub.Lens] = 2[R.sup.2] [cos.sup.-1] (d/2R) - 1/2 d[square root of 4[R.sup.2] - [d.sup.2]]

which is mathematically similar to the equation used in Lavin's (1986) circle segment overlap computation procedure. If a unit circle (R = 1.0) is used and d is given as a proportion of the circle radius, the equation simplifies to:

[Area.sub.Lens] = 2[cos.sup.-1] (d/2) -1/2 d[square root of 4 - [d.sup.2]]

where d ranges from 0 (complete overlap) to 2 (complete separation). When d = 0, the computed lens area is [pi], so that the proportion of a dot covered by the lens (the dot overlap proportion) is

[Area.sub.Lens]/[pi]

and the dot overlap percentage is

[Area.sub.Lens]/[pi] x 100

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

Dot overlap proportions for dot center spacings (d) from 0 to 2 are graphed in Figure 11. The line shows an essentially constant decrease in dot overlap with equal increases in dot spacing for d values from 0 to around 1.4. As the dot center spacing increases from 1.4 to 2.0, the dot overlap proportion decreases nonlinearly, with progressively larger increases in dot spacing producing constant decreases in dot overlap proportion. For example, the dot center spacing is 1.0 for a dot overlap proportion of 0.4, 1.2 for a 0.3 overlap, 1.4 for a 0.2 overlap, but 1.63 for a 0.1 overlap proportion and 2.0 for 0 dot overlap.

The dot center spacing values read from the graph were central to the creation of a pseudo-random dot placement method as a modification of determining dot center coordinates in a strictly random manner using a random number generator. The computer algorithm for pseudo-random dot coordinate calculation with a maximum dot overlap constraint involves the following steps:

* Define the total number of dots needed and the minimum separation distance (d) between dot centers.

* Create two initially empty arrays to hold the x and y coordinates to be generated.

* Use a random number generator to create the (x,y) coordinate for the first dot center and store the x and y values in the first row of the arrays.

* Generate a second (x,y) coordinate and use the Pythagorean Theorem to compute the distance between the two coordinates.

* If the computed distance is greater than d, place the x and y values in the second row of the arrays. If the computed distance is less than d, delete the coordinate and generate a new second coordinate. Repeat the minimum distance check until a coordinate is found with a separation distance greater than d. Place the x and y values in the second row of the arrays.

* Repeat the minimum separation distance check for the third and additional coordinates generated, checking that the minimum separation is maintained for all coordinates previously placed

in the arrays. Stop the procedure when the desired number of dot coordinates are found, or when a maximum number of tries (new dots generated) is reached.

* A C-language program was written to implement the pseudo-random dot placement algorithm for dot sizes from 1 to 2.5 points and maximum dot overlap proportions of 0, 0.1, 0.2, and 0.3. This program created data on the relationship between dot density and aggregate area in dots as the maximum allowable dot overlap increases. The number of dots was incremented in steps of 25 or 50, and a maximum of 32,000 tries was set for each program run. Once the arrays of pseudorandom center coordinates were filled with the desired number of dots, distances from each dot to all others were computed, and the lens area and then the dot overlap proportion were calculated for all separation distances less than the dot diameter. Summing the computed dot overlap proportions gave the total dot overlap area from which the aggregate proportion or percentage of area covered by dots could be calculated. The calculations were based on dot pair overlaps, with the assumption that triple, quadruple or higher dot overlaps were insignificant.

[FIGURE 11 OMITTED]

[FIGURE 12 OMITTED]

Figure 12 shows aggregate dot areas computed for 1 point dots in increments of 50 with maximum dot overlaps of 0 percent (mutually exclusive dots), 10 percent, 20 percent, and 30 percent, along with completely random dots in increments of 25. Each data point is the average aggregate area in dots for 30 repetitions of the dot placement method, where the desired number of dots was obtained for each repetition in less than 32,000 tries.

The aggregate dot area data points for mutually exclusive dots form a straight line as there is no dot overlap. Data for dots placed with the 10 percent, 20 percent, and 30 percent maximum dot overlap constraint form smooth curves increasing in curvature with greater maximum dot overlap. Presumably, the curvature will increase with maximum dot overlaps greater than 30 percent until the totally random dot placement curve is reached with 100 percent allowable dot overlap.

Notice that the aggregate area in dots obtained in less than 32,000 tries increases from about 0.45 to 0.85 as the maximum dot overlap increases from 0 to 30 percent. The maximum aggregate dot areas for mutually exclusive placements were examined further by graphing different dot densities against the average number of tries for 30 repetitions of the method required to obtain dot densities from 25 to 475 dots per [cm.sup.2] in increments of 25 dots (Figure 13). The data points form an exponential curve that appears to reach a limit of 0.5 aggregate dot area at a dot density of 500 dots per [cm.sup.2]. This 0.5 aggregate dot area limit for mutually exclusive dot placement helps explain the "zone of coalescing dots" on the Mackay nomograph, as the words were placed just above and below the tick mark at 0.5 aggregate area in dots for 2 point and larger dots. This similarity between maximum dot density and the placement of the "zone of coalescing dots" is not surprising as Mackay based his nomograph on mutually exclusive dot placement. That the "zone of coalescing dots" rapidly decreases to an aggregate dot area of around 0.25 for smaller dots is surprising in light of the 0.5 aggregate dot area limit found for 1-point dots.

[FIGURE 13 OMITTED]

The four graphs in Figure 14 show the result of applying the pseudo-random dot placement method to 1, 1.5, 2, and 2.5-point size dots. The horizontal dot density axis has been scaled in each graph to illustrate the similarity in the curves formed by the data for the five different degrees of maximum individual dot overlap from mutually exclusive to completely random. That the curves are essentially identical when scaled in this manner becomes apparent when relative dot area, dot density, and aggregate dot area is compared for different dot sizes. For example, 2-point dots have four times the area as 1-point dots, and the graphs for these dot sizes show that it takes four times the number of 1-point dots to obtain the same aggregate dot area. This relationship is true regardless of the maximum amount of individual dot overlap, and similar proportionalities exist for 1.5 and 2.5 point dots. These graphical similarities and proportionalities suggest that a general equation can be devised relating dot size, dot density, and maximum individual dot overlap. Such an equation predicting aggregate dot area allows us to specify the proportion of an area covered by dots for a given dot density and maximum allowable dot overlap proportion. The ability to mathematical predict aggregate area in dots in a single equation is crucial to developing software that will perform dot mapping in a pseudo random manner.

A general equation predicting aggregate area in dots for mutually exclusive, pseudo-random, and completely random placement of different size dots should be a combination of the equations for mutually exclusive and completely random dot placement, that is:

[Area.sub.Agg]. = np

and

[Area.sub.Agg] = np - n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10]

One possibility is that the general equation is a weighted combination of the two equations above, or:

[Area.sub.Agg] = knp + (1 - k){np - n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10])

where k is a weight ranging from 0 (completely random dot placement) to 1 (mutually exclusive dot placement). This equation simplifies to:

[Area.sub.Agg] = np + (1 - k)(- n!/2!(n - 2)![p.sup.2]+n!/3!(n-3)![p.sup.3]- ...+[(-1).sup.10]n!/10!(n - 10)! [p.sup.10])

[FIGURE 14 OMITTED]

However, to what is the weight k proportional? Two possibilities related to the maximum allowable individual dot overlap come to mind. The first is that k is directly proportional to the maximum allowable dot overlap, or k = 1.0--maximum dot overlap proportion. A second possibility is that k is proportional to the minimum spacing d between dot centers for the maximum allowable dot overlap. In this case, k ranges from 0.0 for randomly placed dots with a minimum spacing of 0, to 1.0 for mutually exclusive dots with centers separated by a minimum of one dot diameter. To the author's knowledge, neither possibility has a firm basis in probability theory, but the second was found to fit the data points better (about twice as good a fit overall).

[FIGURE 15 OMITTED]

Figure 15 shows the closeness of fit between aggregate areas in dots predicted by the general equation and measured for four dot sizes from 1 to 2.5 point and for five maximum allowable dot overlaps from 0 (mutually exclusive) to 100 percent (totally random). The exact fit of equation and data for mutually exclusive dot placement is expected since the aggregate dot area for n dots placed in a mutually exclusive manner is predicted exactly by the linear equation [Area.sub.Agg]. = np. The extremely close fit between average aggregate dot area for many runs of the program to fill a unit square with completely random dots and the aggregate area predicted by the truncated unification equation was described previously. Notice the very close fit between the average measured aggregate dot areas and those predicted by the general equation for 10 and 20 percent maximum dot overlaps. This very close correspondence is also found for the 30 percent maximum dot overlap data for up to 0.6 aggregate area in dots, after which there is a progressively larger difference between predicted and measured aggregate areas.

Piecewise and Continuous Pseudo-Random Dot Placement

The aggregate area in dots data graphed in Figure 15 show maximum achievable aggregate areas of around 0.5 for mutually exclusive dot placement, around 0.6 for placement with a 10 percent maximum dot overlap constraint, around 0.8 with a 20 percent maximum dot overlap constraint, and around 0.85 with a 30 percent maximum dot overlap constraint. The fact that up to 85 percent of an area can be covered by dots that overlap by no more than 30 percent suggests a piecewise approach to pseudorandom dot placement where high aggregate dot areas can be created with fewer dots and less dot clustering than when using completely random dot placement to achieve the same aggregate dot areas. The basic idea is to determine a range of aggregate dot areas that can be achieved with a reasonable number of tries for a limited number of maximum dot overlap increments.

One approach to defining the steps in a piecewise approach to dot placement is to create graphs relating dot density and the average number of tries needed to reach the dot density. Graphs of these data for 1-point dots with 0 percent, 10 percent, 20 percent, and 30 percent maximum dot overlap are shown in Figure 16. A 5,000-try limit for obtaining the dots was used on each graph to insure that dot creation would be rapid. The right vertical yellow line on each graph shows this limit. The left vertical yellow line on the 10 percent, 20 percent, and 30 percent maximum dot overlap graphs is the maximum aggregate area in dots reached with the previous maximum dot overlap constraint.

The dot density ranges between these yellow lines define the steps in a piecewise approach to pseudo-random dot placement. The upper left graph for mutually exclusive dot placement shows that dot densities of up to 440 dots/[cm.sup.2] and corresponding aggregate dot areas of up to 0.44 can be obtained in less than 5000 tries. With a 10 percent maximum individual dot overlap constraint, the dot density obtained in less than 5000 tries increased to 630 dots/[cm.sup.2] and an aggregate dot area of 0.58. Similarly, maximum dot densities of 840 and 1.150 dots/[cm.sup.2] (aggregate dot areas of 0.72 and 0.82)were reached within 5000 tries for dot placement with 20 percent and 30 percent individual dot overlap constraints. These four maximum dot density and aggregate dot area values were the information needed to create for 1-point dots for the piecewise pseudo-random dot density selection guide shown in Figure 17. The density selection guides for the larger-diameter dots were created in the same manner.

The four maximum dot overlap steps used in pseudo-random placement of different size dots suggest that continuous mathematical functions can be found which give a maximum dot overlap for each dot density. Such an equation was found for 1-point dots by first drawing the dot overlap steps from Figure 16 on graph paper as steps ten squares high and the width of their dot density range. A smooth curve was then drawn on the graph paper roughly diagonally through the steps so that the number of tries to reach each dot density was kept less than 5000. Curve fitting software was then used to find the following polynomial equation that best fit the hand-drawn curve relating maximum individual dot overlap (percent) and dot density (N): percent = 0.008N + [0.00002N.sup.2]. This function is graphed as a solid blue line in Figure 18, along with a solid red line showing the aggregate area in dots for each dot density as predicted by the general equation relating dot density and aggregate area in dots. Similar functions can easily be determined for other dot sizes.

Maximum percent dot overlap and aggregate dot area values were read from Figure 18 for 23 dot density steps in increments of 50 dots ranging from 50 to 1150 dots/[cm.sup.2]. These values provided the information needed to make a pseudo-random dot density selection guide for 1-point dots with continuously varying maximum dot overlap (Figure 19). This dot density selection guide and similar guides made for larger dot sizes not only allow map makers to select a desired amount of dot coalescence from a set of example areas, but also provide graphic examples of how pseudo-randomly placed dots will appear in lower-density sections of the dot map.

[FIGURE 16 OMITTED]

[FIGURE 17 OMITTED]

Conclusion

Revisiting Dotting the Dot Map has brought us in a full circle. Carefully studying the Mackay nomograph uncovered several shortcomings related to its use in modern cartography, the most severe being its inappropriateness for computerized dot mapping where dots are placed randomly with no constraint on the amount of individual dot overlap. Investigating the mathematical nature of rigid random packing of circles in a unit square resulted in modeling completely random dot placement with a truncated form of the unification equation from probability theory.

This equation was found to predict the aggregate area in dots for different dot sizes and dot densities accurately. However, the numerous small clusters of dots characteristic of completely random dot placement led to the realization that cartographers have traditionally placed dots on maps in a pseudo-random manner to minimize the overlap between individual pairs of dots.

[FIGURE 18 OMITTED]

[FIGURE 19 OMITTED]

Mackay devised his nomograph for this type of dot placement, and the mathematical nature of pseudo-random packing of circles in a square with maximum overlap constraints was investigated. A general equation was devised to predict the aggregate area in dots for the complete range of maximum dot pair overlaps from mutually exclusive to completely random. The exact mathematical form of this equation was not found in the probability literature. However, it is possible that the general equation is a linear combination of the equations for mutually exclusive and completely random probability events. Further study by probability experts into the mathematical nature of probability for events that grade progressively from mutually exclusive to completely random may give the mathematical insight needed to refine the general Equation (*) Nevertheless, Mackay would undoubtedly find the sequence of pseudo-randomly placed dots in the piecewise and continuous dot density selection guides to look both familiar and appropriate for dot maps created by modern computer mapping and geographic information systems.

REFERENCES

Dutton, G. 1978. DOT MAP program summary and portfolio. Laboratory for Computer Graphics and Spatial Analysis. Cambridge, Massachusetts: Harvard University.

Lavin, S. 1986. Mapping continuous geographical distributions using dot-density shading. American Cartographer 13(2): 140-50.

Mackay, J.R. 1949. Dotting the dot map: An analysis of dot size, number, and visual tone density. Surveying and Mapping 9(1): 3-10.

Robinson, A.H., J.L. Morrison, RC. Muehrcke, A.J. Kimerling, and S.C. Guptill. 1995. Elements of cartography, 6th ed. New York, New York: John Wiley & Sons.

Slocum, T.A., R.B. McMaster, F.C. Kessler, and H.H. Howard. 2008. Thematic cartography and geovisualization, 3rd ed. Upper Saddle Rives, New Jersey: Prentice Hall Series in Geographic Information Science.

Solomon, H. 1967. Random packing density. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Volume 3: Physical Sciences. Berkeley, California: University of California Press. pp. 119-34.

Suhov, Y., and M. Kelbert. 2005. Probability and statistics by example. Volume 1, Basic probability and statistics. New York, New York: Cambridge University Press.

Weisstein, E.W. 2008. "Circle-circle intersection." From MathWorld-A Wolfram Web Resource. [http:// mathworld.wolfram.com/Circle-CircleIntersection. html.]

A. Jon Kimerling, Department of Geosciences, Oregon State University, Corvallis, Oregon, 97331. E-mail: <kimerlia@geo.oregonstate.edu>.

Table 1. Dot areas (p) for 1 to 5 point size dots. Point Size p (cm2) 1.0 0.000978 1.5 0.002202 2.0 0.003914 2.5 0.006116 3.0 0.008808 3.5 0.011988 4.0 0.015658 4.5 0.011988 5.0 0.024466

Printer friendly Cite/link Email Feedback | |

Author: | Kimerling, A. Jon |
---|---|

Publication: | Cartography and Geographic Information Science |

Geographic Code: | 1U2NY |

Date: | Apr 1, 2009 |

Words: | 6678 |

Previous Article: | Star plots: how shape characteristics influence classification tasks. |

Next Article: | Visualizing migration flows using kriskograms. |

Topics: |