Wing

Computational Geometry

1970s

Ronald Graham, 1972

Finds the convex hull of a point set by sorting points by polar angle and processing them with a stack.

R. A. Jarvis, 1973

Walks around the extreme points of a set by repeatedly choosing the smallest left turn from the current hull edge.

Michael Shamos & Dan Hoey, 1975

Finds the two closest points in a set by comparing all pairs, highlighting the current best distance.

Jon Bentley & Thomas Ottmann, 1976

Detects all intersections among line segments by sweeping a vertical line across the plane from left to right.

Various (attributed), 1978

Partitions a simple polygon into triangles by repeatedly slicing off convex vertices whose shortcut cannot swallow other vertices.

Various (computational geometry folklore), 1978

Cast a ray from a query point and count polygon edge crossings—odd means inside for simple polygons.

1980s

Martin A. Fischler & Robert C. Bolles, 1981

Fits a model to data with outliers by repeatedly sampling minimal subsets and scoring consensus.

Steven Fortune, 1985

Constructs a Voronoi diagram by sweeping a line across the plane, progressively revealing cell boundaries around each site.