3SUM-hardness for problems in computational geometry.

I explain the 3SUM problem, which an O(n^(2-ε)) solution has not been found for a long time. Based on the seminal paper by Gajentaan and Overmars, I give reductions from the 3SUM problem to various problems in computational geometry. This demonstrates the 3SUM-hardness of the problems discussed in this talk.

Computational geometry seminar series link