4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown in a survey of King on 3SUM-hard problems, where the problem is known as 3-points-on-line.

See also this stackoverflow question, where I found the links given above.

$\endgroup$
  • $\begingroup$ I'm not sure that these problems are the same. I would assume that due to rounding errors, you won't find points that are exactly collinear. Minimum are triangle might be achieved by three points that are just very close together and not at all collinear. $\endgroup$ – gnasher729 Jul 10 '17 at 12:10
  • $\begingroup$ In computational geometry there are no rounding errors. In fact, what you are criticizing is the concept of collinearity itself. $\endgroup$ – Yuval Filmus Jul 10 '17 at 12:15
  • $\begingroup$ It is also extremely likely that the algorithm can be adapted to solve the required problem directly. $\endgroup$ – Yuval Filmus Jul 10 '17 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.