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. Some of these problems seem so simple that they were not regarded as problems at all until the advent of
computers. Consider, for example, the
closest pair problem: • Given
n points in the plane, find the two with the smallest distance from each other. One could compute the distances between all the pairs of points, of which there are , 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 .
Randomized algorithms that take
O(
n) expected time, as well as a deterministic algorithm that takes time, have also been discovered.
Problem classes The core problems in computational geometry may be classified in different ways, according to various criteria. The following general classes may be distinguished.
Static problem In the problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are: •
Convex hull: Given a set of points, find the smallest convex polyhedron/polygon containing all the points. •
Line segment intersection: Find the intersections between a given set of line segments. •
Delaunay triangulation •
Voronoi diagram: Given a set of points, partition the space according to which points are closest to the given points. •
Linear programming •
Closest pair of points: Given a set of points, find the two with the smallest distance from each other. • Farthest pair of points •
Largest empty circle: Given a set of points, find a largest circle with its center inside of their convex hull and enclosing none of them. •
Euclidean shortest path: Connect two points in a Euclidean space (with polyhedral obstacles) by a shortest path. •
Polygon triangulation: Given a polygon, partition its interior into triangles •
Mesh generation •
Boolean operations on polygons The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.
Geometric query problems 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: •
Range searching: Preprocess a set of points, in order to efficiently count the number of points inside a query region. •
Point location problem: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located. •
Nearest neighbor: Preprocess a set of points, in order to efficiently find which point is closest to a query point. •
Ray tracing: Given a set of objects in space, produce a data structure that efficiently tells which object a query ray intersects first. If the search space is fixed, the computational complexity for this class of problems is usually estimated by: • the time and space required to construct the data structure to be searched in • the time (and sometimes an extra space) to answer queries. For the case when the search space is allowed to vary, see ''''.
Dynamic problems Yet another major class is 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, at the cost of increased processing time. 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: • the time and space required to construct the data structure to be searched in • the time and space to modify the searched data structure after an incremental change in the search space • the time (and sometimes an extra space) to answer a query.
Variations Some problems may be treated as belonging to either of the categories, depending on the context. For example, consider the following problem. •
Point in polygon: Decide whether a point is inside or outside a given polygon. 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
pointer. 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. == Numerical computational geometry ==