Proximity problems

Proximity problems is a class of problems in <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> which involve estimation of <a href="/facts/Distance/hbXlaEFk">distances</a> 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 <a href="/facts/Nearest_neighbor_search/R6QTyAph">nearest neighbor search</a>.
A common trait for many of these problems is the possibility to establish the <a href="/facts/Big_O_notation/weFFjSWg">Θ</a>(n log n) <a href="/facts/Lower_bound/YJje9oC2">lower bound</a> on their <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> by reduction from the <a href="/facts/Element_uniqueness_problem/Mwxm6SRv">element uniqueness problem</a> 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.

Proximity problems open-in-new

Proximity problems