Graham Scan Algorithm

The Graham scan algorithm is a simple and efficient algorithm for computing the convex hull of a set of points. It works by iteratively adding points to the convex hull until all points have been added.

• The algorithm starts by finding the point with the smallest y-coordinate. This point is always on the convex hull. The algorithm then sorts the remaining points by their polar angle with respect to the starting point.
• The algorithm then iteratively adds points to the convex hull. At each step, the algorithm checks whether the last two points added to the convex hull form a right turn. If they do, then the last point is removed from the convex hull. Otherwise, the next point in the sorted list is added to the convex hull.
• The algorithm terminates when all points have been added to the convex hull.

Prerequisite:

• How to check if two given line segments intersect?
• Jarvis’s Algorithm

A convex hull is the smallest convex polygon that contains a given set of points. It is a useful concept in computational geometry and has applications in various fields such as computer graphics, image processing, and collision detection.

A convex polygon is a polygon in which all interior angles are less than 180 degrees. A convex hull can be constructed for any set of points, regardless of their arrangement.