The main impetus for the development of computational geometry as a discipline was progress in computer graphics, computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature.
Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (programming of numerically controlled (NC) machines).
The main branches of computational geometry are:
The primary goal of research in combinatorial 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.
One could compute the distances between all the pairs of points, of which there are n(n-1)/2, then pick the pair with the smallest distance. This brute-force algorithm takes O(n2) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(n log n). Randomized algorithms that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.
Computational geometry focuses heavily on computational complexity since the algorithms are meant to be used on very large datasets containing tens and hundreds of million points. For large data sets, the difference between O(n2) and O(n log n) can be the difference between days and seconds of computation.
The core problems in computational geometry may be classified in different ways, according to various criteria. The following general classes may be distinguished.
The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.
In geometric query problems, commonly known as geometric search problems, the input consists of two parts: the search space part and the query part, which varies over the problem instances. The search space typically needs to be preprocessed, in a way that multiple queries can be answered efficiently.
Some fundamental geometric query problems are:
If the search space is fixed, the computational complexity for this class of problems is usually estimated by:
For the case when the search space is allowed to vary, see "Dynamic problems".
A yet another major class are the dynamic problems, in which the goal is to find an efficient algorithm for finding a solution repeatedly after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve dynamic data structures. Any of the computational geometric problems may be converted into a dynamic one. For example, the range searching problem may be converted into the dynamic range searching problem by providing for addition and/or deletion of the points. The dynamic convex hull problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., while the input points are inserted or deleted.
The computational complexity for this class of problems is estimated by:
Some problems may be treated as belonging to either of the categories, depending on the context. For example, consider the following problem.
In many applications this problem is treated as a single-shot one, i.e., belonging to the first class. For example, in many applications of computer graphics a common problem is to find which area on the screen is clicked by a mouse cursor. However in some applications the polygon in question is invariant, while the point represents a query. For example, the input polygon may represent a border of a country and a point is a position of an aircraft, and the problem is to determine whether the aircraft violated the border. Finally, in the previously mentioned example of computer graphics, in CAD applications the changing input data are often stored in dynamic data structures, which may be exploited to speed-up the point-in-polygon queries.
In some contexts of query problems there are reasonable expectations on the sequence of the queries, which may be exploited either for efficient data structures or for tighter computational complexity estimates. For example, in some cases it is important to know the worst case for the total time for the whole sequence of N queries, rather than for a single query. See also "amortized analysis".
This branch is also known as geometric modelling, computer-aided geometric design (CAGD), and may be often found under the keyword curves and surfaces.
Core problems are curve and surface modelling and representation.
First (and still most important) application areas are shipbuilding, aircraft, and automotive industries. However because of modern ubiquity and power of computers even perfume bottles and shampoo dispensers are designed using techniques unheard of by shipbuilders of 1960s.