Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?
I wan't to know the complexity of this decision problem and present my approach as following.
SOLUTIONS. Let $n = |S|$. A naive brute-force takes time $\mathcal{O}(n^3)$. We can simply go through all triplets of points from $S$ and check for collinearity in time $\mathcal{O}(1)$.
I found additionally a $\mathcal{O}(n^2 \log{n})$ solution. For each $p(x_p \mid y_p) \in S$, we consider all points $q(x_q \mid y_q) \in S \setminus \{ p \}$ and compute the slope $m = \left|\frac{\Delta y}{\Delta x}\right| = \left| \frac{y_p - y_q}{x_p - x_q} \right|$ of the (unique) connecting line through $p$ and $q$. Resulting in a list of $n - 1$ slope values, we sort this list in time $\mathcal{O}(n \log {n})$ and use a linear search taking time $\mathcal{O}(n)$ for checking if two elements of the list are identical. If and only if this happens, three points of $S$ are collinear. Since we need time $\mathcal{O}(n \log {n})$ for each of these $n$ points, the whole thing runs in $\mathcal{O}(n^2 \log{n})$.
(Notice: We may assume the points of $S$ to be unique, because a simple preprocessing in time $\mathcal{O}(n \log {n})$ allows use to find duplicates. If $n \ge 3$ and there exists a duplicate, three points are obviously collinear.)
LOWER BOUNDS. A lower bound of $\Omega(n)$ is trivial. But we can do better. Let the set $X = \{ x_1, x_2, \dots, x_n \} \subseteq \mathbb{R}_+^n$ be an instance of the element distinctness problem (EDP). If is well-known, that EDP has a $\Omega(n \log {n})$ lower bound in many computational models (algebraic decision trees for instance). Define $S := \{ (x_1 \mid x_1^2), (x_2 \mid x_2^2), \dots, (x_n \mid x_n^2) \}$ and consider the following two cases.
Case 1: All elements of $X$ are distinct. Because the points of $S$ lie on the parabola $y = x^2$, there are no three collinear points.
Case 2: There are two indices $i, j \in \{ 1, 2, \dots, n \}$ with $i \neq j$ and $x_i = x_j$. Then, $x_i^2 = x_j^2$. If $n \ge 3$, select an arbitary value $x^* \in X \setminus \{ x_i, x_j \}$. Hence, we found three collinear points: $(x^* \mid (x^{*})^2), (x_i \mid x_i^2)$ and $(x_j \mid x_j^2)$.
By reduction principle, our problems complexity is $\Omega(n \log {n})$. Can we do better or is this lower bound optimal? Is there an $\mathcal{O}(n \log {n})$ algorithm?
