NAME:

PRECEPT:

COS 226 Exercises on Geometric Algorithms


1. Run the Graham scan algorithm to compute the convex hull of the following points
(6,3) (5,6) (8,2) (2,4) (3,9) (1, 1) (1,6)
Give the points that appear on the trial hull (after each iteration) in the order that they appear.













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



















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