Lecture Notes: Graham's Scan Algorithm for Convex Hulls

Overview

• Previous topic: Jarvis-March algorithm for convex hulls.
• Drawback: Time complexity O(n * h) where n = total points, h = points on hull (close to O(n²)).
• Current topic: Graham's Scan algorithm - a more efficient alternative.*

Key Concepts

Convex Hull

• Definition: The smallest convex polygon containing all points.
• A convex polygon has all interior angles ≤ 180°.

Steps in Graham's Scan Algorithm

1. Identify Bottom Point (P0)

   • Find point with the smallest y-coordinate (and smallest x if there are ties).

2. Sort Points by Polar Angle

   • Calculate the polar angle between P0 and each other point.
   • Sort points based on their polar angle relative to P0.

3. Building the Convex Hull

   • Start with the first two points on the hull.
   • For each remaining point:
     • Check the orientation of the points (before last, last, and current).
     • If orientation is counterclockwise, add point to the hull.
     • If orientation is clockwise, remove the last point from the hull and re-evaluate.
   • Repeat until all points are processed.

Orientation Check

• Uses the slopes of lines connecting points to determine orientation.
• Maintain counterclockwise orientations only to form the convex hull.

Implementation Outline

• Initialization: Find P0 (the starting point), and initialize hull as a stack.
• Sorting: Sort points based on polar angle and distance from P0.
• Loop through Points: for each point:
  • While there's a clockwise orientation, pop points from hull.
  • Push the current point to hull after ensuring the correct orientation.

Complexity Analysis

• Time Complexity:

  • Finding P0: O(n)
  • Sorting: O(n log n)
  • Hull construction: O(n)
  • Total: O(n log n)

• Space Complexity: O(n) for storing hull points.

Applications

• Next lecture will cover real-world application: Robots finding shortest paths avoiding polygonal obstacles.

Summary: Graham's Scan is an efficient algorithm for finding the convex hull of a set of points with a time complexity of O(n log n) due to sorting. The algorithm involves determining the polar angles of points and ensuring only counterclockwise orientations are maintained in the hull.