Computational Geometry

Computational geometry is the branch of algorithm design that deals with geometric objects—points, line segments, polygons, circles, planes—and asks how to compute with them efficiently.

10 frameworks, from 1975 to today · Algorithms · Computer Science

still a working view ended · each leads to its entry below

Overview

Computational geometry is the branch of algorithm design that deals with geometric objects—points, line segments, polygons, circles, planes—and asks how to compute with them efficiently1. Given a million points, how do you find the closest pair without checking every pair1? Given a map of polygonal obstacles, how does a robot find a path through them12? Given a set of line segments, how do you decide whether any two cross1? These questions look like geometry, but the answers are judged by the standards of algorithms: running time as a function of input size, correctness, and the ability to handle degenerate cases. What is at stake is practical—computer graphics, geographic information systems, robotics, and computer-aided design all depend on fast geometric computation—but also theoretical, because geometry turns out to be a rich source of problems where the obvious approach is far from optimal and where the right data structure or the right way of looking at the problem changes everything1.

Ancient Roots and the Pre-Algorithmic Era

Geometry is one of the oldest mathematical disciplines, but computational geometry as a field is a child of the computer age. The problems themselves are old: finding the convex hull of a set of points—the smallest convex polygon containing them all—appears in the work of early twentieth-century mathematicians, and the idea of a convex hull is implicit in much older geometry. What changed in the 1960s and 1970s was the question being asked. Instead of proving that a geometric object exists or characterizing its properties, researchers began asking how to compute it with a finite procedure whose cost could be analyzed.

Early work came from several directions. Computer graphics needed algorithms for clipping lines against windows and for hidden-surface removal. Pattern recognition and statistics needed convex hulls and nearest-neighbor searches. Operations research had already developed linear programming, which is deeply geometric: the simplex method, devised by George Dantzig in the late 1940s, walks along the vertices of a high-dimensional polytope. But these efforts were scattered across application areas, each with its own conventions and its own notion of what counted as a good algorithm.

The 1970s: Foundations and the Divide-and-Conquer Style

The field crystallized in the mid-1970s. A landmark was the 1975 Ph.D. thesis of Michael Shamos at Yale, which framed geometric problems in explicitly algorithmic terms and introduced fundamental techniques. Shamos and Dan Hoey gave an algorithm for finding the closest pair of points in the plane in time proportional to n log n, where n is the number of points—a result that showed geometry could be done with the same asymptotic discipline as sorting. The key idea was divide and conquer: split the points by a vertical line, solve each half recursively, and then handle the pairs that straddle the dividing line by examining only a narrow strip, because points farther apart than the best distance found so far cannot improve on it. This was not merely a clever trick; it established a template that recurred throughout the field.

Divide and conquer became one of the field's signature methods. The convex hull can be computed by splitting the points, computing the hull of each half, and merging the two hulls by finding their common tangents—an approach developed in the 1970s and refined by later workers. The pattern is always the same: decompose the input into independent subproblems, solve them recursively, and combine the results in time linear in the size of the subproblem. What made geometry distinctive was that the combine step often required geometric insight—finding tangents, merging sorted lists of points along a convex curve, or proving that only a bounded number of candidates near the split need be examined.

Plane Sweep and the Sweep-Line Paradigm

A second foundational technique emerged in the same period: the plane sweep. Imagine a vertical line moving across the plane from left to right. At any moment, the line intersects a set of geometric objects, and the order of those intersections along the line changes only at discrete events—when the line passes a vertex, an endpoint, or an intersection point. By maintaining a data structure of the objects currently crossed by the sweep line and processing events in sorted order, one can solve many problems in O(n log n) time. The technique was applied to detecting whether any two of a set of line segments intersect, to computing the union of rectangles, and to triangulating polygons. Its power lies in turning a two-dimensional problem into a one-dimensional sequence of events, each handled with a balanced search tree.

The plane sweep is closely tied to the idea of a combinatorial arrangement—the decomposition of the plane induced by a set of lines or curves. The arrangement of n lines has on the order of n² vertices, edges, and faces, and computing it efficiently was a natural target. Arrangements became a central object of study because they encode the structure of geometric configurations and because many problems reduce to walking through an arrangement. The field of combinatorial geometry—the study of the combinatorial structure of geometric configurations—grew alongside the algorithmic work, supplying bounds on how many faces, edges, and vertices such structures can have.

Duality and the Unity of Geometric Problems

A conceptual breakthrough of the late 1970s and early 1980s was the systematic use of geometric duality. In the plane, a point can be mapped to a line and a line to a point by a transformation such as the one that sends the point (a, b) to the line $y = ax$ − b. This correspondence preserves incidences: a point lies on a line exactly when the dual line passes through the dual point. Problems that look different—finding the smallest circle enclosing a set of points, or determining whether a point lies above or below each of a set of lines—turn out to be dual to one another. Duality let researchers translate a problem into a form where known techniques applied, and it revealed that many seemingly separate problems were the same problem in disguise. It became a standard tool, alongside inversion and projective transformations, for simplifying geometric arguments.

Randomized Incremental Construction

