Proximity problems

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.

A subset of these problems stated in terms of points only are sometimes referred to as closest point problems,^[1] 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.

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. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions.^[2]
Bounding box, the minimal axis-aligned hyperrectangle 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: 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 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 for a set of points
- Euclidean minimum spanning tree
Delaunay triangulation
Voronoi diagram
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 hull and enclosing none of them
Smallest enclosing rectangle: unlike the bounding box problem mentioned above, the rectangle may be of any orientation
Largest empty rectangle
Geometric spanner, 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

References

Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 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. The proximity problems are covered in chapters 6 and 7.

^ J. R. Sack and J. Urrutia (eds.) (2000). Handbook of Computational Geometry. North Holland. ISBN 0-444-82537-1. {{cite book}}: |author= has generic name (help)
^ V. J. Lumelsky (1985). "On fast computation of distance between line segments". Inf. Process. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.

[1] J. R. Sack and J. Urrutia (eds.) (2000). Handbook of Computational Geometry. North Holland. ISBN 0-444-82537-1. {{cite book}}: |author= has generic name (help)

[2] V. J. Lumelsky (1985). "On fast computation of distance between line segments". Inf. Process. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.

[1]

[2]