On a class of \(O(n^2)\) problems in computational geometry (Q419363)

To honor the winners of their 2011 Test-of-time award, the Computational Geometry journal has reprinted this 1995 article, in which the \textsc{3sum} problem is related to a diverse collection of other geometric computational problems. The \textsc{3sum} problem asks one to determine if, given a set of \(n\) integers, there are three integers from this set whose sum is zero. This problem is known to have a solution that runs in \(\Theta(n^2)\) time in the worst case, but it is not known if a faster solution exists. The authors define a problem \textsc{Pr} to be \textsc{3sum}-hard if \textsc{3sum} can be solved using \textsc{Pr} a constant number of times, plus an additional \(o(n^2)\) amount of time. It is shown that many problems are in fact \textsc{3sum} hard. Some incidence problems are \textsc{3sum}-hard, such as determining if there is a line that contains at least three points from among a collection of \(n\) points in the plane. There are separation problems that are also \textsc{3sum} hard, such as determining if there is non-horizontal line that does not intersect a given set of \(n\) (possibly half-infinite) horizontal line segments. Some covering problems also fit into this category. For instance, determining if the union of a set of \(n\) rectangular strips in the plane completely cover a given axis-aligned rectangle is \textsc{3sum}-hard. The authors show that there are visibility and motion problems that are also \textsc{3sum}-hard. The article is largely self-contained and accessible to a general audience familiar with computational geometry.