The 1980s and 1990s brought a shift in method. Deterministic algorithms were the ideal, but some problems resisted clean deterministic solutions, and the analysis of worst-case behavior could be pessimistic. Randomized incremental construction offered a different path: build the solution by adding objects one at a time in random order, maintaining the answer incrementally. The random order ensures that, in expectation, each insertion is cheap, because the probability that a given object is the last one added—and therefore the one that forces expensive restructuring—is small. This technique gave simple, elegant algorithms for problems such as computing the intersection of half-planes, constructing Delaunay triangulations, and building arrangements. The analysis relied on backward analysis, a technique for bounding the expected cost of the last step by considering the probability that a particular object was added last. Randomized methods did not replace deterministic ones but gave practitioners a powerful alternative, especially when the deterministic algorithm was complicated to implement.

Robust Geometric Computation

As algorithms matured, a practical crisis emerged. Geometric predicates—decisions such as whether three points are collinear or whether a point lies inside a circle—are computed in floating-point arithmetic, which rounds. A rounding error can flip a decision, and a flipped decision can make an algorithm produce a topologically inconsistent result: a triangulation with crossing edges, a convex hull that is not convex. The problem is not rare; it arises whenever inputs are nearly degenerate. The response, developed from the late 1980s onward, was robust geometric computation: exact arithmetic for predicates, adaptive precision that uses exact arithmetic only when floating-point is inconclusive, and symbolic perturbation to handle degeneracies consistently. This work made the difference between algorithms that were correct in theory and algorithms that worked in practice.

Motion Planning and the Geometry of Movement

A major application area that shaped the field was motion planning—computing a collision-free path for a robot among obstacles. The configuration space approach, formalized in the 1980s, maps the robot's possible positions and orientations into a high-dimensional space and treats obstacles as forbidden regions. For a translating polygon among polygonal obstacles, the problem reduces to finding a path in the plane; for a rotating robot, the configuration space gains dimensions. Computational geometry supplied the tools: visibility graphs, shortest-path maps, and cell decomposition. The problem also pushed the field toward complexity theory, because motion planning in high dimensions is computationally hard, and toward approximation, because exact solutions are often infeasible.

Polygon Triangulation and the Quest for Linear Time

Triangulating a simple polygon—decomposing it into triangles by adding non-crossing diagonals—is a basic operation in graphics and mesh generation. The naive approach is quadratic; the challenge was to do it in linear time. A 1991 algorithm by Bernard Chazelle achieved O(n) time, a theoretical triumph that was notoriously complex. In practice, simpler O(n log n) algorithms based on monotone decomposition—splitting the polygon into monotone pieces and triangulating each—were widely used. The gap between theoretical optimality and practical simplicity became a recurring theme.

The Present: Libraries, Libraries, and Open Questions

Today computational geometry is embedded in software libraries such as CGAL and in the geometry engines of graphics systems, GIS platforms, and CAD tools. The core techniques—divide and conquer, plane sweep, duality, randomized incremental construction, robust predicates—are taught in standard textbooks and used daily. The field has expanded into areas such as mesh generation, shape reconstruction from point clouds, and geometric approximation. Open questions remain: exact complexity of fundamental problems in higher dimensions, the design of algorithms that are both theoretically optimal and practically simple, and the handling of massive datasets where the input does not fit in memory. The history of computational geometry is a history of finding the right way to look at a geometric problem—and of discovering that the right way often comes from a small set of powerful ideas.

References

  1. Computational geometry (introduction, Combinatorial computational geometry, Static problem), Wikipedia
  2. Motion planning, Wikipedia

The frameworks of Computational Geometry

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1975-Present

    Discrete geometry

    What is the combinatorial structure of geometric configurations?

    Fly to its tower in Nousfarer

  2. 1975-Present

    Divide-and-conquer algorithm

    How can a problem be split into independent subproblems?

    Fly to its tower in Nousfarer

  3. 1975-Present

    Motion Planning

    How can a robot find a collision-free path?

    Fly to its tower in Nousfarer

  4. 1975-Present

    Sweep line algorithm

    How can a moving line simplify a two-dimensional problem?

    Fly to its tower in Nousfarer

  5. 1978-Present

    Geometric Duality

    How can points and lines be mapped to each other?

    Fly to its tower in Nousfarer

  6. 1978-Present
  7. 1980-Present

    Combinatorial Geometry and Arrangements

    How many faces, edges, and vertices can an arrangement have?

    Fly to its tower in Nousfarer

  8. 1980-Present

    Configuration Space Approach

    How can movement be represented as a path in a high-dimensional space?

    Fly to its tower in Nousfarer

  9. 1985-Present

    Randomized Incremental Construction

    How can randomness make an algorithm simple and fast?

    Fly to its tower in Nousfarer

  10. 1988-Present

    Robust Geometric Computation

    How can geometric computations be made exact and consistent?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Discrete geometryDivide-and-conquer algorithmMotion PlanningSweep line algorithmGeometric DualityPolygon Triangulation and Monotone De…Combinatorial Geometry and Arrangemen…Configuration Space ApproachRandomized Incremental ConstructionRobust Geometric Computation

Beyond the field

Where Computational Geometry's ideas came from in other fields, and what they led to there: the strongest 12 of 34 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Computational Geometry is a planet in Nousfarer

Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.

Land on Computational Geometry

Related fields

Fields its ideas are linked to

More in Algorithms

See where Computational Geometry sits on the Map of Human Knowledge