Computational geometry

Summary

Computational geometry is the study of algorithms and data structures for geometric objects such as points, segments, polygons and polyhedra. Typical problems are computing a convex hull, a polygon triangulation, a Voronoi diagram or a Delaunay triangulation, and finding intersections among many segments. Its results are measured by running time and memory in terms of the input size, and it relies on combinatorial bounds from discrete geometry. Applications include computer graphics, geographic information systems, robotics and computer-aided design.