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 ele ...

on their

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

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 segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s. 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 joi ...

. 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 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 functio ...

nearest neighbor query 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 ...

: 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 ...

): Given N points, find a closest one for each of them *

Diameter of a point set In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

: Given N points, find two with the largest distance between them *

Width of a point set Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the In ...

: 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 ...

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 In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, ''etc.'' of the box. I ...

: 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 number ...

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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * ...

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 s ...

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. S ...

and

Michael Ian Shamos Michael Ian Shamos (born April 21, 1947) is an American mathematician, attorney, book author, journal editor, consultant and company director. He is (with Franco P. Preparata) the author of ''Computational Geometry'' (Springer-Verlag, 1985), wh ...

, 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