What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let's consider the following specific problem:
input: $n$ integer points $(x_1, y_1), \ldots, (x_n, y_n)$ in the plane
output: are any three of the given points colinear?
Let's assume the standard RAM model of computation, with constant-time arithmetic on $O(\log n)$-bit integers. For upper bounds, feel free to assume that the given points' coordinates are $O(\log n)$-bit integers.
Exhaustive search (try all possible triples) can answer the question in $O(n^3)$ time. Perhaps this data structure yields an $\tilde O(n^{2})$-time algorithm. Are there faster algorithms, or any evidence that the problem cannot be solved in, say, $O(n\log n)$ time?