Computational geometry is the branch of computer science that studies algorithms for solving geometric problems. In the modern world, computational geometry has applications in (among other fields) computer graphics, robotics, VLSI design, CAD, statistics, and modeling.
The input to a compuational geometry problem usually consists of a set of geometric objects, such as a set of points in two or three dimensions, a set of line segments, or the vertices of a polygon in a particular order. The output is often a response to a query about the object, such as whether any of the lines intersect or a new geometric object.
Due to the fact that many applications of computational geometry involve millions of calculations, efficiency is of the utmost importance. Thus, computational geometry research usually involves honing solutions to specific problems down to the quickest conceivable calculation and solution.
A simple example of computational geometry is the problem of whether or not one segment of a line is clockwise or counterclockwise from another segment which share an endpoint. It's important to give a basic example in two-dimensional geometry, because jumping straight into the fire of higher-order dimensional geometry from a computational perspective can be overwhelming.
To determine whether a directed segment p0p1 is clockwise or counterclockwise from a directed segment p0p2 with respect to their common endpoint p0, we simply use a little trick of Cartesian coordinate geometry. We set the origin (0,0) to be the endpoint p0. Once we've done that, then we realize that the values of p1 and p2 have changed, such that p1 now has the value (x'1,y'1), where x'1 = (x1 - x0) and y'1 = (y1 - y0). A similar notion holds for p2.
So, if we now use the cross product rule, which states that:
p1 x p2 = | x1 x2 |
| y1 y2 |
= x1y2 - x2y1
In other words, if p1 x p2 is positive, then p1 is clockwise from p2 with respect to the origin (0,0). Since in the example above we have set one of the endpoints in each line to be the origin, we can then use the cross product rule:
(p1 - p0) x (p2 - p0) = | x'1 x'2 |
| y'1 y'2 |
If this cross product is positive, then p0p1 is clockwise from p0p2; if the product is negative, then p0p1 is counterclockwise from p0p2.
More complex problems build upon the solution developed here, using the cross product rule time and time again; it is one of the most valuable tools of a computational geometrist. Other common problems include determining whether any pair of line segments in a set of segments intersect, finding the convex hull of a set of points (in other words, finding the smallest boundary around the edge of a set of points without using angles greater than 90 degrees in size), and finding the two points nearest to each other in a set of points. Again, these problems only scratch the surface of some of the complex problems of computational geometry; the depth of research and application of computational geometry is amazing once you begin to investigate the field in depth.
For further reading on computational geometry in a textbook-like environment, the book Computational Geometry: An Introduction by Franco P. Preparata and Micheal Ian Shamos is highly regarded. Another highly regarded general book on computational geometry, this time from a more research-oriented perspective, is Algorithms in Combinatorial Geometry by Herbert Edelsbrunner.
Computational geometry is a satisfying sub-field in the field of computer science that provides a number of solutions to important problems we face in our everyday lives.