#computational-geometry

Given $n$ integers, decide whether some three of them sum to zero. A simple algorithm takes $\mathcal{O}(n^2)$ time. Is there an algorithm that runs in time $\mathcal{O}(n^{2-\epsilon })$ for some fixed $\epsilon >0$?

A set of points in the plane is in general position if no three lie on a line. An empty hexagon in such a set is a convex hexagon whose vertices are points of the set and which contains no other point of the set. Find the smallest $N$ such that every $N$ points in general position contain an empty…