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, 2021 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, 2021 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, 2021 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, 2021 at 9:10
  • $\begingroup$ Actually, just compute the dual and see if there is a vertex incident to three lines. $\endgroup$
    – Tassle
    Dec 12, 2021 at 9:31

0

Reset to default

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.