patternMinor
Complexity of determining whether three points are collinear from a set of points
Viewed 0 times
threedeterminingarepointssetfromwhethercomplexitycollinear
Problem
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,
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,
Solution
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.
See also this stackoverflow question, where I found the links given above.
Context
StackExchange Computer Science Q#77753, answer score: 5
Revisions (0)
No revisions yet.