<p>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:</p>
<p><strong>input:</strong> <em><span class="math-container">$n$</span> integer points <span class="math-container">$(x_1, y_1), \ldots, (x_n, y_n)$</span> in the plane</em></p>
<p><strong>output:</strong> <em>are any three of the given points colinear?</em></p>
<p>Let's assume the standard RAM model of computation, with constant-time arithmetic on <span class="math-container">$O(\log n)$</span>-bit integers.  For upper bounds, feel free to assume that the given points' coordinates are <span class="math-container">$O(\log n)$</span>-bit integers.</p>
<p>Exhaustive search (try all possible triples) can answer the question in <span class="math-container">$O(n^3)$</span> time.  Perhaps <a href="https://cstheory.stackexchange.com/q/42609/8237">this data structure</a> yields an <span class="math-container">$\tilde O(n^{2})$</span>-time algorithm.  Are there faster algorithms, or any evidence that the problem cannot be solved in, say, <span class="math-container">$O(n\log n)$</span> time?</p>

CC BY-SA 4.0
2021-12-08T21:40:13.987Z
Of course, by point-line duality, the problem is equivalent to the following: *given n straight lines in the plane, do any three of them intersect at a single point*?
Neal Young
CC BY-SA 4.0
2021-12-09T07:25:16.403Z
This problem is 3SUM-hard. A reference may be found in https://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear
Meng-Tsung Tsai
CC BY-SA 4.0
2021-12-09T12:41:57.887Z
Thank you @Meng-TsungTsai.  I think that question makes this one effectively a duplicate.  [For the record, as a comment there notes, there are subquadratic-time algorithms for 3SUM now, but they are just barely subquadratic.  I tried to vote to mark this question as a duplicate, but it's not allowed as the other question is not on cstheory.se.]
Neal Young
CC BY-SA 4.0
2021-12-12T09:10:39.733Z
Note also that you can get an $O(n^2)$ algorithm (without hashing) by first sorting all points circularly around $q$ for every $q$ in $S$. Doing that naively leads to a $O(n^2\log n)$ algorithm but you can do it in quadratic time by first constructing the dual arrangement. Then for every $q$ in $S$, you can get the circular order of the other points around $q$ by traversing the dual from left to right along some horizontal line and recording the lines you hit (by the zone theorem this can be done in linear time per point).
Tassle
CC BY-SA 4.0
2021-12-12T09:31:23.723Z
Actually, just compute the dual and see if there is a vertex incident to three lines.
Tassle
<reference-request><computational-geometry>
Complexity of detecting general position in the plane?
Neal Young
# Complexity of detecting general position in the plane?

(Asked by: username_0 on 2021-12-08)

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](https://cstheory.stackexchange.com/q/42609/8237) 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?

**Tags:** reference-request, computational-geometry

> **Comments:**
> **username_0**: Of course, by point-line duality, the problem is equivalent to the following: *given n straight lines in the plane, do any three of them intersect at a single point*?  
> **username_1**: This problem is 3SUM-hard. A reference may be found in https://stackoverflow.com/questions/2734301/given-a-set-of-points-find-if-any-of-the-three-points-are-collinear  
> **username_0**: Thank you @Meng-TsungTsai.  I think that question makes this one effectively a duplicate.  [For the record, as a comment there notes, there are subquadratic-time algorithms for 3SUM now, but they are just barely subquadratic.  I tried to vote to mark this question as a duplicate, but it's not allowed as the other question is not on cstheory.se.]  
> **username_2**: Note also that you can get an $O(n^2)$ algorithm (without hashing) by first sorting all points circularly around $q$ for every $q$ in $S$. Doing that naively leads to a $O(n^2\log n)$ algorithm but you can do it in quadratic time by first constructing the dual arrangement. Then for every $q$ in $S$, you can get the circular order of the other points around $q$ by traversing the dual from left to right along some horizontal line and recording the lines you hit (by the zone theorem this can be done in linear time per point).  
> **username_2**: Actually, just compute the dual and see if there is a vertex incident to three lines.  

---

## 0 answers

