Convex Hull (Graham Scan)
Find smallest convex polygon containing all points. Graham Scan invented by Ronald Graham in 1972, runs in O(n log n). Essential in computational geometry, computer graphics, and pattern recognition.
Visualization
Interactive visualization for Convex Hull (Graham Scan)
Interactive visualization with step-by-step execution
Implementation
1interface Point {
2 x: number;
3 y: number;
4}
5
6function convexHull(points: Point[]): Point[] {
7 if (points.length < 3) return points;
8
9 // Find bottom-most point (or left-most if tie)
10 let start = 0;
11 for (let i = 1; i < points.length; i++) {
12 if (points[i].y < points[start].y ||
13 (points[i].y === points[start].y && points[i].x < points[start].x)) {
14 start = i;
15 }
16 }
17
18 [points[0], points[start]] = [points[start], points[0]];
19 const p0 = points[0];
20
21 // Sort by polar angle
22 const sorted = points.slice(1).sort((a, b) => {
23 const angleA = Math.atan2(a.y - p0.y, a.x - p0.x);
24 const angleB = Math.atan2(b.y - p0.y, b.x - p0.x);
25 if (angleA !== angleB) return angleA - angleB;
26 // If same angle, closer point first
27 return dist(p0, a) - dist(p0, b);
28 });
29
30 const hull: Point[] = [p0, sorted[0], sorted[1]];
31
32 for (let i = 2; i < sorted.length; i++) {
33 while (hull.length >= 2 &&
34 crossProduct(hull[hull.length - 2], hull[hull.length - 1], sorted[i]) <= 0) {
35 hull.pop();
36 }
37 hull.push(sorted[i]);
38 }
39
40 return hull;
41}
42
43function crossProduct(o: Point, a: Point, b: Point): number {
44 return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
45}
46
47function dist(a: Point, b: Point): number {
48 return (a.x - b.x) ** 2 + (a.y - b.y) ** 2;
49}Deep Dive
Theoretical Foundation
Start with lowest point, sort others by polar angle. Use stack to maintain convex hull. For each point: pop while making right turn (using cross product), then push point. Cross product determines turn direction: positive=left, negative=right, zero=collinear.
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(n)
Applications
Industry Use
Computer graphics (shape rendering and clipping)
Collision detection in video games
Geographic Information Systems (GIS)
Image processing and computer vision
Robotics path planning and navigation
Pattern recognition and machine learning
Computational biology (protein folding)
Manufacturing (optimal material usage)
Use Cases
Related Algorithms
A* Search Algorithm
Informed search algorithm combining best-first search with Dijkstra's algorithm using heuristics. Widely used in pathfinding and graph traversal, A* is optimal and complete when using admissible heuristic. Used in games, GPS navigation, and robotics. Invented by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
Line Segment Intersection
Determine if two line segments intersect. Fundamental geometric primitive used in graphics, CAD, GIS. Uses orientation and collinearity tests.
Caesar Cipher
The Caesar Cipher is one of the oldest and simplest encryption techniques, named after Julius Caesar who used it to protect military messages around 100 BC. It works by shifting each letter in the plaintext by a fixed number of positions down the alphabet. For example, with a shift of 3, A becomes D, B becomes E, and so on. Despite being used for over 2000 years, it's extremely weak by modern standards with only 25 possible keys, making it trivially breakable by brute force or frequency analysis.
Vigenère Cipher
Polyalphabetic substitution cipher using keyword. Invented by Giovan Battista Bellaso in 1553, misattributed to Blaise de Vigenère. More secure than Caesar, resists simple frequency analysis.