How to Guard an Art Gallery and Other Discrete Mathematical Adventures

Index

Index Abbot Albert, 155 abbreviated state sequence, 145, 151 absolute sequence, 122 addition table, 173, 174 additive number theory, 170 additivity of area, 50 Afghanistan, 106 Aikman, Leo, 113 Alberti, Leon Battista, 112 algorithm, 75, 78, 83 art gallery, 83, 84 right-angled, 96 Bresenham’s, 115, 122, 123, 134 Bruce Willis problem, 143 circle of lights, 197, 202 Euclid’s, 132, 135, 242 line drawing, 115, 122 Bresenham’s, 115, 122, 123, 134 water measuring, 148–150 Alice and Bob, 194, 200, 201, 204 Anderson, John T., 135 antialiasing, 124 Apostol, Thomas M., xi approximation, 41, 125 area, 34 Diophantine, 128 arithmetical Islamic calendar, 126, 130, 137 arithmetic array, 118, 119, 151, 152, 163, 168, 198, 201, 230 diminished, 182, 184, 186, 201 arithmetic array theorem, 153, 185, 199 arithmetic progression, 120, 152– 154 art gallery, ix, 51, 73, 75, see also gallery algorithm, 83, 84 right-angled galleries, 96 problems, 75, 88 theorem, 81 AT&T Laboratories, 20 Atiyah, Michael, 32 ATM card, 164 attainable number, 170 uniquely, 181 axis-parallel, 44 Ball, Keith, 65 Banks, Robert B., 22 barcode, 74 baseball, 56 batting average, 56, 68 Beck, Matthias, 65 Berra, Yogi, 1 bijection, 180 binomial theorem, 161, 167 Bogomolny, Alex, 156 Boldi, P., 164, 168 Bresenham, Jack, 115, 134 Bresenham’s algorithm, 115, 122, 123, 134 Brualdi, Richard A., 22 Bruce Willis problem, x, 139, 152, 156 calculus, 8, 43 calculus of finite differences, 7 calendar, 125 Hebrew, 125 Islamic, 126, 137 Julian, 131 251 252 I n de x Cartesian coordinates, 35, 113 plane, 39, 42 ceiling function, x , 92 Chinese Remainder Theorem, 172, 187, 222 choose function, 10, 12, 167, 241 chords, 26 Chvátal, Vasek, 81, 88, 98, 106, 112 circle of lights algorithm, 197, 202 code length, 214 parameters, 214 quadratic residues, 214, 240 repetition, 213 size, 214 code word, 213 coding theory, 208, 213 coin exchange problem, 190 coin theorem, 192 comb-shaped gallery, 93 complete state sequence, 145 complete the square, 241 compound, 200 computational complexity, 78 computational geometry, 74 computer graphics, 113, 115 computer line drawing, see line drawing congruence, 161, 187, 209 Fermat’s, 160, 162, 167, 242 connected graph, 17 continued fractions, 130 continuity error, 146 convex, 76 convex polyhedron, 60 convex quadrangulation, 95, 100 theorem, 96 Conway, John Horton, 194 co-primality theorem, 133, 154, 155, 164, 187 co-prime, 122, 140, 141, 147, 167, 168, 172 Cromwell, Peter R., 22 Crown Gallery, 79 cryptography, 164, 208, 224, 225 cube, 19, 102 Cuoco, Al, 22 Czyzowicz, J., 106 Davenport, H., 239 Dean, James, 207 degenerate quadrilateral, 88, 94 derivative, 8 determinants, 37 Die Hard: With a Vengeance, x, 139, 146 difference table, 2, 7, 11, 24, 30 digital signature, 164, 225 diminished arithmetic array, 182, 184, 186, 201 Diophantine approximation, 128 Diophantus, 129 discrete mathematics, ix, 2, 5, 34, 65, 74, 78, 84, 86, 150, 164, 196 dissection puzzle, 68 distance formula, 117 vertical, 117 dollar-changing, 37 problem, x, 33, 171 theorem, 47 Ebert, Roger, 146 edge, 17 Ehrhart polynomial, 65 Einstein, Albert, 43 Eisenstein, Ferdinand, 237, 239 Eppstein, David, 22 Eratosthenes, 188 error-correcting code, 213 Euclid’s algorithm, 132, 135, 242 Euler, Leonhard, 16, 216, 219, 236 I n d e x 253 Euler’s criterion, 219, 220, 226, 244 Euler’s formula, 16, 17, 22, 25– 27, 56, 65 Euripedes, 112 face, 17 factorial, 12 Fermat, Pierre de, x, 142, 160 Fermat’s congruence, 160, 162, 167, 242 Fermat’s theorem, 160 fingerprint recognition, 75 finite differences, 7 Fisk, Steve, 81, 88, 93, 100, 106 floor function, x , 80 forensics, 75 fortress problem, 88 four squares theorem, 171 framed (triangle), 36, 52 Frobenius, Ferdinand Georg, 191 Frobenius number, 191, 198, 202 gallery, 75 comb, 93 convex, 77 Crown, 79, 80 New Wave, 97 rectangulated, 92, 109 theorem, 92 right-angled, 93 Scorpio, 110 Square Wave, 99 Sunflower, 73, 76, 110 Sunrise, 86 Gauss, Carl Friedrich, 226, 236, 244 Gauss’s lemma, 226, 243 gcd, see greatest common divisor generating function, 196 Gentry, Sommer, xi global positioning satellite (GPS), 74 golden theorem, 237 grapefruit-cutter’s formula, 11, 30 grapefruit-cutter’s recurrence, 30 greatest common divisor, 45, 132, 141, 172, 204, 242 Gruber, Simon, 139, 150 guard, 73 guarded, 96 half-, 90, 110 guarded guards, 96 theorem, 98 right-angled galleries, 100 half-guard, 90, 110 theorem, 91 Harris, M. A., 135 Hebrew calendar, 125 Heron’s formula, 35...