Proximity problems is a class of problems in computational geometry which involve estimation of

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

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 (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...

. A common trait for many of these problems is the possibility to establish the Θ(''n'' log ''n'')

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...

on their computational complexity by reduction from the

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 segments. It cannot be expressed by a single formula, unlike, e.g., the

distance from a point to a line In Euclidean geometry, the distance from a point to a line'' is the shortest distance from a given point to any point on an infinite straight line. It is the perpendicular distance of the point to the line, the length of the line segment which join ...

. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions. *

Bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...

, the minimal axis-aligned

hyperrectangle In geometry, an orthotopeCoxeter, 1973 (also called a hyperrectangle or a box) is the generalization of a rectangle to higher dimensions. A necessary and sufficient condition is that it is congruent to the Cartesian product of intervals. If all ...

that contains all geometric data

Problems on points

Closest pair of points The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...

: Given N points, find two with the smallest distance between them * Closest point query / nearest neighbor 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 The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a neare ...

): Given N points, find a closest one for each of them * Diameter of a point set: 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 tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

for a set of points **

Euclidean minimum spanning tree A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments ...

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...

Smallest enclosing sphere In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an d-dimensional solid sphere containing all of the ...

: Given N points, find a smallest sphere (circle) enclosing them all *

Largest empty circle In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in ''d''-dimensional space whose interior does not overlap with any given obstacles. Two dimensions The largest empty circl ...

: Given N points in the plane, find a largest circle centered within their convex hull and enclosing none of them * Smallest enclosing rectangle: unlike the

bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...

problem mentioned above, the rectangle may be of any orientation *

Largest empty rectangle In 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. There are a numb ...

Geometric spanner A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path ...

, a

weighted graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

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 approach The 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. The distance of closest approach is ...

References

* {{cite book , author =

Franco P. Preparata Franco P. Preparata is a computer scientist, the An Wang Professor, Emeritus, of Computer Science at Brown University. He is best known for his 1985 book "Computational Geometry: An Introduction" into which he blended salient parts of M. I. ...

and Michael Ian Shamos , title = Computational Geometry - An Introduction , publisher =

Springer-Verlag Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 ...

, year = 1985 , id = 1st edition: {{ISBN, 0-387-96131-3; 2nd printing, corrected and expanded, 1988: {{ISBN, 3-540-96131-3; Russian translation, 1989: {{ISBN, 5-03-001041-6 , isbn = 0-387-96131-3 , url-access = registration , url = https://archive.org/details/computationalgeo0000prep The proximity problems are covered in chapters 6 and 7. Geometric algorithms