3SUM

Anyone who tries solving any interesting computational problem soon has to stare the NP-hardness ogre in the face.
Although proving a problem NP-hard can direct one's energies in the right direction (get an approximation, solve a special case), it can often be a nuisance.

One of the nice things about geometry is that (along with string matching and data structures), it is a rich source of problems which are in P i.e the problem can be solved in polynomial time. Some of the coolest algorithmic techniques come from geometry; getting an algorithm to run in time that is subquadratic in the input size can force one to delve into fairly hairy tricks.

But what if one is stuck ? There are many problems for which it seems extremely difficult to break the n² bound. This is where 3SUM comes in:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

A simple enough problem, and you can solve it in quadratic time. Not much is know about whether one can do any better. What makes this problem useful is that it can be used a proof of hardness for many other problems, much like we use one NP-hard problem to show another one NP-hard.

If you want to suggest that your favorite problem can't be solved in subquadratic time, reduce 3SUM to it i..e show that if you can solve this problem, you can also solve 3SUM. Voila, you can dump your problem on the ever more burdened back of 3SUM, and walk away a free geometer :)


More details on 3SUM here. It's a wiki page, so edit it if you have a problem that is known to be 3SUM-hard