# Computational geometry Computational geometry is the branch of [[Computer_science]] that designs and analyzes [[Algorithm|algorithms]] whose inputs are geometric — points, segments, [[Polytope|polytopes]], meshes — and whose costs are measured with the same asymptotic discipline as sorting or searching. The field crystallized in the mid-1970s around Michael Shamos's thesis work and the Preparata–Shamos textbook (1985), which showed that a handful of structures — convex hulls, Voronoi [[Tessellation|tessellations]], Delaunay triangulations — and a handful of techniques — plane sweep, divide-and-conquer, randomization — solve whole families of problems at the provably optimal O(n log n). Its outputs are the working substrate of [[Geographic_information_system|geographic information systems]], [[Robotics|robot motion planning]], [[Computer_vision]], mesh generation for physical [[Simulation]], and nearest-neighbor search in [[Machine_learning]] — anywhere [[Discrete_geometry|discrete geometric]] structure must be built, queried, and trusted under the constraints of finite [[Algorithmic_efficiency|machine arithmetic]]. ## The working structures: hulls, Voronoi, Delaunay The convex hull — the smallest convex [[Polytope]] containing n points — is the field's fruit fly: Graham's scan (1972) builds it in O(n log n), and Chan's output-sensitive [[Algorithm|algorithm]] (1996) in O(n log h) for h hull vertices. The Voronoi diagram partitions the plane into cells of nearest allegiance, an idea reaching back through Voronoi (1908) to Dirichlet (1850); Fortune's sweepline (1987) computes it in O(n log n). Its dual, the Delaunay triangulation (Delone, 1934), connects points whose Voronoi cells touch, satisfies the empty-circumcircle property, and maximizes the minimum angle over all triangulations — the reason it feeds finite-element [[Simulation]] meshes. Because a triangulation is a planar [[Graph_theory|graph]], Euler's formula V − E + F = 2 caps its size at O(n) triangles, and the Euclidean minimum spanning tree — a [[Combinatorial_optimization]] object — sits inside it as a subgraph, a fact [[Network_theory|network]] designers exploit. ## The toolkit: sweeps, divide-and-conquer, randomness Three techniques do most of the lifting. A plane sweep drags a line across the input, maintaining a sorted status structure and a priority queue of pending events, exactly the event-driven bookkeeping of a discrete-event [[Simulation]]; Bentley–Ottmann (1979) reports all k segment intersections in O((n + k) log n). Divide-and-conquer splits, solves, and merges: the Shamos–Hoey closest-pair [[Algorithm|algorithm]] (1975) runs in O(n log n) where brute force pays n²/2 distance tests. Randomized incremental construction (Clarkson–Shor, 1989) inserts objects in random order and lets [[Probability_theory]] average the damage; expected O(n log n) Delaunay construction follows, as does Welzl's expected-linear smallest enclosing circle (1991). Query-time siblings — kd-trees (Bentley, 1975) and O(log n) planar point location (Kirkpatrick, 1983) — turn built structures into instruments for [[Decision-making|decision]] pipelines and [[Geographic_information_system|GIS]] servers that answer "which region holds this point" millions of times per second. ## Why n log n keeps showing up — and when it can't Lower bounds anchor the subject to the [[Theory_of_computation]]. Sorting reduces to convex hull: lift numbers onto a parabola, and the hull reads them off in order, so hull computation inherits the Ω(n log n) bound of comparison sorting in algebraic decision-tree models. Other problems sit on harder floors: for detecting three collinear points among n, no strongly subquadratic method is known, and Gajentaan–Overmars (1995) organized a whole class of such "3SUM-hard" neighbors of [[Discrete_mathematics|discrete]] geometry. Combinatorial complexity is a second ceiling — an arrangement of n lines has Θ(n²) faces, so any [[Algorithm]] that must write the arrangement down pays quadratically — which is why output-sensitive and approximate variants, including (1+ε)-approximations for [[Machine_learning|nearest-neighbor]] search in high dimension, matter in practice where exact [[Algorithmic_efficiency|optimality]] is unaffordable. ## Robustness: the determinant that must not lie Almost every planar routine bottoms out in one predicate: the orientation of an ordered triple, the sign of a 3×3 determinant from [[Linear_algebra]]. Under floating-point rounding that sign can flip near degeneracy, and a single wrong branch can produce structurally invalid output — hulls that self-intersect, triangulations that violate planarity — a [[Correctness_(computer_science)|correctness]] failure rather than a small numeric error, and a real hazard for downstream [[Robotics|robot]] or [[Geographic_information_system|GIS]] pipelines. The exact-geometric-computation response, embodied in the CGAL library (begun 1996), evaluates predicates with certified filters: fast interval arithmetic that acknowledges its own [[Uncertainty]], falling back to exact rational arithmetic only when the interval straddles zero. Symbolic perturbation schemes complete the [[Software_engineering|engineering]] story by dissolving degenerate inputs — collinear triples, cocircular quadruples — into general position without changing asymptotic [[Algorithmic_efficiency|cost]]. ## Configuration spaces: geometry serving robots Motion planning recasts a robot as a single point in its [[Configuration_space_(physics)|configuration space]], one dimension per joint; obstacles become forbidden regions there (Lozano-Pérez, 1983). Exact planning is expensive — the generalized piano mover's problem is PSPACE-hard (Reif, 1979), and Canny's roadmap (1988) still costs time exponential in dimension — a hardness lesson straight from the [[Theory_of_computation]]. Practice therefore samples: probabilistic roadmaps (1996) and rapidly exploring random trees (1998) draw random configurations, [[Monte_Carlo_method|Monte-Carlo]] style, and connect collision-free neighbors into a [[Graph_theory|graph]] that a shortest-path search then exploits. The same machinery plans camera paths, routes assembly sequences, and explores molecular conformations alongside [[Molecular_dynamics]]; coupling the planners to dynamics and feedback hands the result to [[Control_theory]] and [[Robotics]] proper. ## Where the algorithms earn their keep [[Geographic_information_system|GIS]] overlays, map labeling, and viewshed analysis are computational geometry wearing cartography's clothes. One-nearest-neighbor classifiers in [[Machine_learning]] literally decide by Voronoi cell. Delaunay refinement (Ruppert, 1995) generates guaranteed-quality meshes for [[Simulation]] of [[Partial_differential_equation|PDE]] models; collision detection runs inside every physics engine and [[Real-time_computing|real-time]] game loop; facility-location models in [[Operations_research]] read optimal sites off Voronoi vertices, and largest-empty-circle siting is a standard [[Decision_theory|decision]] subroutine. Stereo reconstruction in [[Computer_vision]] triangulates point clouds that hull and mesh algorithms then solidify. Wherever sensors emit coordinates — lidar sweeps, particle tracks, [[Network_science|spatial networks]] — the pipeline from raw points to trusted structure is this field's [[Algorithm|algorithmic]] inventory at work. **On the spine:** [[Discrete_geometry]] · [[Algorithm]] · [[Tessellation]] · [[Polytope]] · [[Graph_theory]]. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Computational_geometry) : [Wikitube](https://en.wikitube.io/wiki/Computational_geometry) ## Previous hub tags Hubs: `Systems`. Portals: [[PORTAL_Systems]], [[PORTAL_Graph_theory]], [[PORTAL_Decision_theory]], [[PORTAL_Information_theory]], [[PORTAL_Control_theory]]. --- *Repopulated 2026-08-12 · redlink fill · 0 deletions.*