What Is Computational Geometry?

Computational geometry is a branch of computer science and mathematics concerned with the design, analysis, and implementation of algorithms for solving geometric problems. Its objects of study include points, lines, polygons, polyhedra, and curved surfaces, and its central questions ask how to compute intersections, convex hulls, Voronoi diagrams, triangulations, and related structures both efficiently and correctly. The field is distinguished from classical geometry by its emphasis on algorithmic complexity: a solution in computational geometry is not just a mathematical construction but a procedure that must run in bounded time and space.

The discipline emerged as a distinct field in the late 1970s, shaped by the foundational work of Michael Shamos and his 1978 dissertation at Yale, and by Preparata and Shamos's 1985 textbook. Its development ran in parallel with the growth of computer graphics and geographic information systems, which provided concrete problems requiring efficient geometric algorithms. Today, computational geometry feeds into CAD/CAM systems, robotics, medical imaging, and scientific computing wherever geometric data must be processed at scale.

Geometric Algorithms and Data Structures

The core of computational geometry is the study of algorithms for fundamental geometric tasks and the data structures that support them. The convex hull of a point set, the smallest convex polygon containing all points, can be computed in O(n log n) time by algorithms such as Graham scan and Quickhull. Voronoi diagrams, which partition the plane into regions closest to each of a set of seed points, and their duals, Delaunay triangulations, are computed in O(n log n) time and serve as foundational structures for nearest-neighbor search, mesh generation, and interpolation. The ACM Symposium on Computational Geometry is the principal venue for new theoretical results, including improved bounds for classical problems and algorithms for higher-dimensional and non-Euclidean settings.

Surface Fitting and Geometric Modeling

Surface fitting addresses the problem of constructing smooth mathematical representations of shapes from discrete point data, such as a cloud of points measured by a laser scanner or CT imaging device. B-spline surfaces and non-uniform rational B-splines (NURBS) are the standard representation in CAD systems, offering compact parameterizations with local control. Subdivision surfaces, used extensively in animation, generate smooth limit surfaces from a coarser control mesh by recursive refinement. The choice of fitting method affects both the geometric quality of the result and the computational cost; constraints such as curvature continuity or watertightness impose additional algorithmic requirements. Research on these topics appears in IEEE Transactions on Visualization and Computer Graphics, which covers the intersection of geometric modeling with real-time rendering and interactive systems.

Geometric Computation in Three Dimensions

Many industrial applications require algorithms that extend cleanly to three dimensions, where combinatorial complexity grows faster and topological correctness is harder to guarantee. Half-space intersection, polyhedral Boolean operations, and 3D Delaunay tetrahedralization are fundamental tools for volumetric mesh generation. Layered manufacturing processes, broadly called additive manufacturing or 3D printing, depend critically on computational geometry for slicing a solid CAD model into printable layers, generating support structures, and computing tool paths. The NIST Engineering Laboratory's work on additive manufacturing metrology highlights geometry algorithms as a key enabler, from verifying that a printed part conforms to its CAD specification to detecting geometric defects from in-process sensor data.

Applications

Computational geometry has applications in a wide range of disciplines, including:

• Computer graphics and visual effects, through triangle mesh processing and rendering pipelines
• Robotics, for motion planning, collision detection, and workspace analysis
• Geographic information systems, including polygon overlay and spatial indexing
• Medical imaging and surgical simulation, reconstructing anatomical surfaces from CT and MRI data
• Additive manufacturing, generating slice data and tool paths from CAD models