NAMES:

LOGINS:

PRECEPTS:

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)
Start with the point with the minimum y-coordinate. List the points that appear on the trial hull after each point is considered, in the order that they appear.

Be careful with (5, 6).