Threesomes, Degenerates, and Love Triangles

Allan Grønlund, Seth Pettie

The 3SUM problem is to decide, given a set of $n$ real numbers, whether any three sum to zero. It is widely conjectured that a trivial $O(n^2)$-time algorithm is optimal and over t…