Proximity problems
Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.
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 promlems
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 comfigurations.
- Bounding box, a minimal axis-aligned rectangle 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: Given N points, find a clesest 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
- Delaunay triangulation
- Voronoi diagram
- Smallest enclosing sphere: Given N points, find a smallest sphere (circle) enclosing them all
- Largest empty circle: Given N points, 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
Other
Reference
- Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 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.