Proximity problems
Encyclopedia
Proximity problems is a class of problems in computational geometry
which involve estimation of distance
s between geometric objects.
A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used synonymously to the nearest neighbor search
.
A common trait for many of these problems is the possibility to establish the Θ
(n log n) lower bound on their computational complexity
by reduction from the element uniqueness problem
basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.
Computational geometry
Computational geometry is a branch of computer science devoted 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...
which involve estimation of distance
Distance
Distance is a numerical description of how far apart objects are. In physics or everyday discussion, distance may refer to a physical length, or an estimation based on other criteria . In mathematics, a distance function or metric is a generalization of the concept of physical distance...
s between geometric objects.
A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used synonymously to the nearest neighbor search
Nearest neighbor search
Nearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
.
A common trait for many of these problems is the possibility to establish the Θ
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) lower bound on their computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
by reduction from the element uniqueness problem
Element uniqueness problem
In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.It is a well studied problem in many different models of computation...
basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.
Atomic problems
While these problems pose no computational complexity challenge, some of them are notable because of their ubiquity in computer applications of geometry.- Distance between a pair of line segmentLine segmentIn geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s. It cannot be expressed by a single formula, unlike, e.g., the distance from a point to a lineDistance from a point to a lineThe distance from a point to a line is the shortest distance from a point to a line in Euclidean geometry. It can be calculated in the following ways.-Cartesian coordinates:...
. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions. - Bounding box, the minimal axis-aligned hyperrectangleHyperrectangleIn geometry, an orthotope is the generalization of a rectangle for higher dimensions, formally defined as the Cartesian product of intervals....
that contains all geometric data
Problems on points
- Closest pair of points: Given N points, find two with the smallest distance between them
- Closest point query / nearest neighbor query query: Given N points, find one with the smallest distance to a given query point
- All nearest neighbors problem (construction of the nearest-neighbor graph): Given N points, find a closest one for each of them
- Diameter of a point setDiameter of a point setIn mathematics, the diameter of a point set is the maximum pairwise distance between two points in the set, or more generally, regardless of whether a maximum exists, the smallest upper bound on such distances....
: Given N points, find two with the largest distance between them - Width of a point set: Given N points, find two (hyper)planes with the smallest distance between them and with all points between them
- Minimum spanning treeMinimum spanning treeGiven a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
for a set of points- Euclidean minimum spanning treeEuclidean minimum spanning treeThe Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
- Euclidean minimum spanning tree
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
- Smallest enclosing sphere: Given N points, find a smallest sphere (circle) enclosing them all
- Largest empty circle: Given N points in the plane, find a largest circle centered within their convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
and enclosing none of them - Smallest enclosing rectangle: unlike the bounding box problem mentioned above, the rectangle may be of any orientation
- Largest empty rectangleLargest empty rectangleIn computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane...
- geometric spannerGeometric spannerA geometric spanner or a k-spanner graph or a k-spanner was initially introduced as a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most k times the spatial distance between these points for a fixed k...
, a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most 'k' times the spatial distance between these points for a fixed 'k'.
Other
- Shortest path among obstacles
- Distance of closest approachDistance of closest approach of ellipses and ellipsoidsThe distance of closest approach of two objects is the distance between their centers when they are externally tangent. The objects may be geometric shapes or physical particles with well defined boundaries...