# Complexity of detecting general position in the plane?

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?

• 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? Dec 8, 2021 at 21:40
• This problem is 3SUM-hard. A reference may be found in stackoverflow.com/questions/2734301/… Dec 9, 2021 at 7:25
• 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.] Dec 9, 2021 at 12:41
• 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). Dec 12, 2021 at 9:10
• Actually, just compute the dual and see if there is a vertex incident to three lines. Dec 12, 2021 at 9:31