How to Guard an Art Gallery and Other Discrete Mathematical Adventures

4. Pixels, Lines, and Leap Years

4 Pixels, Lines, and Leap Years The shortest distance between two points is under construction. Leo Aikman 4.1 Pixels and Lines A computer monitor has a rectangular array of thousands of tiny square cells called pixels, each of which is light or dark at any time. In the field of computer graphics, we confront the problem of rendering continuous geometric shapes on the array of discrete pixels in an accurate and pleasing manner . This chapter focuses on the most basic situation, the representation of a straight line—more precisely, a line segment —joining two specified points. Computer line drawing problem. How does a computer construct the best configuration of pixels to represent a line segment joining two specified points? Figure 4.1 shows a jagged sequence of 14 dark pixels that represent the segment joining the points with Cartesian coordinates (0, 0) and (13, 8). In our diagrams, the origin is near the lower left corner, the x-axis points rightward, and the y-axis points upward; to reduce clutter, we usually omit the axes. We use unrealistically large pixels to illustrate our ideas more clearly. The center (x, y) of each pixel is a lattice point; both coordinates x and y are integers. 113 114 D is c r e t e M a t he m a t ic a l A d v en t u r es x y (0, 0) (13, 8) Figure 4.1: Pixels for the segment joining (0, 0) and (13, 8) The 14 dark pixels in Figure 4.1 are the pixels closest to the segment. The segment has equation y = (8/13) x, and so the coordinates of the dark pixels are (x, y) = x, round  8 13 x  for x = 0, 1, . . . , 13. The function round [Y] rounds the number Y to the nearest integer. If Y is halfway between two integers, it is rounded up. In general, if 0 < v ≤ w, the line segment joining (0, 0) and (w, v) is represented by the pixels (x, y) = x, round  v w x  for x = 0, 1, . . . , w. (4.1) Algorithm 4.1, which is based directly on (4.1), is unsatisfactory for practical use because step 5 relies on operations P i x el s, L i n es, a n d L e a p Y ea r s 115 that slow down the line drawing process. First, computing the expression (v/w)x uses multiplication and division instead of the faster operations of addition and subtraction. Second, the rounding operation occurs outside of the preferred domain of integer arithmetic, where operations can be performed most rapidly. Algorithm 4.1. A line drawing algorithm Input: integers v and w with 0 < v ≤ w Output: w + 1 dark pixels that represent the line segment joining (0, 0) and (w, v) 1. Start at pixel (x, y) = (0, 0). 2. Darken pixel (x, y). 3. If x = w, then all w + 1 pixels are dark. Stop. 4. Replace x by x + 1. 5. Let y = round  v w x  . Return to step 2. In the 1960s, Jack Bresenham, a computer scientist at IBM, produced a simple, efficient line drawing algorithm that uses only addition and subtraction of integers and other fast operations to.generate the correct pixels. Bresenham’s algorithm is a cornerstone of computer graphics. In this chapter, we discover the algorithm for ourselves. Although our path is not identical to the one taken by Bresenham , our approach helps us relate the computer line drawing to numerical approximations and the distribution of leap years in calendars. In Chapter 7, we link line drawing to a classic problem in number theory. 116 D is c r e t e M a t he m a t ic a l A d v en t u r es 4.2 Lines and Distances We first transform the geometric problem of line drawing to an arithmetic problem involving integers. A Special Case Horizontal and vertical segments are easy to represent on a monitor. We will focus on representing a segment joining the origin (0, 0) and a point (w, v) with 0 < v ≤ w. The slope v/w of this segment satisfies 0 < v w ≤ 1. Our line drawing algorithm will select one pixel in column x for each x = 0, 1, . . . , w, as in Figure 4.1. Solving this special case solves the line drawing problem in general. Other segments can be obtained by reflections and translations (parallel shifts), which can be executed quickly and automatically by a computer. For examx y (0, 0) (13, 8) (8, 13) (−8, 13) Figure 4.2: Transforming the segment joining (0, 0) and (13, 8) P i x el s, L i n es, a n d L e a p Y ea r s 117 ple, suppose we have already determined the pixels for the segment joining the origin (0, 0) and (13, 8). Then the segment joining (20, 10) and (33, 18) is obtained by translating the original segment 20 units horizontally and 10 units vertically . Moreover, interchanging the x- and y-coordinates of the original segment gives the segment joining the origin and (8, 13), and then negating the x-coordinates reflects the segment about the y-axis to produce the segment joining the origin and (−8, 13), as shown in Figure 4.2. A Distance Formula The following formula for the vertical distance from the center of a pixel to a line is the key to our derivation of Bresenham ’s line drawing algorithm. Vertical distance formula. The vertical distance from the point (x, y) to the line joining (0, 0) and (w, v) is dvert =|vx − wy| w . dvert (0, 0) (w, 0) (0, v) (w, v) (x, y) (x, 0) (x, vx/w) Figure 4.3: Vertical distance from a point to a line 118 D is c r e t e M a t he m a t ic a l A d v en t u r es Figure 4.3 shows why the formula is true. The vertical line through (x, y) intersects the slanted line joining (0, 0) and (w, v) at the point (x, vx/w). If the point (x, y) falls below the line, then subtraction shows that the vertical distance we seek is dvert = vx w − y = vx − wy w , while if (x, y) is above (or on) the line, then dvert = y − vx w = − vx − wy w . The vertical distance formula combines both cases by taking the absolute value. For the line drawing problem, it is also reasonable to consider the direct distance d from (x, y) to the line instead of the vertical distance. However, it is not difficult to show (see Problem 1 for hints) that d =|vx − wy| √ v2 + w2 = w √ v2 + w2 dvert, which tells us that within each column the same pixel minimizes both d and dvert. 4.3 Arithmetic Arrays Suppose we want to select the dark pixels representing the segment joining (0, 0) and (13, 8). The distance from the pixel with center (x, y) to the segment is dvert =|8x − 13y| 13 . The rectangular array of numbers in Figure 4.4 helps us select the correct pixels. The number 8x − 13y occurs in position (x, y) in the array. We know that the pixel (x, y) in P i x el s, L i n es, a n d L e a p Y ea r s 119 0 0 8 16 24 32 40 48 56 64 72 80 88 96 104 3 11 19 27 35 43 51 59 67 75 83 91 6 14 22 30 38 46 54 62 70 78 1 9 17 25 33 41 49 57 65 4 12 20 28 36 44 52 7 15 23 31 39 2 10 18 26 5 13 –8 –16 –24 –32 –40 –48 –56 –64 –72 –80 –88 –96 –104 –3 –11 –19 –27 –35 –43 –51 –59 –67 –75 –83 –91 –6 –14 –22 –30 –38 –46 –62 –70 –78 –1 –9 –17 –25 –33 –41 –49 –57 –65 –4 –12 –20 –28 –36 –44 –44 –52 –7 –15 –23 –31 –39 –2 –10 –18 –26 –5 –13 Figure 4.4: Pixels in the arithmetic array A(8, −13) column x is closest to the line joining (0, 0) and (13, 8) exactly when y is chosen to minimize the absolute value of 8x − 13y. The dark pixel in each column is therefore the one whose entry has the smallest absolute value. Note that the dark pixels shown in Figure 4.4 are identical those in Figure 4.1. The same idea works generally. In the arithmetic1 array A(v, −w), the number vx − wy occurs in row x and column y, where x ranges from 0 to w and y ranges from 0 to v. To represent the segment joining (0, 0) and (w, v), the computer should darken the pixel with the smallest absolute value in each column of the arith1 This adjective is pronounced AIR-ith-MEH-tik with accents on the first and third syllables. 120 D is c r e t e M a t he m a t ic a l A d v en t u r es metic array A(v, −w). The number 0 occurs both in position (0, 0) in the lower left corner and in position (w, v) in the upper right corner of the array, which guarantees that the two endpoints of the segment are dark. The numbers in the arithmetic array A(v, −w) increase by v as we read across each row, forming an arithmetic progression with difference v. As we read up each column, we find an arithmetic progression with difference −w. The arithmetic progressions make the entries in the arithmetic array easy to compute by hand and create other patterns we explore later. A Staircase Shortcut It is not necessary to compute every entry in the arithmetic array to find the desired pixels. Within each column, the smallest entry in absolute value is the unique2 number n = vx − wy satisfying − w 2 ≤ n < w 2 . (4.2) We generate the segment from (0, 0) to (w, v) one pixel at a time, working column by column from left to right. Suppose a particular pixel (x, y) has just been darkened, and let the corresponding entry of the arithmetic array be n = vx− wy. Because the slope of our segment is at most 1, either pixel (x + 1, y) or pixel (x + 1, y + 1) should be darkened in the next column. The corresponding entries in the arithmetic array are n + v and n + v − w, and we only need to decide which of these two numbers satisfies (4.2). This means we can restrict our attention to the entries on a staircase configuration in the arithmetic array, as in Figure 4.5. Table 4.1 lists successive pixels and values of n for the segment joining (0, 0) and (13, 8). The output agrees with 2 Two pixels in a column might have values −w/2 and w/2; we have adopted the arbitrary convention of choosing the pixel with value −w/2. P i x el s, L i n es, a n d L e a p Y ea r s 121 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 –1 –2 –3 –4 –5 –6 Figure 4.5: A staircase of pixels in the arithmetic array A(8, −13) Figure 4.4. Algorithm 4.2 implements the staircase method in general. The key test for darkening a pixel occurs in step 5, and the value of n is updated in steps 4 and 6. Table 4.1: Pixels darkened by the line drawing algorithm (x, y) (0, 0) (1, 1) (2, 1) (3, 2) · · · (13, 8) n 0 −5 3 −2 · · · 0  n = 2n − 13 −13 −23 −7 −17 · · · −13 The shaded cells in the arithmetic array A(8, −13) in Figure 4.5 contain the numbers 0, −5, 3, −2, 6, 1, −4, 4, −1, −6, 2, −3, 5, 0. 122 D is c r e t e M a t he m a t ic a l A d v en t u r es Algorithm 4.2. A line drawing algorithm Input: integers v and w with 0 < v ≤ w Output: w + 1 dark pixels that represent the line segment joining (0, 0) to (w, v) 1. Start at pixel (x, y) = (0, 0). Let n = 0. 2. Darken pixel (x, y). 3. If x = w, then all w + 1 pixels are dark. Stop. 4. Replace (x, y) by (x + 1, y) and n by n + v. 5. If −w/2 ≤ n < w/2, return to step 2. 6. Replace (x, y) by (x, y + 1) and n by n − w. Return to step 2. Each number from −6 to 6 occurs once, except for 0, which occurs twice. Also, the absolute sequence, obtained by ignoring the negative signs, is a palindrome, reading the same backward and forward. The same properties hold for the shaded cells in the arithmetic array A(v, −w) whenever v and w are co-prime. Two positive integers are co-prime provided their greatest common divisors is 1. We record these observations for future reference. Observation. Consider the numbers in the shaded cells of the arithmetic array A(v, −w) for the segment joining (0, 0) and (w, v), where v and w are co-prime and v < w. (a) Each integer n satisfying −w/2 ≤ n < w/2 occurs once, except for 0, which occurs twice. (b) The absolute sequence of numbers is palindromic. P i x el s, L i n es, a n d L e a p Y ea r s 123 4.4 Bresenham’s Algorithm Algorithm 4.2 can be improved. It is not difficult to see that the inequality −w/2 ≤ n in step 5 is never violated. Also, the condition n < w/2 is equivalent to 2n − w < 0. If we introduce the parameter  n = 2n − w, then the algorithm only needs to check the condition  n < 0 in step 5. (See the last row of Table 4.1.) A computer can check this simple sign condition quickly. The resulting improvements produce Bresenham’s famous line drawing algorithm (Algorithm 4.3). The algorithm selects the best pixels to represent a segment while relying almost entirely on addition and subtraction of integers. Algorithm 4.3. Bresenham’s line drawing algorithm Input: integers v and w with 0 < v ≤ w Output: w + 1 dark pixels that represent the line segment joining (0, 0) and (w, v) 1. Start at pixel (x, y) = (0, 0). Let  n = −w. 2. Darken pixel (x, y). 3. If x = w, then all w + 1 pixels are dark. Stop. 4. Replace (x, y) by (x + 1, y) and  n by  n + 2v. 5. If  n < 0, return to step 2. 6. Replace (x, y) by (x, y + 1) and  n by  n − 2w. Return to step 2. Our statement of Bresenham’s algorithm emphasizes its logical structure. Practical computer implementations in modern programming languages execute steps 2–5 in a loop with x running from 0 to w. Also, the multiplication by 2 in 124 D is c r e t e M a t he m a t ic a l A d v en t u r es steps 4 and 6 can be eliminated by defining the parameters 2v and 2w before entering the loop. 4.5 A Touch of Gray: Antialiasing The smoothness of a line segment on a computer monitor can often be enhanced by antialiasing, a process that assigns varying shades of gray to pixels near the segment. The number of shades available is usually a power of 2. Figure 4.6 shows eight shades of gray, ranging from 0 (black) 0 1 2 3 4 5 6 7 Figure 4.6: Eight shades of gray to 7 (white), and Figure 4.7 shows the smoother appearance of an antialiased line segment using these eight shades. Figure 4.7: The antialiased segment is on the right We outline one scheme to carry out antialiasing. Assign shade 0 (black) to a pixel if the line segment passes directly through its center. If the segment passes between two pixel centers in a column, then assign the shades of gray in rough proportion to the distances of these two pixels from the segment . In particular, we can assign shade s to one pixel and P i x el s, L i n es, a n d L e a p Y ea r s 125 shade 7−s to the other one for some value of s = 1, 2, . . . , 6. All other pixels remain white (s = 7). Because the distance between a line and the pixel (x, y) is determined by the parameter n = vx − wy, Bresenham’s algorithm can be readily modified to produce antialiased lines. 4.6 Leap Years and Line Drawing A perplexing mathematical question arises in the design of calendars. How do we impose the familiar discrete divisions (day, month, year) on the continuous, periodic movements of the earth, moon, and sun? Any answer to this question entails compromise since the exact periods of the celestial bodies cannot be expressed as the ratios of small integers. Truly accurate calendars are necessarily complex, while simple calendars are inaccurate. Calendars rely on approximations that sacrifice some degree of accuracy for the sake of simplicity and predictability. Many calendars insert a leap day or month in specified leap years—a process called intercalation —to correct for the accumulation of approximation errors and realign the dates with natural phenomena. Some calendars distribute the leap days and months evenly throughout some cycle of years. We now discuss a connection between the computer line drawing problem and the leap year patterns in two calendars . The Hebrew Calendar The Hebrew calendar is an ancient lunar calendar with an intercalary month. It is still used today to determine the dates of religious observances. Every 19-year cycle contains 11 common years (with 12 months) and 7 leap years (with 13 months). Within the cycle, the leap years occur in years 3, 6, 8, 11, 14, 17, and 19. 126 D is c r e t e M a t he m a t ic a l A d v en t u r es 14 17 19 3 6 8 11 Figure 4.8: The 19-year cycle of leap years in the Hebrew calendar The leap year pattern can be found in the configuration of pixels representing the segment from (0, 0) to (19, 7). The dark pixels in Figure 4.8 distribute a rise of 7 vertical units (the leap years) as evenly as possible across a horizontal run of 19 years. Year x is a leap year when pixel (x, y) is followed by a step up to pixel (x + 1, y + 1). If we let pixels (0, 0) and (19, 7) correspond to year 13 of the 19-year cycle, then the cyclic pattern of 2- and 3-unit horizontal runs of pixels agrees with the pattern of leap years in the Hebrew calendar. The Arithmetical Islamic Calendar The lunar calendar of the Islamic world depends on local sightings of the crescent moon and therefore on the prevailing weather conditions, the visual acumen of an observer, and small changes in the orbits of the earth and moon. Islamic scholars of the eighth century devised the arithmetical Islamic calendar, which uses simple mathematical rules to assign dates that are remarkably close to the correct ones. A common year has 354 days, and a leap year has 355 days in P i x el s, L i n es, a n d L e a p Y ea r s 127 the arithmetical calendar. The 11 leap years occur in years 2, 5, 7, 10, 13, 16, 18, 21, 24, 26, and 29 of a 30-year cycle. The leap year pattern corresponds to the horizontal runs of pixels representing the segment joining (0, 0) and (30, 11). See Figure 4.9. Pixels (0, 0) and (30, 11) correspond to year 12 of the 30-year cycle. 13 16 18 21 24 26 29 2 5 7 10 Figure 4.9: Leap years in the arithmetical Islamic calendar Despite its mathematical virtues, the arithmetical calendar is not widely used. It has deviated at times from the observation-based calendar by one or two days, an unacceptable shortcoming for religious purposes. A Direct Line of Reasoning How did people concoct leap year patterns centuries before computer line drawing problems had been contemplated? Here is one plausible path. In the Hebrew calendar, each common year is 7/19 of a month too short. It is reasonable to add one full leap month when the accumulated error exceeds 1/2 month. After the first year, the accumulated error is 7/19. After the second year, the error is 14/19, 128 D is c r e t e M a t he m a t ic a l A d v en t u r es which is greater than 1/2. So a leap month is inserted in the second year, and the accumulated error is adjusted to (14 − 19) /19 = −5/19. After the third and fourth years, the accumulated errors are 2/19 and 9/19, respectively. After the fifth year, the error is 16/19, so a leap month is inserted and the error is adjusted to −3/19. Continuing the process yields the full pattern of leap years in the Hebrew calendar. The method of accumulated errors can also be applied directly to the line drawing problem. Not surprisingly, it leads to Bresenham’s algorithm. In fact, this is the usual method of deriving Bresenham’s algorithm. The geometric distances measured by the entries in our arithmetic arrays are visual manifestations of the accumulated errors. 4.7 Diophantine Approximations We turn from from the geometric problem of approximating lines by pixels to the numerical one of approximating real numbers by fractions. We will see that the two problems are closely related. Two of the most famous approximations in mathematics are π ≈ 22 7 and π ≈ 3.14. The first approximation is superior to the second in both simplicity and accuracy. The fraction 22/7 is simpler than 3.14 = 157/50 because the denominator 7 is less than the denominator 50. To compare the accuracies, we look at the absolute errors    π − 22 7     = 0.001264 . . . and |π − 3.14| = 0.001592 . . . . A Diophantine approximation of the real number u is a fraction y/x chosen to meet the two conflicting goals of sim- P i x el s, L i n es, a n d L e a p Y ea r s 129 plicity and accuracy. We are given u and want to find a fraction y/x with a small denominator x and an absolute error    u − y x     close to 0. Because the numerator y and the denominator x must be integers, we are approximating u by a rational number . Diophantine approximations are named for Diophantus of Alexandria, a third-century mathematician whose study of rational solutions to equations played a major role in the development of algebra and number theory. Suppose the denominator x in a Diophantine approximation is specified in advance. The multiples of 1/x are equally spaced points on a number line, and Figure 4.10 makes it clear than any given real number u must fall within 1/2x of the nearest multiple of 1/x. It follows that for each denominator x, there is a numerator y such that    u − y x     ≤ 1 2x . u 3 x 4 x 5 x 6 x 7 x 8 x Figure 4.10: The number u is within 1/2x of a multiple of 1/x Better Diophantine approximations are available if the denominator x is not specified in advance. The elementary error bound 1/2x can often be replaced by the much smaller expression 1/2x2 . An important result of this type deals with approximations to irrational numbers, numbers like π and √ 2 that cannot be expressed as the ratio of two integers. 130 D is c r e t e M a t he m a t ic a l A d v en t u r es Diophantine approximations to irrational numbers. An irrational number u has infinitely many Diophantine approximations u ≈ y x with absolute error    u − y x     < 1 2x2 . Approximations of the type described in the preceding result include π ≈ 22 7 with absolute error < 1 2(7)2 = 0.01 . . . and π ≈ 355 113 with absolute error < 1 2(113)2 = 0.00039 . . . . Diophantine approximations to irrational numbers are best found by examining continued fractions, a fascinating topic we do not explore here. Diophantine Approximations and Line Drawing Now let us look at Diophantine approximations y/x to a rational number u = v w . Of course, the error is 0 if we choose y/x = v/w, but we insist on using a denominator x that is strictly less than w. In other words, we seek to approximate one fraction by another one with a smaller denominator. Approximations of this type are implicit in the choice of leap year frequencies in calendars. For instance, astronomical measurements have shown that the average number of days between new moons is about 29.530589, an unwieldy rational number. The accuracy of the arithmetical Islamic calendar is a consequence of the excellent Diophantine approximation 29.530589 ≈ 10631 360 . P i x el s, L i n es, a n d L e a p Y ea r s 131 The source of the mysterious fraction 10631/360 is given in Problem 11. The tiny absolute error    29.530589 − 10631 360     = 0.000033 . . . reveals the sophistication of early Islamic astronomy. The Julian calendar3 used widely in Europe until the late sixteenth century had an error roughly 20 times as large. Diophantine approximations to rational numbers are related to the computer line drawing problem. If we approximate the fraction u = v/w by the fraction y/x, the absolute error is     v w − y x     =|vx − wy| wx = dvert x , where dvert is the vertical distance between the point (x, y) and the line joining the points (0, 0) and (w, v). To make the error small, we should choose the point (x, y) close to this line—the same task we faced in the computer line drawing problem. When v < w, the arithmetic array A(v, −w) contains the information we need. Example 1. To approximate the fraction 8/13, we inspect the arithmetic array A(8, −13) in Figure 4.4. The numbers 1 and −1 appear in positions (x, y) = (5, 3) and (8, 5), giving us the Diophantine approximations 8 13 ≈ 3 5 and 8 13 ≈ 5 8 with absolute errors     8 13 − 3 5     = 1 13 × 5 = 0.015 . . . and     8 13 − 5 8     = 1 13 × 8 = 0.009 . . . . 3 A solar calendar with one leap year every four years. 132 D is c r e t e M a t he m a t ic a l A d v en t u r es In general, to approximate the fraction v/w, we locate the positions (x, y) of 1 and −1 in the array A(v, −w). Our observations in Section 4.3 guarantee that one of these two numbers occurs in the left half of the array and thus satis- fies x ≤ w/2. This gives us a Diophantine approximation v w ≈ y x with absolute error     v w − y x     = 1 wx ≤ 1 (2x)x = 1 2x2 . Here is a formal statement. Diophantine approximations to rational numbers. Let u = v/w be a rational number in lowest terms with 0 < v < w. Then u has a Diophantine approximation u ≈ y x with absolute error    u − y x     ≤ 1 2x2 and denominator x at most w/2. Euclid’s Algorithm There is no need to inspect arithmetic arrays to produce the rational Diophantine approximation given above. A better approach is based on the familiar algorithm of Euclid for finding the greatest common divisor of two positive numbers . To find the greatest common divisor of v and w, Euclid’s algorithm divides v into w to produce a quotient q and remainder r. The relation w = vq + r makes it clear that any common divisor of v and w is also a divisor of r. In fact, gcd(w, v) = gcd(v, r), P i x el s, L i n es, a n d L e a p Y ea r s 133 and the procedure can be repeated with r and v in place of v and w. Continue in the same manner until a remainder of 0 occurs. The last nonzero remainder is the greatest common divisor of the original numbers v and w. Example 2. When v = 103 and w = 127, Euclid’s algorithm gives gcd(127, 103) = gcd(103, 24) = gcd(24, 7) = gcd(7, 3) = gcd(3, 1) = gcd(1, 0) = 1. See Table 4.2 for details. We find that gcd(127, 103) = 1, and so the numbers 127 and 103 are co-prime. Table 4.2: Euclid’s algorithm and the gcd of 127 and 103 127 ÷ 103 = 1 with remainder 24 103 ÷ 24 = 4 with remainder 7 24 ÷ 7 = 3 with remainder 3 7 ÷ 3 = 2 with remainder 1 3 ÷ 1 = 3 with remainder 0 For the purposes of our Diophantine approximations, it is better to express the successive remainders in the algorithm in terms of v = 103 and w = 127, as in Table 4.3. The last row of the table tells us that the equation 103x + 127y = 1 is satisfied by x = 37 and y = −30. In general, Euclid’s algorithm leads to the following result . 134 D is c r e t e M a t he m a t ic a l A d v en t u r es Table 4.3: Euclid’s algorithm and the co-primality theorem [127, 103] = [w, v] [103, 24] = [v, w − v] [24, 7] = [w − v, v − 4 (w − v)] = [w − v, −4w + 5v] [7, 3] = [−4w + 5v, (w − v) − 3 (−4w + 5v)] = [−4w + 5v, 13w − 16v] [3, 1] = [13w − 16v, (−4w + 5v) − 2 (13w − 16v)] = [13w − 16v, −30w + 37v] Co-primality theorem. If v and w are co-prime, then there are integers x and y that satisfy vx + wy = 1. The co-primality theorem lets us show that |y|/|x| is a good Diophantine approximation to the fraction v/w. Example 3. To find a good Diophantine approximation to the fraction 103/127, we begin with the relation 103 × 37 + 127 × (−30) = 1 from the co-primality theorem. Divide both sides by the product 127 × 37 and take the absolute value to see that     103 127 − 30 37     = 1 127 × 37 ≤ 1 2(37)2 . This inequality gives the Diophantine approximation 103 127 ≈ 30 37 with absolute error ≤ 1 2(37)2 . 4.8 Notes and References Bresenham describes his algorithm in [2], which is also available online at the link given. The book [3] discusses Bresenham’s algorithm and P i x el s, L i n es, a n d L e a p Y ea r s 135 connections to other problems in computer graphics; computer code is included. Wu and Rokne [11] describe a variant of Bresenham’s algorithm that darkens pixels two at a time. The mathematics of calendars is covered in detail in [7] and [8]. The link between leap years and computer line drawing is discussed by Harris and Reingold [4]. They also relate computer line drawing to Euclid’s algorithm. See [10] for a discussion of Diophantus’ role in the history of mathematics . Diophantine approximations are treated in [5] and in many books on number theory, including the one by Ogilvy and Anderson [6]. For more on continued fractions, see the last three chapters of [1]. A good introduction to Euclid’s algorithm is found in Stillwell’s book [9]. 1. Ball, Keith, Strange Curves, Counting Rabbits, and Other Mathematical Explorations. Princeton University Press, Princeton, New Jersey, 2003. 2. Bresenham, J. E., Algorithm for computer control of a digital plotter, IBM Systems Journal 4 no. 1 (1965), 25–30. Also available at: www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf 3. Glassner, Andrew S. (ed.), Graphics Gems. Academic Press Professional, Boston, 1990. 4. Harris, M. A., and Reingold, E. M., Line drawing, leap years, and Euclid, ACM Computing Surveys 36 (2004), 68–80. 5. Niven, Ivan, Diophantine Approximations. Dover, New York, 2008. 6. Ogilvy, C. Stanley, and Anderson, John T., Excursions in Number Theory. Dover, New York, 1988. 7. Reingold, Edward M., and Dershowitz, Nachum, Calendrical Calculations : The Millennium Edition. Cambridge University Press, Cambridge, U.K., 2001. 8. Reingold, Edward M., and Dershowitz, Nachum, Calendrical Tabulations, 1900–2200. Cambridge University Press, Cambridge, U.K., 2002. 9. Stillwell, John, Elements of Number Theory. Springer, New York, 2003. 10. Stillwell, John, Numbers and Geometry. Springer, New York, 1998. 11. Wu, X., and Rokne, J. G., Double-step incremental generation of lines and circles, Computer Vision, Graphics, and Image Processing 37 (1987), 331–334. 4.9 Problems 1. (a) Use a suitable pair of similar right triangles in Figure 4.3 to show that v w = dvert + y x . 136 D is c r e t e M a t he m a t ic a l A d v en t u r es (b) Use part (a) to deduce the vertical distance formula. (c) Use another pair of similar right triangles in Figure 4.3 to deduce that d =|vx − wy| √ v2 + w2 . 2. Use the arithmetic array A(3, −5) in Figure 4.11 to darken the six pixels for the segment joining (0, 0) and (5, 3). 0 0 3 6 9 12 15 1 4 7 10 2 5 –3 –9 –12 –15 –1 –4 –4 –7 –10 –2 –5 Figure 4.11: The arithmetic array A(3, −5) 3. Use the arithmetic array A(5, −8) in Figure 4.12 to darken the nine pixels for the segment joining (0, 0) and (8, 5). 0 0 5 10 15 20 25 30 35 40 2 7 12 17 22 27 32 4 9 14 19 24 1 6 11 16 3 8 –5 –10 –15 –20 –25 –30 –35 –40 –2 –7 –12 –17 –22 –27 –32 –4 –9 –14 –19 –24 –1 –6 –11 –16 –3 –8 Figure 4.12: The arithmetic array A(5, −8) P i x el s, L i n es, a n d L e a p Y ea r s 137 4. If Algorithm 4.2 is used with v = w = 5 to represent the segment from (0, 0) to (5, 5), what is the value of n each time step 2 is executed? 5. What are the omitted entries in Table 4.1? 6. Let Bresenham’s algorithm be used to represent the segment from (0, 0) to (w, v), where w is odd. Show that pixel (x, y) is dark if and only if pixel (w − x, v − y) is dark. 7. Use the result of the Problem 6 to modify Bresenham’s algorithm so that it darkens pixels from both ends of the segment simultaneously. Either assume w is odd, or else make a small adjustment to the conclusion of Problem 6 in case w is even. 8. Verify that the successive numerators 7, −5, 2, 9, −3, . . . of the accumulated errors for the Hebrew calendar occur in the positions of the dark pixels for the segment joining (0, 0) and (19, 7) in the arithmetic array A(7, −19). 9. (a) Which pixels are darkened by Bresenham’s algorithm for the segment joining (0, 0) and (12, 5)? (b) Use the answer to part (a) to distribute five months of 31 days and seven months of 30 days over a 365-day year in some reasonable manner. 10. The arithmetical Islamic calendar described by Figure 4.9 has a variant in which a leap year in year 15 replaces the one in year 16. What reasonable modification of our convention in (4.2) agrees with this variant? 11. In the arithmetical Islamic calendar, the 12 months in a year alternate between 30 and 29 days, except that the twelfth month has 30 days in a leap year. Show that there are 10631/360 days per month on average. 138 D is c r e t e M a t he m a t ic a l A d v en t u r es 12. (a) What calendar is related to the Diophantine approximation 365.2422 ≈ 365 + 1 4 ? (b) What calendar is related to the Diophantine approximation 365.2422 ≈ 365 + 97 400 ? 13. Sketch an antialiased representation of the segment joining (0, 0) and (13, 8) using four shades of gray. Compare your sketch to Figure 4.1. 14. Find a Diophantine approximation 355 113 ≈ y x with x < 113 and absolute error at most 1/2x2 . 15. Find a Diophantine approximation 55 89 ≈ y x with x < 89 and absolute error at most 1/2x2 . God writes straight with crooked lines. Spanish proverb Truth is much too complicated to allow anything but approximations. John von Neumann ...