4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Dec 8 '21 at 21:40
  • 3
    $\begingroup$ This problem is 3SUM-hard. A reference may be found in stackoverflow.com/questions/2734301/… $\endgroup$
    – Meng-Tsung Tsai
    Dec 9 '21 at 7:25
  • $\begingroup$ 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.] $\endgroup$
    – Neal Young
    Dec 9 '21 at 12:41
  • $\begingroup$ 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). $\endgroup$
    – Tassle
    Dec 12 '21 at 9:10
  • $\begingroup$ Actually, just compute the dual and see if there is a vertex incident to three lines. $\endgroup$
    – Tassle
    Dec 12 '21 at 9:31

Your Answer

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

Browse other questions tagged or ask your own question.