Computational geometry

Computational geometry is a branch of computer science dedicated to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity.

Overview

An ancient precursor is the sundial, but the relevant computational problems are related to cartography (map making), and robotics. The primary goal of research in computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc.

Algorithms and Applications

Some of the key problems of computational geometry include:

• Convex hulls: The computation of the convex hull of a set of points is a fundamental problem in computational geometry, with various applications in areas such as pattern recognition, image processing, statistics, geographic information systems (GIS), and machine learning.
• Line segment intersection: This problem deals with finding whether or not any pair of segments intersect. It has applications in computer graphics, motion planning, and geographic information systems.
• Voronoi diagrams: These are partitions of a plane into regions based on distance to points in a specific subset of the plane, with applications in nearest neighbor search, clustering algorithms, and cellular biology.
• Delaunay triangulation: This is a triangulation of a set of points in the plane that maximizes the minimum angle. It has applications in mesh generation, computer graphics, and numerical simulations.

Computational Models

The computational problems in computational geometry are modeled using several computational models like the comparison model, algebraic decision tree, and Real RAM. The efficiency of algorithms are analyzed using these models.

See Also

• Discrete geometry
• Differential geometry
• Topological graph theory
• Geometric graph theory