  The 3SUM problem asks if an input $n$-set of real numbers contains a triple
whose sum is zero. We consider the 3POL problem, a natural generalization of
3SUM where we replace the sum function by a constant-degree polynomial in three
variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave a
$O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomial
equations when the solutions are taken from the cartesian product of three
$n$-sets of real numbers. We give algorithms for the corresponding problem of
counting such solutions. Gr\o nlund and Pettie recently designed subquadratic
algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed
light on the General Position Testing (GPT) problem: "Given $n$ points in the
plane, do three of them lie on a line?", a key problem in computational
geometry.
  We prove that there exist bounded-degree algebraic decision trees of depth
$O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved
in $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in the
real-RAM model. Among the possible applications of those results, we show how
to solve GPT in subquadratic time when the input points lie on $o({(\log
n)}^\frac{1}{6}/{(\log \log n)}^\frac{1}{2})$ constant-degree polynomial
curves. This constitutes a first step towards closing the major open question
of whether GPT can be solved in subquadratic time.
  To obtain these results, we generalize important tools --- such as batch
range searching and dominance reporting --- to a polynomial setting. We expect
these new tools to be useful in other applications.
