- Atlas
- Computer Science
- Computational Geometry
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
- Discrete geometry 1975-Present
- Divide-and-conquer algorithm 1975-Present
- Motion Planning 1975-Present
- Sweep line algorithm 1975-Present
- Geometric Duality 1978-Present
- Polygon Triangulation and Monotone Decomposition 1978-Present
- Combinatorial Geometry and Arrangements 1980-Present
- Configuration Space Approach 1980-Present
- Randomized Incremental Construction 1985-Present
- Robust Geometric Computation 1988-Present
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
- Computational geometry (introduction, Combinatorial computational geometry, Static problem), Wikipedia
- 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.
- 1975-Present
Discrete geometry
What is the combinatorial structure of geometric configurations?
- 1975-Present
Divide-and-conquer algorithm
How can a problem be split into independent subproblems?
- 1975-Present
- 1975-Present
Sweep line algorithm
How can a moving line simplify a two-dimensional problem?
- 1978-Present
- 1978-Present
Polygon Triangulation and Monotone Decomposition
How can a polygon be cut into simple pieces?
- 1980-Present
Combinatorial Geometry and Arrangements
How many faces, edges, and vertices can an arrangement have?
- 1980-Present
Configuration Space Approach
How can movement be represented as a path in a high-dimensional space?
- 1985-Present
Randomized Incremental Construction
How can randomness make an algorithm simple and fast?
- 1988-Present
Robust Geometric Computation
How can geometric computations be made exact and consistent?
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.
Combinatorial Geometry and Arrangements grew out of Discrete geometry
Combinatorial geometry and arrangements grew directly out of discrete geometry's study of the combinatorial structure of geometric configurations, adding algorithmic construction.
Configuration Space Approach grew out of Motion Planning
The configuration space approach was developed as a formal framework for motion planning, mapping robot positions and orientations into a high-dimensional space with forbidden regions.
Polygon Triangulation and Monotone Decomposition influenced by Sweep line algorithm
Sweep-line algorithms were used to decompose polygons into monotone pieces and to triangulate them by processing vertices in sorted order.
Combinatorial Geometry and Arrangements influenced by Sweep line algorithm
Sweep-line techniques were used to construct arrangements of lines and segments by processing intersection events in order.
Combinatorial Geometry and Arrangements influenced by Geometric Duality
Geometric duality provided a way to map arrangements of lines to arrangements of points, simplifying the construction and analysis of arrangements.
Randomized Incremental Construction influenced by Geometric Duality
Duality was used in randomized incremental algorithms, for example to compute half-plane intersections by dualizing to convex hulls built incrementally.
Randomized Incremental Construction influenced by Combinatorial Geometry and Arrangements
Randomized incremental construction was applied to build arrangements and other combinatorial structures, using backward analysis to bound expected cost.
Robust Geometric Computation influenced by Polygon Triangulation and Monotone Decomposition
Robust geometric computation addressed the practical failures of geometric predicates, such as those used in triangulation, when floating-point rounding caused inconsistent decisions.
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.
Motion Planning influenced by Computational geometry in Geometry
Computational geometry supplied the configuration-space formulation and the geometric algorithms that motion planning adopted as its core method in the late 1970s.
Motion Planning influenced by Computational geometry in Discrete Geometry
Motion planning was built directly on computational geometry: the configuration-space approach and the visibility and roadmap algorithms of the late 1970s and 1980s came from geometric algorithmics.
Polygon Triangulation and Monotone Decomposition grew out of Computational geometry in Geometry
Computational geometry is the field that posed and solved polygon triangulation and monotone decomposition as algorithmic problems in the late 1970s.
Polygon Triangulation and Monotone Decomposition grew out of Computational geometry in Discrete Geometry
Polygon triangulation and monotone decomposition were developed within computational geometry in the late 1970s, notably in the linear-time triangulation work of that period.
Configuration Space Approach grew out of Configuration Space Planning in Robot Motion Planning
The configuration-space approach to motion planning, formulated by Lozano-Pérez and Udupa in the late 1970s, is the direct ancestor of the configuration-space framework in robotics; the later framework generalises and formalises that planning formulation.
Carried by Tomás Lozano-Pérez.
Discrete geometry influenced by Discrete geometry in Geometry
Classical discrete geometry supplied the objects and questions, such as packing, covering and lattice point problems, that computational geometry took up as algorithmic problems in the 1970s.
Discrete geometry influenced by Combinatorial geometry and incidence theory in Discrete Geometry
Combinatorial geometry and incidence theory gave computational geometry its core problem stock, including incidences and arrangements, which were recast as algorithmic questions in the 1970s and 1980s.
Discrete geometry influenced by Convex geometry in Geometry
Convex geometry provided the convex hull, separation and polarity results that computational geometry turned into algorithms in the 1970s.
Motion Planning influenced Learning-Based Motion Planning in Robot Motion Planning
Learning-based planners take the classical motion planning problem formulation, configuration spaces and sampling-based planners as the setting they learn to solve or accelerate, so the earlier planning framework supplied the problem and benchmarks.
Motion Planning provoked Artificial Potential Fields in Robot Motion Planning
Potential-field methods were posed as an alternative to the geometric motion-planning problem, using a continuous field over the workspace instead of explicit configuration-space construction. Khatib's 1986 formulation framed itself against the computational cost of the configuration-space planners.
Carried by Oussama Khatib.
Geometric Duality influenced by Projective geometry in Geometry
Projective geometry supplied the point-line duality principle, the classical polarity correspondence, that computational geometry adapted into an algorithmic transform in the late 1970s.
Combinatorial Geometry and Arrangements influenced by Discrete geometry in Geometry
Classical discrete geometry's study of arrangements of lines and hyperplanes and of incidence configurations provided the objects whose algorithmic construction computational geometry later formalised.
Carried by Herbert Edelsbrunner.

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 GeometryRelated fields
Fields its ideas are linked to
- Discrete Geometry 11 links
- Geometry 10 links
- Robot Motion Planning 6 links
- Convex Geometry 5 links
- Combinatorics 1 link
- Robot Kinematics Dynamics 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Computational Geometry sits on the Map of Human Knowledge