COS 226 Exercises on Geometric Search

NAME:

PRECEPT:

LOGIN:

COS 226 Exercises on Geometric Search

1. Draw the 2D tree 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 tree.

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.)