xviii Contents
12.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
12.6.1 Ant on a Chessboard . . . . . . . . . . . . . . . . . . . . . . . 279
12.6.2 The Monocycle . . . . . . . . . . . . . . . . . . . . . . . . . . 280
12.6.3 Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
12.6.4 Bee Maja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
12.6.5 Robbery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
12.6.6 (2/3/4)-D Sqr/Rects/Cubes/Boxes? . . . . . . . . . . . . . . . 286
12.6.7 Dermuba Triangle . . . . . . . . . . . . . . . . . . . . . . . . . 287
12.6.8 Airlines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
12.7 Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
13 Geometry 291
13.1 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
13.2 Triangles and Trigonometry . . . . . . . . . . . . . . . . . . . . . . . 294
13.2.1 Right Triangles and the Pythagorean Theorem . . . . . . . . 295
13.2.2 Trigonometric Functions . . . . . . . . . . . . . . . . . . . . . 295
13.2.3 Solving Triangles . . . . . . . . . . . . . . . . . . . . . . . . . 296
13.3 Circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
13.4 Program Design Example: Faster Than a Speeding Bullet . . . . . . 299
13.5 Trigonometric Function Libraries . . . . . . . . . . . . . . . . . . . . 302
13.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
13.6.1 Dog and Gopher . . . . . . . . . . . . . . . . . . . . . . . . . . 304
13.6.2 Rope Crisis in Ropeland! . . . . . . . . . . . . . . . . . . . . . 305
13.6.3 The Knights of the Round Table . . . . . . . . . . . . . . . . 306
13.6.4 Chocolate Chip Cookies . . . . . . . . . . . . . . . . . . . . . 307
13.6.5 Birthday Cake . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
13.6.6 The Largest/Smallest Box ... . . . . . . . . . . . . . . . . . . . 309
13.6.7 Is This Integration? . . . . . . . . . . . . . . . . . . . . . . . . 310
13.6.8 How Big Is It? . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
13.7 Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
14 Computational Geometry 313
14.1 Line Segments and Intersection . . . . . . . . . . . . . . . . . . . . . 313
14.2 Polygons and Angle Computations . . . . . . . . . . . . . . . . . . . 315
14.3 Convex Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
14.4 Triangulation: Algorithms and Related Problems . . . . . . . . . . . 319
14.4.1 Van Gogh’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 320
14.4.2 Area Computations . . . . . . . . . . . . . . . . . . . . . . . . 322
14.4.3 Point Location . . . . . . . . . . . . . . . . . . . . . . . . . . 322
14.5 Algorithms on Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
14.5.1 Range Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
14.5.2 Lattice Polygons and Pick’s Theorem . . . . . . . . . . . . . . 325
14.6 Geometry Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
14.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
14.7.1 Herding Frosh . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
