Loading field map
Computational geometry is the branch of algorithmics concerned with the design, analysis, and implementation of algorithms for geometric problems. Its subject matter is the geometry of points, lines, segments, polygons, circles, and higher-dimensional analogues, but its methods belong to computer science: worst-case complexity analysis, data structures, and the careful management of numerical and combinatorial edge cases. The field asks not merely what is true about geometric objects, but how efficiently one can compute, query, or verify such truths when the input is large.
At its core, computational geometry studies problems of three broad kinds. The first is construction: given a set of geometric objects, build a derived structure that encodes their arrangement. The most famous example is the convex hull—the smallest convex set containing a given set of points. Other construction problems include computing the intersection of two polygons, triangulating a point set, or finding the pair of points closest to each other.
The second kind is query processing: preprocess a static geometric scene so that questions about it can be answered quickly, often many times. Typical queries ask whether a point lies inside a polygon, which of many line segments a vertical ray hits first, or which of many rectangles contain a given query point. The preprocessing may be expensive, but the payoff is that each query runs in time far smaller than scanning the entire input.
The third kind is optimization: find the geometric configuration that minimizes or maximizes a quantity. Examples include finding the smallest enclosing circle for a set of points, the largest empty rectangle in a region, or a shortest path around obstacles. These problems often combine construction and query techniques, and many are computationally hard in the sense of NP-hardness, meaning no efficient exact algorithm is known.
A distinctive feature of the field is its insistence on exactness and robustness. A geometric algorithm must work for all inputs, including degenerate ones: three points that are collinear, two segments that overlap, or points that are nearly coincident. Because floating-point arithmetic introduces rounding errors, a naive implementation of a mathematically correct algorithm can fail catastrophically, producing inconsistent answers or infinite loops. Much of the field's practical effort goes into handling these issues through exact arithmetic, symbolic perturbation, or careful numerical analysis.
The modern field emerged in the 1970s, when computer scientists began applying the tools of algorithm analysis to geometric problems. Earlier work existed—the mathematician and computer scientist Michael Shamos, in his 1978 doctoral dissertation, is often credited with naming the field and establishing its research agenda—but the intellectual precursors were older. Classical geometry, from Euclid onward, provided the mathematical facts; the new contribution was to ask about computational cost. The computational complexity movement of the 1960s, which had already transformed sorting, searching, and graph problems, supplied the framework of asymptotic analysis and lower bounds.
The 1980s were a period of rapid consolidation. Researchers developed the major data structures and algorithmic techniques that still define the field: the Delaunay triangulation and its dual, the Voronoi diagram, which partition space according to nearest-neighbor relationships; arrangements of lines and surfaces, which encode all pairwise intersections among a set of objects; and the plane sweep method, which processes geometric events in sorted order. The field also developed a rich theory of randomized algorithms, in which the algorithm makes random choices that, with high probability, lead to efficient running times.
By the 1990s, computational geometry had matured. The major open problems of the early years had been resolved, the standard toolbox was well understood, and the field turned toward more specialized questions: motion planning for robots, mesh generation for numerical simulation, and the geometry of high-dimensional spaces. A parallel development was the creation of robust software libraries, most notably CGAL (the Computational Geometry Algorithms Library), which made the field's results available to practitioners outside academia.
The dominant approach in computational geometry treats geometric objects as combinatorial entities. A point set is a finite list of coordinates; a polygon is a cyclic sequence of vertices; a line is defined by two coefficients. The goal is to design algorithms whose running time is expressed as a function of the input size, and to prove worst-case bounds on that running time. This tradition prizes asymptotic optimality: an algorithm that runs in \(O(n \log n)\) time is considered superior to one that runs in \(O(n^2)\) time, regardless of constant factors, because the difference matters as \(n\) grows large.
This tradition has produced a remarkable body of theory. The Delaunay triangulation of \(n\) points in the plane can be computed in \(O(n \log n)\) time, and this is optimal in the comparison-based model. The Voronoi diagram, which partitions the plane into cells of nearest neighbors, has the same complexity and is closely related. Arrangements of \(n\) lines in the plane have \(O(n^2)\) vertices, edges, and faces, and can be constructed in \(O(n^2)\) time; for curved objects the complexity can be higher, and bounding it is a deep subject.
A key technique is the plane sweep: sort events (such as segment endpoints or intersections) by one coordinate, then process them in order while maintaining a data structure that represents the current state of the sweep line. This method underlies many efficient algorithms for intersection detection, polygon overlay, and map construction.
Another central technique is randomized incremental construction: add objects one by one in random order, updating the structure after each insertion. The expected running time is often optimal, and the analysis uses the fact that the structure built from a random subset is likely to be small. This approach yields the fastest known algorithms for many problems, including convex hulls and Delaunay triangulations.
A second approach, which grew out of practical frustration with the combinatorial tradition, focuses on making geometric algorithms actually work on real computers. The issue is that combinatorial algorithms assume exact arithmetic, but floating-point numbers are approximate. A point that lies exactly on a line in theory may appear slightly off it in floating-point arithmetic, causing an algorithm to make inconsistent decisions.
This tradition has developed several strategies. One is exact arithmetic: represent coordinates as rational numbers and perform all computations with arbitrary-precision integers, so that geometric predicates (such as "is this point to the left of that line?") are evaluated exactly. This guarantees correctness but can be slow. A second strategy is symbolic perturbation: add infinitesimal random displacements to the input so that degenerate cases disappear, then recover the answer for the original input as a limit. A third is adaptive precision: evaluate predicates with increasing precision until the result is certain, using floating-point arithmetic for the common case and exact arithmetic only when needed.
This tradition also studies the numerical stability of geometric constructions. Computing a convex hull by sorting points by angle and then walking around the hull is simple, but small errors in angle computation can produce a wrong hull. The field has developed robust algorithms that compute the same combinatorial structure regardless of small perturbations in the input, a property called combinatorial consistency.
A more recent tendency connects computational geometry to discrete differential geometry, the study of geometric structures that approximate smooth surfaces and curved spaces. Here the objects of study are meshes—collections of triangles or other polygons that approximate a surface—and the questions concern curvature, geodesics, and shape deformation. This approach borrows techniques from the combinatorial tradition but adds a layer of geometric analysis: the discrete objects are not just combinatorial structures but approximations to smooth ones, and the algorithms must preserve geometric properties such as area, angle, or curvature.
This connection has been fruitful for applications in computer graphics, medical imaging, and scientific simulation. It also marks a shift in emphasis from worst-case complexity to practical performance and geometric fidelity. The two traditions are not rivals so much as complementary: the combinatorial tradition provides the algorithmic skeleton, while the discrete differential geometry tradition provides the geometric meaning and the validation against smooth reality.
A unifying idea across these approaches is geometric duality, which maps one kind of geometric object to another while preserving incidence. The most common duality maps a point to a line (or hyperplane) and vice versa, in such a way that a point lies on a line in the primal plane if and only if the dual line passes through the dual point. This transformation often turns a difficult problem into an easier one: computing the convex hull of points becomes computing the upper envelope of lines, and finding the intersection of half-planes becomes computing the lower envelope of points.
Duality is not merely a trick; it reveals that many apparently different problems are the same problem in disguise. The Voronoi diagram and the Delaunay triangulation are dual to each other, and both are related to the power diagram and the arrangement of certain surfaces in one higher dimension. This web of connections gives the field its intellectual coherence: a small set of fundamental structures and transformations underlies a wide range of problems.
Contemporary computational geometry is a mature field with a stable core and active frontiers. The core results—convex hulls, Voronoi diagrams, Delaunay triangulations, arrangements, and the associated data structures—are taught in standard courses and implemented in robust libraries. The field's main journal and conference, the Symposium on Computational Geometry (SoCG), have run continuously since the 1980s, and the community maintains a shared body of knowledge through open problems lists and benchmark suites.
The active frontiers are several. High-dimensional geometry has become important because of machine learning: points in thousands of dimensions arise naturally in data analysis, and classical algorithms that work well in two or three dimensions become inefficient or meaningless in high dimensions. The field has responded with approximation algorithms that compute near-optimal answers in time polynomial in the dimension, and with the theory of geometric spanners, sparse graphs that approximately preserve distances.
Another frontier is kinetic and dynamic geometry: maintaining geometric structures as the input moves or changes over time. This arises in simulation, animation, and robotics, where the positions of objects are continuously updated. The field has developed kinetic data structures that update the Voronoi diagram or the convex hull as points move, with guarantees on the number of changes over time.
A third frontier is the interface with topology. Computational topology studies the shape of data through persistent homology and related tools, asking which features of a geometric object survive across multiple scales. This work has deep connections to algebraic topology and has found applications in shape analysis, sensor networks, and the study of high-dimensional data. It is often considered a sibling field rather than a subfield, but the boundary is porous: many researchers work in both communities, and the techniques overlap substantially.
The field also continues to engage with applications. Geographic information systems (GIS) rely on computational geometry for map overlay, terrain modeling, and spatial query processing. Computer-aided design (CAD) uses the field's algorithms for surface reconstruction and solid modeling. Robotics applies motion planning algorithms that navigate around obstacles. Computer graphics uses mesh generation, collision detection, and visibility computation. In each of these domains, the field's contribution is not a single algorithm but a repertoire of structures and techniques that practitioners combine and adapt.
What holds computational geometry together is not a single method but a shared commitment to a particular kind of question: given a geometric problem, what is the most efficient algorithm that solves it, and what is the structure that makes that efficiency possible? The field's characteristic objects—Voronoi diagrams, Delaunay triangulations, arrangements—are not arbitrary inventions but the natural combinatorial shadows of geometric space, and the field's characteristic methods—plane sweep, randomized incremental construction, duality—are the ways in which those shadows can be computed and manipulated.
This unity persists across the field's internal diversity. The combinatorial tradition and the robustness tradition ask different questions about the same algorithms; the discrete differential geometry tradition adds a different notion of correctness; the high-dimensional and kinetic frontiers extend the field's reach beyond its classical domain. But all of them share the field's defining assumption: that geometry, when viewed through the lens of computation, reveals a structure that is both beautiful and useful, and that understanding that structure is a worthy intellectual goal in its own right.