Computational geometry is the study of efficient algorithms to solve geometric problems. Typical problems in computational geometry are as follows:

• Given N points in the Euclidean plane, compute the smallest polygon that encloses all the points.
• Given N points in the Euclidean plane, find the nearest neighbor of a given point.
• Given N straight lines, find which of them intersect; or, find the line which most closely approaches some particular other line.
• Partition a polygon efficiently into convex parts.

Of course, it is not necessary that problems be restricted to Euclidean planes or even conventional geometries. There are interesting problems involving hyperbolic and non-Euclidean geometries.

We thus may say, more generally and formally, that computational geometry is that discipline at the interface of geometry and algorithmics which employs triangular meshes and other constructs to analyze shapes (including approximations of objects or terrains) in two or more...