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.