COS 226 Exercises on Geometric Search

1. Draw the 2d-tree (both the binary tree and the subdivision of the plane) that results when the points (2,1) (5,6) (8,2) (6,3) (4,7) (3,9) and (1,4) are inserted in the order given into an initially empty 2d-tree. (Start by subdividing on the x-coordinate of the root, as in the lecture slides.)

2. Give the sequence of trees, in the style of Figure 27.4, produced by the horizontal-vertical line intersection routine when run on the lines (2,1)---(2,5), (1,6)---(6,6), (3,3)---(3,4), and (5,2)---(5,7). Name the lines A, B, C, and D respectively. Use a horizontal sweep line that sweeps from bottom to top as in the text. (The lecture notes use a vertical sweep line from left to right.)