Proximity problems is a class of problems in

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

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

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. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions. * Bounding box, 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 of ...

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 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 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 *

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

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

: 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 In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

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

: unlike the bounding box 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 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. Sh ...

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), whic ...

, 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 in ...

, 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