Computer Science, Geometry Joys, Milestones, Murderous Maths, Notes on everyday life, Simon teaching, Simon's sketch book

Graham Scan Algorithm

“Connect some points into a convex polygon such that all of the remaining points are inside that convex polygon. The algorithm that will find it for me is called the Graham Scan Algorithm (actually invented by Ronald Graham),” Simon told me as he printed out a sheet dotted with points. He had also prepared some paper cards with numbers on them. “In general, a Convex Hull is the smallest set (in this case, of points) that contains your original set”.

In the video, Simon manually applies the Graham Scan Algorithm (using the print-out, a protractor and paper cards to create a stack). He measured the angles between the P point and the rest of the points and sorted them (“If you want to do this, you can use any sorting algorithm,” Simon adds).

Simon first learned about the algorithm from a Visualgo visualization but that resource didn’t explain how the algorithm actually works, so he looked it up on Wikipedia.

Simon got his set of points from this site.

the final result

Busy with the same algorithm during the Easter break at the summer house:

wrote the steps of the algorithm in chalk and repeated the whole procedure with fewer points

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s